The culprit is line 37. You write
isPalindrome(mLetters)
instead of
return isPalindrome(mLetters)
The first one returns it to nothing, and thus the function concludes by returning nil (by default). If you replace it with the second version things should check out.
#EDIT:
Ok, to address the second part of the question.
One thing you might be able to do to make it more efficient is by first converting the string to an array.
local stringArray = {}
for i=1, #str:len() do
stringArray[i] = str:sub(i, i)
end
This should only be around O(n) amortized, which is good. We're converting it to an array so that we can directly index letters and pass this around without too much overhead.
With this, we can rewrite the isPalindrome() function
local function isPalindrome(str, startIndex, endIndex)
local stringArray
local length
if type(str) == "string" then
stringArray = {}
length = str:len()
for i=1, length do
stringArray[i] = str:sub(i, i)
end
else
stringArray = str
end
startIndex = startIndex or 1
endIndex = endIndex or length
local fLetter = stringArray[startIndex]
local lLetter = stringArray[endIndex]
if endIndex - startIndex <= 1 then
return true
elseif fLetter:lower() == lLetter:lower() then
return isPalindrome(stringArray, startIndex + 1, endIndex - 1)
end
return false
end
As you can see, I've ditched the supporter functions and everything's contained within one more compact isPalindrome() function. The idea behind the modifications is that everything's inplace and that we only have to communicate information about indices between function calls instead of feeding the string each time and then further modifying that during each iteration.
To see if our hard work actually made the code more efficient, let's test its speed!
local startTime = tick()
local testString = "1234567890098765432112345678900987654321"
for i=0, 100000 do
local palindrome = isPalindrome(testString)
end
local endTime = tick()
print(endTime-startTime)
For your original function, it took around 3.48 seconds.
For the modified version, it only took 3.12 seconds.
This amounts to only about an 11% speed improvement, which is dismally small given how many modifications we made. However, 11% could also mean the difference between a player quitting your game due to lag and a player enjoying your game for what it is. Plus, this is recursive, so there's always going to be that added function call overhead slowing us down.
Still, I think we can do better. In fact, I'm sure we can. What I wrote was hastily scribbled and was treated with very limited foresight. It definitely can be optimized further.
But I think we're reinventing the wheel here...
string.reverse()
2 comments
The reason it's not a good idea is because of its efficiency, as BlueTaslem had previously pointed out. If you made references instead of duplicating the parts of the string, then the efficiency as well as memory utilization would be significantly improved
answered