25 December 2009
I love christmas. Coworkers are gone, email is quiet, distractions are at a minimum. The perfect opportunity to catch up on the things I've been meaning to get around to all year. One of them is releasing a port of the Diff Match Patch library in Lua. I had never heard of that programming language until an email from Duncan Cross landed in my inbox with a complete translation. Lua is currently an immature and a painfully slow language, so it took a bit of massaging to bring up to standards. Features such as Unicode support or String.lastIndexOf are entirely missing from the language, which necessitated some creative workarounds.
Pop quiz: How do the following lastIndexOf functions scale?
-- Test each substring starting from the rear. local function lastIndexOfSubstring(a, b) for i = #a, 1, -1 do if string.sub(a, i, i + #b - 1) == b then return i end end return -1 end -- Find all matches and return the last one. local function lastIndexOfFind(a, b) local i = -1 local j, answer repeat answer = i i, j = string.find(a, b, i + 1, true) until (i == nil) return answer end -- Reverse both strings and find the first match. local function lastIndexOfReverse(a, b) a = string.reverse(a) b = string.reverse(b) local i, j = string.find(a, b, start, true) if (i == nil) then return -1 end return #a - i - #b + 2 end
Answer: They are all O(n) and the last two are an order of magnitude faster than the first one. [Test script]
Speaking of christmas, this seems like an appropriate time to point out that the Vatican City contains 5.9 popes per square mile. It's true.