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

 
 

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

Submitted by:  Max Görner <maxg>
Submitted on:  Fri 21 Mar 2014 11:24:32 AM UTC  
 
Category: Octave Forge PackageSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: FixedAssigned to: None
Originator Name: Open/Closed: Closed
Release: otherOperating System: Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project Administrator
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>
Project Administrator
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>
Project Administrator
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 File(s):
   
   
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
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by jordigh (Posted a comment)
  • -unavailable- added by maxg (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 12 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 31 May 2015 05:23:49 PM UTCmtmillerStatusPatch Submitted=>Fixed
      Open/ClosedOpen=>Closed
    Fri 21 Mar 2014 04:38:58 PM UTCjordighStatusNone=>Patch Submitted
    Fri 21 Mar 2014 03:06:32 PM UTCmaxgAttached File-=>Added levenshtein.m, #30991
    Fri 21 Mar 2014 03:04:07 PM UTCmaxgAttached File-=>Added levenshtein.m, #30990
    Fri 21 Mar 2014 02:35:53 PM UTCcarandraugItem GroupFeature Request=>Performance
      StatusPatch Submitted=>None
      Release3.8.0=>other
    Fri 21 Mar 2014 02:35:05 PM UTCjordighStatusNone=>Patch Submitted
      SummaryO(n^2) memory usage for editdistance=>strings package: O(n^2) memory usage for editdistance
    Fri 21 Mar 2014 11:24:32 AM UTCmaxgAttached File-=>Added testMemorySavingVersionOfEditDistance.m, #30982
      Attached File-=>Added levenshtein.m, #30983

    Back to the top


    Powered by Savane 3.1-cleanup1