6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "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. \$\endgroup\$ – Mud Aug 7 '13 at 5:19
  • \$\begingroup\$ I did try both and got the same amount of time. The length is evaluated every time. I even get a performance boost. \$\endgroup\$ – Taka Aug 7 '13 at 5:31
  • \$\begingroup\$ "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. \$\endgroup\$ – Mud Aug 7 '13 at 15:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Taka Aug 7 '13 at 15:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Mud Aug 7 '13 at 15:34
4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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))
\$\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.