rubygems/rubygems — pull request #809 by tenderlove (2014-02-05 23:09:30+00:00)
Title: speed up levenshtein distance

This speeds up levenshtein distance calculation by about 1.6x. Levenshtein distance is used when you make a typo on `gem install`.

Here is my benchmark:

```ruby
require 'benchmark/ips'
require 'rubygems/text'

include Gem::Text

def min3 a, b, c
if a < b && a < c
a
elsif b < a && b < c
b
else
c
end
end

def levenshtein_distance2 str1, str2
s = str1
t = str2
n = s.length
m = t.length
max = n/2

return m if (0 == n)
return n if (0 == m)
return n if (n - m).abs > max

d = (0..m).to_a
x = nil

n.times do |i|
e = i+1

m.times do |j|
cost = (s[i] == t[j]) ? 0 : 1
x = min3(
d[j+1] + 1, # insertion
e + 1, # deletion
d[j] + cost) # substitution

d[j] = e
e = x
end

d[m] = x
end

return x
end

str1 = "hello world"
str2 = " hello world"

Benchmark.ips do |x|
x.report("original") { levenshtein_distance str1, str2 }
x.report("new") { levenshtein_distance2 str1, str2 }
end
```

Results:

```
[aaron@higgins rubygems (master)]$ ruby -I lib test.rb
Calculating -------------------------------------
original 800 i/100ms
new 1398 i/100ms
-------------------------------------------------
original 7969.3 (±5.5%) i/s - 40000 in 5.036031s
new 14185.3 (±3.3%) i/s - 71298 in 5.031767s
```