2
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.