Calculating the Hamming distance

Question

That's an easy one. I just want to calculate the Hamming distance between two strings.

function hamming(str1,str2)
  local distance = 0

  -- cannot calculate Hamming distance if strings have different sizes
  if #str1 ~= #str2 then return false end

  for i = 1, #str1 do
    if str1:sub(i,i) ~= str2:sub(i,i) then
      distance = distance + 1 
    end
  end

  return distance
end

Maybe the for-loop isn't the most efficient one. I'm not sure. Any improvements?

Answer 1

There is nothing inefficient about your loop. You are simply counting from 1 to #str1. Both bounds are known in advance. This is as good as it gets with loops in Lua.

The only improvement I could think of was using string.byte instead of string.sub, avoiding the interning of 1-character substrings. Even then, the difference is negligible, because the overhead of calling a C function (sub or byte) from the interpreter takes most of the CPU time.

Unless you run it under LuaJIT that is. Under LuaJIT, byte will be inlined into the body of the loop (where is consists only of a bounds check + array access) and the string interning (which requires an allocation + hash table lookup) dominates the CPU time.