search

hiddentao / fast-levenshtein

Efficient Javascript implementation of Levenshtein algorithm with locale-specific collator support.
MIT License
596 stars 56 forks source link

Make it 15 times faster #30

Closed ka-weihe closed 4 years ago

ka-weihe commented 4 years ago

This PR makes fast-levenshtein up to 15 times faster by utilizing fastest-levenshtein link. Many depend upon fast-levenshtein and this PR would make it the fastest again. No one would complain about that. Thanks in advance :slightly_smiling_face:

Benchmark

N = length of strings Numbers are in ops/sec Higher is better. 15 times faster when N = 1024

By merging this, fast-levenshtein will become as fast as fastest-levenshtein Test Target N=4 N=8 N=16 N=32 N=64 N=128 N=256 N=512 N=1024
fastest-levenshtein 44423 23702 10764 4595 1049 291.5 86.64 22.24 5.473
fast-levenshtein 18577 6112 1265 345 89.41 22.70 5.676 1.428 0.348

Using your benchmark I get:

Before: >> fast-levenshtein x 2,768 ops/sec ±0.91% (101 runs sampled)

After: >> fast-levenshtein x 12,703 ops/sec ±3.16% (96 runs sampled)

hiddentao commented 4 years ago

Hahaha, thanks a lot 😆

I can merge this.

ka-weihe commented 4 years ago

Thanks a lot, I appreciate it :slightly_smiling_face: