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] Updated: (LANG-413) Memory usage improvement for StringUtils#getLevenshteinDistance()
Date Thu, 21 Feb 2008 11:27:21 GMT

     [ 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.


Mime
View raw message