# Lua string parsing

The following code takes a string and converts it to it's number equivalent. A=1 ... Z=26, while keeping all other characters intact. It formats the string using two delimiters. One for between characters and one for between words. I want to optimize it, and have fixed a lot of redundancy, and slow parts. However, I can't seem to make it any faster. The longest amount of time is taken for decrypting an encrypted string. I would like to optimize both parts.

Suggestions on techniques or code with explanation would be most helpful. This is mostly for me to understand the bottlenecks in Lua logic.

function parseString(str,del1,del2)
local delim1 = del1 or ' '
local delim2 = del2 or '-'
local tab = {}
local sub = ''
local index = 1
local c = ''
local i = 1
while (i > #str and sub == '') == false do
c = str:sub(i,i)
if c == delim2 or c == delim1 or c == '' then
if string.match(sub,'%d') == nil then
tab[index] = sub
index = index + 1
else
tab[index] = string.char(tonumber(sub) + 96)
index = index + 1
end
if c == delim1 then
tab[index] = ' '
index = index + 1
end
sub = ''
else
sub = sub .. c
end
i = i + 1
end
return table.concat(tab)
end
function strToNums(str)
local t = {string.byte(str,1,#str)}
for i,v in ipairs(t) do
if v < 97 and v >= 65then
t[i] = v - 64
else
if v <= 172 and v >= 97then
t[i] = v - 96
else
t[i] = v
end
end
end
return t
end
function formater(del1,del2,arg)
local out = {}
local index = 1
local nDel1 = string.byte(del1)
local nDel2 = string.byte(del2)
for i,v in ipairs(arg) do
if v <= 26 and v >= 1 then
out[index] = tostring(v)
index = index + 1
if i < #arg and arg[i+1] ~= nDel1 then
out[index] = del2
index = index + 1
end
else
if v == 32 then
out[index]  = del1
index = index + 1
else
out[index] = string.char(v)
index = index + 1
if i < #arg and arg[i+1] ~= nDel1 then
out[index] = del2
index = index + 1
end
end
end

end
return table.concat(out)
end
function main()
local line = ''
local del1 = ' '
local del2 = '-'
local x = os.clock()
local line2 = ''
local str =''
for i=1,1000 do
str = strToNums("This string'll test my system!")
line = formater(del1,del2,str)
line2 = parseString(line,del1,del2)
end
print(line,line2)
print(string.format("elapsed time: %.10f\n", os.clock() - x))
--  while true do
--      line = io.read()
--      if string.match(line,'%a+') == nil then break end
--      line = formater(del1,del2,strToNums(line))
--      print(line)
--      print(parseString(line,del1,del2))
--  end
end
main()


This is the output that I would expect for the given input:

20-8-9-19 19-20-18-9-14-7-'-12-12 20-5-19-20 13-25 19-25-19-20-5-13-!   this string'll test my system!
elapsed time: 0.0880000000


strToNum takes a string and converts it to a table of char values.

Formatter takes two types of delimiters: one for between characters and one for between words. It also takes the table of values generated by strToNum. It takes these values and creates a string with each character separated by one delimiter and each word separated by another.

parseString takes a string and two delimiters. The delimiters are to be checked against. The string is iterated over, and between iterators another sub string is created and added to as long as there is not a delimiter. Each time it runs into a delimiter it adds it to a table. Which is then concatenated at the end. This function takes the most amount of time to run. I think it is because of the using substring, string.char and tonumber.

edit: It certainly became faster. Not quite twice as fast though. I see a lot of the redundancies in my code now. Mine with just encoding

> lua numandstring.lua
20-8-9-19 19-20-18-9-14-7-'-12-12 20-5-19-20 13-25 19-25-19-20-5-13-!
elapsed time: 0.0330000000
new one with just encoding

> lua numandstring.lua
20-8-9-19 19-20-18-9-14-7-'-12-12 20-5-19-20 13-25 19-25-19-20-5-13-!
elapsed time: 0.0280000000


I squeezed out a little more speed with

function encode3(input, wordDelimiter, characterSeparator)
local out = {}
input = input:upper()
local index = 1
local c = input:sub(1,1)
local inputLength = #input
for i=1,inputLength do
local nextc = input:sub(i+1,i+1)
if c == wordDelimiter then
out[index] = c
index = index + 1
else
out[index] = lookup[c] or  c
index = index + 1
if i < inputLength and nextc ~= wordDelimiter then
out[index] = characterSeparator
index = index + 1
end
end

c = nextc
end

return table.concat(out)
end


I eliminated calling the table length method repeatedly, because it has to iterate over the whole table. C habits die hard.

> lua numandstring.lua
20-8-9-19 19-20-18-9-14-7-'-12-12 20-5-19-20 13-25 19-25-19-20-5-13-!
elapsed time: 0.0250000000


Also the calls to the first sub make no difference. Sub is called the same amount of times either way.

• "Sub is called the same amount of times either way". Um, no. Try removing the call outside the loop. BTW, the table length call in the for loop is evaluated only once. – Mud Aug 7 '13 at 5:19
• I did try both and got the same amount of time. The length is evaluated every time. I even get a performance boost. – Taka Aug 7 '13 at 5:31
• "The length is evaluated every time." All three control expressions are evaluated only once, before the loop starts. This is Lua 101. "I even get a performance boost." Because your benchmarking sucks. This stuff trivial to prove. Run this: function x() print('x') return 10 end for i=1,x() do end Note how many times x is called. – Mud Aug 7 '13 at 15:19
• You completely missed what I was saying. When you use the length of a table as an index for the table it has to iterate through the table to find the new table length. i.e. this: "out[#out +1] = c". I know for a loop it is only called once btw. – Taka Aug 7 '13 at 15:22
• I said "The table length call IN THE FOR LOOP is evaluated only once." You responded "The length is evaluated every time." Can you see why I would "miss what you're saying"? You responded to a comment about the for loop. If you were talking about something else entirely, there's no possible way I could know that. My point is that your code removes the length check from the for loop, when there's no reason to do that. That length call happens only once. – Mud Aug 7 '13 at 15:34

## 2 Answers

Your code is a bit is overcomplicated. There are a million ways to skin this cat, but I'll show a few. They're all about twice as fast as your code on my machine:

The most concise would be to let Lua do most of the parsing for us. We'll first chop the string into words, then chop each word into characters, convert the characters, concat the characters back into a word with the character delimiter, then concat the words back into a string with the word delimiter:

function encode1(input, wordDelimiter, characterSeparator)
local ascii_offset = ('A'):byte() - 1
local words = {}

for word in input:upper():gmatch('[^'..wordDelimiter..']+') do
local encodedWord = {}
for c in word:gmatch('.') do
encodedWord[#encodedWord + 1] = c:match('%w') and c:byte() - ascii_offset or c
end
words[#words + 1] = table.concat(encodedWord, characterSeparator)
end

return table.concat(words, wordDelimiter)
end


Usage and output:

print(encode("This string'll test my system!", ' ', '-'))

20-8-9-19 19-20-18-9-14-7-'-12-12 20-5-19-20 13-25 19-25-19-20-5-13-!


To make it a bit faster, we can use a lookup table to find the value for a character.

local lookup = {
A= 1, B= 2, C= 3, D= 4, E= 5, F= 6, G= 7, H= 8, I= 9, J=10, K=11, L=12, M=13,
N=14, O=15, P=16, Q=17, R=18, S=19, T=20, U=21, V=22, W=23, X=24, Y=25, Z=26,
}

function encode2(input, wordDelimiter, characterSeparator)
local words = {}

for word in input:upper():gmatch('[^'..wordDelimiter..']+') do
local encodedWord = {}
for c in word:gmatch('.') do
encodedWord[#encodedWord + 1] = lookup[c] or c
end
words[#words + 1] = table.concat(encodedWord, characterSeparator)
end

return table.concat(words, wordDelimiter)
end


Something a bit closer to your approach (manually parsing the input) is a bit more complicated but is measurably faster:

function encode3(input, wordDelimiter, characterSeparator)
input = input:upper()
local out = {}
local c = input:sub(1,1)
for i=1,#input do
local nextc = input:sub(i+1,i+1)
if c == wordDelimiter then
out[#out + 1] = c
else
out[#out + 1] = lookup[c] or  c
if i < #input and nextc ~= wordDelimiter then
out[#out + 1] = characterSeparator
end
end
c = nextc
end

return table.concat(out)
end


Notice that I make the first call to sub outside of the loop so that I only need one sub call in the loop. Not doing this makes a measurable speed difference.

You can use a translation table with gsub, as in the code below:

local t={}
for c in ("abcdefghijklmnopqrstuvwxyz"):gmatch(".") do
local k=c:upper()
local v=(k:byte()-("A"):byte()+1).."-"
t[c]=v
t[k]=v
end

s="This string'll test my system!"
s=s:gsub("%A+","/")
print(s:gsub("%a",t))