Repository: commons-lang Updated Branches: refs/heads/master 031f6b082 -> 49455b78b
LANG-1234: getLevenshteinDistance with a threshold: optimize implementation if the strings lengths differ more than the threshold (closes #118) If the string lengths differ more than the threshold, there's no need for the algorithm to begin allocating arrays etc. Project: http://git-wip-us.apache.org/repos/asf/commons-lang/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-lang/commit/04b41e2c Tree: http://git-wip-us.apache.org/repos/asf/commons-lang/tree/04b41e2c Diff: http://git-wip-us.apache.org/repos/asf/commons-lang/diff/04b41e2c Branch: refs/heads/master Commit: 04b41e2c97fe5faaf521c2e0581c30e18e2f0c27 Parents: 031f6b0 Author: Jonatan Jönsson <[email protected]> Authored: Thu Nov 26 10:23:15 2015 +0100 Committer: pascalschumacher <[email protected]> Committed: Sat May 21 16:47:59 2016 +0200 ---------------------------------------------------------------------- src/main/java/org/apache/commons/lang3/StringUtils.java | 4 ++++ 1 file changed, 4 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-lang/blob/04b41e2c/src/main/java/org/apache/commons/lang3/StringUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/lang3/StringUtils.java b/src/main/java/org/apache/commons/lang3/StringUtils.java index 31a572a..c169e0a 100644 --- a/src/main/java/org/apache/commons/lang3/StringUtils.java +++ b/src/main/java/org/apache/commons/lang3/StringUtils.java @@ -7585,6 +7585,10 @@ public class StringUtils { } else if (m == 0) { return n <= threshold ? n : -1; } + // no need to calculate the distance if the length difference is greater than the threshold + else if (Math.abs(n - m) > threshold) { + return -1; + } if (n > m) { // swap the two strings to consume less memory
