You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Cédrik LIME (JIRA)" <ji...@apache.org> on 2008/02/21 11:35:19 UTC

[jira] Created: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()

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.


[jira] Updated: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()

Posted by "Cédrik LIME (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LANG-413?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Cédrik LIME updated LANG-413:
-----------------------------

    Attachment: StringUtils-Levenshtein.patch

Patch as attachment

> 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
>         Attachments: StringUtils-Levenshtein.patch
>
>   Original Estimate: 0.17h
>  Remaining Estimate: 0.17h
>
> 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.


[jira] Updated: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()

Posted by "Henri Yandell (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LANG-413?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Henri Yandell updated LANG-413:
-------------------------------

    Remaining Estimate:     (was: 0.17h)
     Original Estimate:     (was: 0.17h)

> 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
>             Fix For: 2.4
>
>         Attachments: StringUtils-Levenshtein.patch
>
>
> 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.


[jira] Closed: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()

Posted by "Henri Yandell (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LANG-413?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Henri Yandell closed LANG-413.
------------------------------

    Resolution: Fixed

svn ci -m "Applying Cedrik Lime's patch to LANG-413; improving the memory footprint of getLevenshteinDistance" src

Sending        src/java/org/apache/commons/lang/StringUtils.java
Transmitting file data .
Committed revision 630580.

> 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
>             Fix For: 2.4
>
>         Attachments: StringUtils-Levenshtein.patch
>
>
> 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.


[jira] Updated: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()

Posted by "Henri Yandell (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LANG-413?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Henri Yandell updated LANG-413:
-------------------------------

    Fix Version/s: 2.4

> 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
>             Fix For: 2.4
>
>         Attachments: StringUtils-Levenshtein.patch
>
>
> 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.