[Python-checkins] suggestions.c: Improve efficiency of levenshtein_distance method (#91835)
JelleZijlstra
webhook-mailer at python.org
Mon May 2 13:09:46 EDT 2022
https://github.com/python/cpython/commit/feb45d0ae98f3030b2b07089bc0eb066b69f5625
commit: feb45d0ae98f3030b2b07089bc0eb066b69f5625
branch: main
author: Pieter Eendebak <pieter.eendebak at gmail.com>
committer: JelleZijlstra <jelle.zijlstra at gmail.com>
date: 2022-05-02T11:09:35-06:00
summary:
suggestions.c: Improve efficiency of levenshtein_distance method (#91835)
files:
M Python/suggestions.c
diff --git a/Python/suggestions.c b/Python/suggestions.c
index d9e69fa7e0db2..b84acaaed6b1f 100644
--- a/Python/suggestions.c
+++ b/Python/suggestions.c
@@ -78,9 +78,11 @@ levenshtein_distance(const char *a, size_t a_size,
// Instead of producing the whole traditional len(a)-by-len(b)
// matrix, we can update just one row in place.
// Initialize the buffer row
+ size_t tmp = MOVE_COST;
for (size_t i = 0; i < a_size; i++) {
// cost from b[:0] to a[:i+1]
- buffer[i] = (i + 1) * MOVE_COST;
+ buffer[i] = tmp;
+ tmp += MOVE_COST;
}
size_t result = 0;
More information about the Python-checkins
mailing list