Levenstein distance performance

[marcomorain]

The levenshtein/distance function has very poor performance for even short strings – is this a known issue? It takes 10 seconds on a MacBook Pro (3 GHz Intel Core i7) running Java 8.

user=> (time (clj-fuzzy.levenshtein/distance "feature" "get-project-features"))
"Elapsed time: 10438.251547 msecs"
13

[Yomguithereal]

Hello @marcomorain, I've just run your test and must say you are right. There is something fishy here.I start investigating.

[marcomorain]

thanks!

On Wed, Jan 7, 2015 at 6:35 PM, Guillaume Plique notifications@github.com
wrote:

Hello @marcomorain https://github.com/marcomorain, I've just run your
test and must say you are right. There is something fishy here.I start
investigating.

—
Reply to this email directly or view it on GitHub
#33 (comment)
.

[Yomguithereal]

I just deployed a faster version thanks to this gist's implementation without relying on external core.matrix.

Can you test that and tell me if this feels better?

[marcomorain]

I've just changed my code to use this impl:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Clojure

I'll try your again if I get some free time tomorrow.

Thanks!

On Wed, Jan 7, 2015 at 7:02 PM, Guillaume Plique notifications@github.com
wrote:

I just deployed a faster version thanks to this
https://gist.github.com/vishnuvyas/958488 gist's implementation without
relying on external core.matrix.

Can you test that and tell me if this feels better?

—
Reply to this email directly or view it on GitHub
#33 (comment)
.

[marcomorain]

⭐

clj-fuzzy.levenshtein=> (time (distance "feature" "get-project-features"))
"Elapsed time: 0.535482 msecs"
13

Awesome!

[marcomorain]

🚀