Memory usage improvement for StringUtils#getLevenshteinDistance()
-----------------------------------------------------------------
Key: LANG-413
URL: https://issues.apache.org/jira/browse/LANG-413
Project: Commons Lang
Issue Type: Improvement
Affects Versions: 2.3
Reporter: Cédrik LIME
Priority: Minor
StringUtils#getLevenshteinDistance() has recently been optimized to conserve a
whole lot of memory, which is good. Since the algorithm is symmetric, we can go
even further by selecting the shortest of the 2 input Strings to work upon :
Index:
/Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java
===================================================================
---
/Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java
(revision 629728)
+++
/Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java
(working copy)
@@ -5737,6 +5737,15 @@
return n;
}
+ if (n > m) {
+ // swap the input strings to consume less memory in p[] and d[]
+ String tmp = s;
+ s = t;
+ t = tmp;
+ n = m;
+ m = t.length();
+ }
+
int p[] = new int[n+1]; //'previous' cost array, horizontally
int d[] = new int[n+1]; // cost array, horizontally
int _d[]; //placeholder to assist in swapping p and d
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
