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.