Re: [useless] Having some fun with lua

[Peter Odding <peter@...>]

Geoffroy Carrier schreef:
> Hello!
>
> An "ridiculous" evaluation of the Levenshtein distance in pure Lua:
> http://gist.github.com/158506/
> I took no care in the "quality" of this code, so you might want to
> tear your eyes out.
> I'd be very interested in performance tweaks/code reduction, from
> minor remarks to global rewrites, as long as it remains pure Lua with
> standard libraries. I didn't think a lot about it, specially the use
> of table.sort which must be stupid.

I don't have any real insights but my implementation of Levenshtein uses 
a single Lua table to hold the whole matrix. I haven't a clue how much 
faster this is but it must account for something, with all that table 
creation :)

function levenshtein(s, t)
	local d, sn, tn = {}, #s, #t
	local byte, min = string.byte, math.min
	for i = 0, sn do d[i * tn] = i end
	for j = 0, tn do d[j] = j end
	for i = 1, sn do
		local si = byte(s, i)
		for j = 1, tn do
			d[i*tn+j] = min(d[(i-1)*tn+j]+1, d[i*tn+j-1]+1, d[(i-1)*tn+j-1]+(si 
== byte(t,j) and 0 or 1))
		end
	end
	return d[#d]
end

 - Peter