bugGNU Octave - Bugs: bug #41920, strings package: O(n^2) memory...

 
 

bug #41920: strings package: O(n^2) memory usage for editdistance

Submitter:  Max Görner <maxg>
Submitted:  Fri 21 Mar 2014 11:24:32 AM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 31 May 2015 05:23:49 PM UTC, comment #6: 

The referenced patch #8426 has been applied to the strings mercurial repo. Closing as fixed.

Mike Miller <mtmiller>
Group Member
Mon 31 Mar 2014 10:56:47 AM UTC, comment #5: 

I wrote an even better version which is faster and memory efficient on demand. See https://savannah.gnu.org/patch/index.php?8426 .

Max Görner <maxg>
Fri 21 Mar 2014 04:38:58 PM UTC, comment #4: 

Rule 2 is actually one of the best parts of the style: since this language does not have separate syntax for function calls and indexing, we have to do make the distinction elsehow. You suck if you disagree. ;-)

You still are missing newlines after your if and else statements.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Fri 21 Mar 2014 03:06:32 PM UTC, comment #3: 

forgot about rule 8

(file #30991)

Max Görner <maxg>
Fri 21 Mar 2014 03:04:07 PM UTC, comment #2: 

Please find the octave style function attached. Please note, that most of the not accepted code is already part of the package 'statistics'.

I also updated the documentation.

PS: Rule 2 and Rule 6 suck ;-).

(file #30990)

Max Görner <maxg>
Fri 21 Mar 2014 02:35:05 PM UTC, comment #1: 

Can you please write this in Octave style instead of Matlab style?

1) Informative end statements
2) Space for functioncall () but not space for indexing()
3) "Double quoted strings", not 'single quoted'
4) #octothorpe comment character, not %percentage.
5) Newline after if statement
6) Round brackets around condition of an if (statement)
7) No pointless commented out code, just delete inactive lines.
8) Spaces after commas.

Jordi Gutiérrez Hermoso <jordigh>
Group Member
Fri 21 Mar 2014 11:24:32 AM UTC, original submission:  

The calculation of the levenshtein distance creates an 2D-Array to store distance values. If one tries to calculate the distance between two not very short strings (2^13 <= l < 2^14), the function fails since the array cannot be constructed.

However, not all the array is needed. All what is needed are 2 rows of the array. Therefore, the implementation should be changed or enhanced to enable users to use the memory efficient version.

I attached a proposal for such an algorithm. It contains only some changes to the old one.

I tested the correctness of that version using the second script.

Max Görner <maxg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #30991:  levenshtein.m added by maxg (2KiB - text/x-objcsrc)
file #30990:  levenshtein.m added by maxg (2KiB - text/x-objcsrc)
file #30983:  levenshtein.m added by maxg (788B - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mtmiller (Posted a comment)
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by maxg (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 12 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-05-31 mtmiller StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2014-03-21 jordigh StatusNone Patch Submitted
    2014-03-21 maxg Attached File- Added levenshtein.m, #30991
    2014-03-21 maxg Attached File- Added levenshtein.m, #30990
    2014-03-21 carandraug Item GroupFeature Request Performance
        StatusPatch Submitted None
        Release3.8.0 other
    2014-03-21 jordigh StatusNone Patch Submitted
        SummaryO(n^2) memory usage for editdistance strings package: O(n^2) memory usage for editdistance
    2014-03-21 maxg Attached File- Added testMemorySavingVersionOfEditDistance.m, #30982
        Attached File- Added levenshtein.m, #30983

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code