← Back to index | Original Bugzilla link

Bug 13834 – make levenshteinDistance @nogc

Status: RESOLVED
Resolution: FIXED
Severity: enhancement
Priority: P1
Component: phobos
Product: D
Version: D2
Platform: All
OS: All
Creation time: 2014-12-08T14:56:08Z
Last change time: 2018-03-26T23:57:30Z
Assigned to: No Owner
Creator: Martin Nowak

Comments

Comment #0 by code — 2014-12-08T14:56:08Z

It currently allocates a matrix for the computation. That could be easily done with a temporary buffer (using the stack up to a certain threshold, then falling back to malloc). The levenshteinDistancePath function should take an output range for the edit ops.

Comment #1 by code — 2015-02-16T23:35:45Z

Implementing the more space efficient variant of the algorithm when the final path isn't needed is another optimization. http://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows

Comment #2 by bugzilla — 2015-04-10T04:03:28Z

Remove GC allocation for matrix: https://github.com/D-Programming-Language/phobos/pull/3170

Comment #3 by greensunny12 — 2018-03-26T23:57:30Z

The Phobos PR has been merged.