Neil's News

Lua Diff

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]

[Performance plot of three algorithms]

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.

< Previous | Next >

Neil Fraser: News: Lua Diff