commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Cédrik LIME (JIRA) <j...@apache.org>
Subject [jira] Created: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()
Date Thu, 21 Feb 2008 10:35:19 GMT
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.


Mime
View raw message