Lua Code Efficiency

[Snavy]

I am a beginner in LUA, and i've made a script which checks wether a player exists in a room of 3SQM(s).
I believe this is not the most efficient version of it so I decided to came here and get some feedback.

local positions = {
    {x=1005, y=992, z=6, stackpos=253},
    {x=1006, y=992, z=6, stackpos=253},
    {x=1007, y=992, z=6, stackpos=253}
}

local kickPos = {x=1006, y=994, z=6}

function onUse(cid, item, fromPosition, itemEx, toPosition)

    for i=1, table.maxn(positions) do
        -- (I am) the player in room, teleport me out.
        if getTopCreature(positions[i]).uid == cid then
            doTeleportThing(cid, kickPos)
            doSendMagicEffect(getCreaturePosition(cid), 4)
            return true
        end

        if isPlayer(getTopCreature(positions[i]).uid) then
            -- Player Exists in room
            doPlayerSendTextMessage(cid, MESSAGE_EVENT_DEFAULT, "There's someone in the room! Please wait. ")
            doSendMagicEffect(getCreaturePosition(cid), 2)
            return true
        end
    end  
  
    -- no player was found, teleport me in!
    doTeleportThing(cid, positions[2])
    doSendMagicEffect(getCreaturePosition(cid), MAGIC_EFFECT_FIREATTACK)

    return true
end

 

[Night Wolf]

You could explain it a little better, why have you made this check right here?

1. if getTopCreature(positions).uid == cid then
   [*] doTeleportThing(cid, kickPos)
   [*] doSendMagicEffect(getCreaturePosition(cid), 4)
   [*] return true
   [*] end
   
   Are you using this as actionid on two different levers, one as a exit lever?
   

 

[ScorpionOT]

local positions = {
    ["a"] = {x=1005, y=992, z=6}, -- min pos (a)
    ["b"] = {x=1007, y=992, z=6}  -- max pos (b)
}

--[[
[a 1 1 1] -- a -> min pos
[1 1 1 1]
[1 1 1 b] -- b -> max pos
--]]
local kickPos = {x=1006, y=994, z=6}
local initPos = {x=1006, y=992, z=6}

function onUse(cid, item, fromPosition, itemEx, toPosition)

    for posx=positions['a'].x, positions['b'].x do
        for posy=positions['a'].y, positions['b'].y do
            for posz=positions['a'].z, positions['b'].z do
                local posit = {x=posx, y=posy, z=posz, stackpos=253}
           
                -- (I am) the player in room, teleport me out.
                if getTopCreature(posit).uid == cid then
                    doTeleportThing(cid, kickPos)
                    doSendMagicEffect(kickPos, 4)
                    return true
                end
         
                if isPlayer(getTopCreature(posit).uid) then
                    -- Player Exists in room
                    doPlayerSendTextMessage(cid, MESSAGE_EVENT_DEFAULT, "There's someone in the room! Please wait. ")
                    doSendMagicEffect(getCreaturePosition(cid), 2)
                    return true
                end
            end
        end
    end 

    -- no player was found, teleport me in!
    doTeleportThing(cid, initPos)
    doSendMagicEffect(initPos, MAGIC_EFFECT_FIREATTACK)

    return true
end

Might be a bit more efficient this way.

 

[samco]

local positions = {
    ["a"] = {x=1005, y=992, z=6}, -- min pos (a)
    ["b"] = {x=1007, y=992, z=6}  -- max pos (b)
}

--[[
[a 1 1 1] -- a -> min pos
[1 1 1 1]
[1 1 1 b] -- b -> max pos
--]]
local kickPos = {x=1006, y=994, z=6}
local initPos = {x=1006, y=992, z=6}

function onUse(cid, item, fromPosition, itemEx, toPosition)

    for posx=positions['a'].x, positions['b'].x do
        for posy=positions['a'].y, positions['b'].y do
            for posz=positions['a'].z, positions['b'].z do
                local posit = {x=posx, y=posy, z=posz, stackpos=253}
          
                -- (I am) the player in room, teleport me out.
                if getTopCreature(posit).uid == cid then
                    doTeleportThing(cid, kickPos)
                    doSendMagicEffect(kickPos, 4)
                    return true
                end
        
                if isPlayer(getTopCreature(posit).uid) then
                    -- Player Exists in room
                    doPlayerSendTextMessage(cid, MESSAGE_EVENT_DEFAULT, "There's someone in the room! Please wait. ")
                    doSendMagicEffect(getCreaturePosition(cid), 2)
                    return true
                end
            end
        end
    end

    -- no player was found, teleport me in!
    doTeleportThing(cid, initPos)
    doSendMagicEffect(initPos, MAGIC_EFFECT_FIREATTACK)

    return true
end

Might be a bit more efficient this way.

How comes 3 fors is more efficient than just one?

Efficiency of first code is O(n), Efficiency of yours is O(n^3) which is way worse.

 

[ScorpionOT]

There are different types of efficiency, this is readability and redaction efficiency. Having more loop buckles is not necessarily inefficient, as long as it complies with the idea in mind. Perhaps you should read a document on efficiency before you go ahead and make hasty judgment of my coding preference (i.e https://www.lua.org/gems/sample.pdf).

Here are two benchmarks on the code, based on time:
Yours-------------------------------------------------------------------> Mine

Lua Performance Tests
lua-users wiki: Object Benchmark Tests

Additionally, here's another tool oriented to profiling memory tests for scripts being run in Lua if you're really willing to instigate further:
http://www.lua.org/wshop15/Musa2.pdf

Edit: oh also
Mind you we are checking for an area. Manually adding position per position to check every place to be used in the code might not be as efficient if the area is more ample than initially proposed, thus, having different loops to check from startPos to endPos would be optimal in certain circumstances, specially if the iteration function is not too heavy on the memory (as you can see it virtually takes no time from the memory, as stated in seconds... if you wish to be really specific and check for milliseconds, you could alternatively use the os.clock function as such:

 print(string.format("elapsed time: %.2f\n", os.clock() - initTime))

).

 

[samco]

There are different types of efficiency, this is readability and redaction efficiency. Having more loop buckles is not necessarily inefficient, as long as it complies with the idea in mind. Perhaps you should read a document on efficiency before you go ahead and make hasty judgment of my coding preference (i.e https://www.lua.org/gems/sample.pdf).

Here are two benchmarks on the code, based on time:
Yours-------------------------------------------------------------------> Mine

Lua Performance Tests
lua-users wiki: Object Benchmark Tests

Additionally, here's another tool oriented to profiling memory tests for scripts being run in Lua if you're really willing to instigate further:
http://www.lua.org/wshop15/Musa2.pdf

Edit: oh also
Mind you we are checking for an area. Manually adding position per position to check every place to be used in the code might not be as efficient if the area is more ample than initially proposed, thus, having different loops to check from startPos to endPos would be optimal in certain circumstances, specially if the iteration function is not too heavy on the memory (as you can see it virtually takes no time from the memory, as stated in seconds... if you wish to be really specific and check for milliseconds, you could alternatively use the os.clock function as such:

 print(string.format("elapsed time: %.2f\n", os.clock() - initTime))

).

Sure its makes no difference in this case. And maybe because language i understand efficiency just as performance. Readability is another thing complete different for me.
To be honest i still think code is not efficient nor readable.

thanks for the pdf.

 

[ScorpionOT]

Alright. In order to understand the subject, perhaps you would also like to look a little more into memory allocation research, so that you can become a little more cultured on the subject instead of making blatant statements. I'll refer you to an investigation on the matter, in case you should find it relevant: Lua object memory sizes

Edit #1: also, it does make a difference. The code I converted is more efficient, both memory wise and runtime wise. Please be careful with your statements, and make sure you look into the subject first before going ahead and spouting whatever comes to your mind; it might make you be brushed off as ignorant.

Edit #2: Please do elaborate though, how is the code not readable to you?

If you wish to learn more about code optimizing, read at your own caution:
Writing Efficient Code

Heck, if you really wanna learn about it, let's go back to the C language, from which Lua is based. Here are a few tutorials in relation to memory allocation and the weight of operation accessing variables, in comparison to deterministic functional code elaborated with the same purpose.
Chapter 8: Pointers and Memory Allocation · Learning C with Pebble
https://www.cs.swarthmore.edu/~newhall/unixhelp/C_arrays.html

Perhaps you should also look into dynamic vs static memory allocation and the different weight it releases upon a machine:
https://stackoverflow.com/questions...mory-allocation-and-dynamic-memory-allocation
https://stackoverflow.com/questions/2672085/static-array-vs-dynamic-array-in-c

 

[Ninja]

Spoiler

local positions = {
    ["a"] = {x=1005, y=992, z=6}, -- min pos (a)
    ["b"] = {x=1007, y=992, z=6}  -- max pos (b)
}

--[[
[a 1 1 1] -- a -> min pos
[1 1 1 1]
[1 1 1 b] -- b -> max pos
--]]
local kickPos = {x=1006, y=994, z=6}
local initPos = {x=1006, y=992, z=6}

function onUse(cid, item, fromPosition, itemEx, toPosition)

    for posx=positions['a'].x, positions['b'].x do
        for posy=positions['a'].y, positions['b'].y do
            for posz=positions['a'].z, positions['b'].z do
                local posit = {x=posx, y=posy, z=posz, stackpos=253}
         
                -- (I am) the player in room, teleport me out.
                if getTopCreature(posit).uid == cid then
                    doTeleportThing(cid, kickPos)
                    doSendMagicEffect(kickPos, 4)
                    return true
                end
       
                if isPlayer(getTopCreature(posit).uid) then
                    -- Player Exists in room
                    doPlayerSendTextMessage(cid, MESSAGE_EVENT_DEFAULT, "There's someone in the room! Please wait. ")
                    doSendMagicEffect(getCreaturePosition(cid), 2)
                    return true
                end
            end
        end
    end

    -- no player was found, teleport me in!
    doTeleportThing(cid, initPos)
    doSendMagicEffect(initPos, MAGIC_EFFECT_FIREATTACK)

    return true
end

Might be a bit more efficient this way.

If you wish to make it even more efficient: Let it go through the Z-axis first & construct the posit table once (before the for loops) and simply assign new x/y/z values.

    local posit = { x = 0, y = 0, z = 0, stackpos = 253 }
    for posz = positions['a'].z, positions['b'].z do
        posit.z = posz
        for posy = positions['a'].y, positions['b'].y do
            posit.y = posy
            for posx = positions['a'].x, positions['b'].x do
                posit.x = posx
            end
        end
    end

 

[ScorpionOT]

True that. Thx for the reminder, @Ninja.

 

[Night Wolf]

First of all this is not a benchmark. You are running it once and only for elements = 3.
The op code runs 3 times searching for players, efficiency is not a problem here unless he iterates over 5k players online to do so.

@ScorpionOT
The most cost you have is checking the values twice, storing the elements instead of acessing twice every table should increase it heavily.

 

[ScorpionOT]

@Night Wolf
Sorry, I didn't really comprehend your sentence on that one last bit, although I do believe @Ninja 's solution would make up for my mistake at the garbage collection/proper memory allocation instance. This is no ad hominem, but I will show you how your argument is completely wrong.

Regardless of it not being a benchmark, I just posted the proof of the code I composed being able to run smoother and faster than the one the poster previously had put up, as it did. Regardless of him just wanting to check 3 SQM, he did mention wanting to check a room (which if I understand gramatically, is a composition of a N-dimensional space [or altenatively, a matrix of n-vectors belonging to a specific coordinate system], which I adapted the code to, more appropriately).

I am not trying to say your argument is not valid because of the things you pointed out, although the poster is clearly asking for code efficiency, so I guess that would contradict your saying of "efficiency is not a problem". I do believe codes should be as efficient as they come, always, of course, depending on your course of action. Mind you this if a free forum and we're able to decide how we play things out.

Anyway, take it or leave it, all of your opinions are somewhat irrelevant seeing how the poster specifically asked for code efficiency and nobody but I had been able to respond to him with a properly formatted and composed code.

 

[Night Wolf]

I really want to understand why people at otland have this urge to always try to impress. You don't even know what he wants, he just posted a code and asked about efficiency and you're clearly misleading him.
I totally agree you should always do things as best as you can but you wrote so many texts and pasted so many links that honestly makes me think you're really trying to prove yourself when you clearly missed the whole point of the topic.

As your own link states:

(i.e https://www.lua.org/gems/sample.pdf).

In Lua, as in any other programming language, we should always follow the two maxims of program optimization:
Rule #1: Don’t do it.
Rule #2: Don’t do it yet. (for experts only)

You didn't even understood the first rule!!

You look like those douches who argue that you should always use ++i for optimal efficiency, but the truth is that wasting 1 sec to correct i++ to ++i will waste you more time than all the executions of all the for loops you'll write in your life. Do you understand it now?

What I said in my last line is clearly the only optimization that you should do, but unfortunately it seems that you spent too much time on the wrong side of the problem:

1. local posit = { x = 0, y = 0, z = 0, stackpos = 253 }
2. for posz = positions['a'].z, positions['b'].z do
3. posit.z = posz
4. for posy = positions['a'].y, positions['b'].y do
5. posit.y = posy
6. for posx = positions['a'].x, positions['b'].x do
7. posit.x = posx
8. end
9. end
10. end

should be:

local posit = {x = 0, y = 0, z = 0, stackpos = 253}
local vc_a, vc_b = positions['a'], positions['b']
    for posz = vc_a.z, vc.b.z do
        posit.z = posz
        for posy = vc_a.y, vc.b.y do
            posit.y = posy
            for posx = vc_a.x, vc.b.x do
                posit.x = posx
            end
        end
    end

this way you'll reduce the number of calls to the table significally.

But then again: It's too soon to talk about this kinda of optimization because it will reduce a problem of 0,00000005s to 0,00000004s, which means nothing. Also we could make a better approach to the problem resolution if we know in details why he's checking this part:

1. -- (I am) the player in room, teleport me out.
2. if getTopCreature(posit).uid == cid then
3. doTeleportThing(cid, kickPos)
4. doSendMagicEffect(kickPos, 4)
5. return true
6. end

Beyond all that, we should also use repeat until in the place of for because he have two return statements that will broke the loop and that is bad because the compilator separates memory to process this loop and when we break it we cause a small delay to the next process because the pipeline goes to a place to process the return statement. To explain this further it would require me to draw some images of the compilator pipeline itself, because it's not a quick explanation. I guess you'll have to trust me in this one, or you can say I don't know what I'm talking about and read the Knuth for yourself.

Lastly: Think before writing code, we already have too much monkeys who know how to code. Talking to the client and understand his necessities is the best way to start the optimal solution.
I've been working with programming for about 10 years now and programmers nowadays are so anxious to finish things fastly. Don't be one more idiot out there.
I hope you do not take this personal, this is the knowledge I'm sharing.

 

[Night Wolf]

Apologies taken and I think I should apologize too. I've never liked how people are presumptuous here at otland (not necessarily saying it was your case, I just understood that way) and I really dislike being underestimated. Sorry too.

As for the optimization: my advice is still the same, let's him answer my first question. When we have the full understanding of what he wants and why he did it that way then we can begin talking about optimizations. Nevertheless, the code is very punctual, small-consuming and well written and therefore doesn't really need any effort in being optimized at all, this is just for educational purposes.

 

[tetra20]

How comes 3 fors is more efficient than just one?

Efficiency of first code is O(n), Efficiency of yours is O(n^3) which is way worse.

Both Scripts Written are O(1) Time

An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input.

The Area searched each time is of constant size, unbounded by the input size

And even if you have 5000 players in the server,it wouldn't even lag the slightest

 

[Night Wolf]

The Area searched each time is of constant size, unbounded by the input size

The arguing was about if he changed the number of the sqms to be checked. The algorithm it's O(n) since it checks are linearly correspondent to the number of elements in positions table.

Scorpion's version is also O(n) despite using 3 fors, that's because he uses a different match in the fors to iterate over possible positions described as values of a tridimensional vector: x, y and z
Mathematically, there's no way to do this with less than O(n) comparisons (unless we cheat a little but will cost of O(n) memory, it's a simple tradeoff afterall) so we are really on the maximum efficiency here.

The only room for improvement are the hidden factors, that's because when we say it's O(n) we ignore the hidden constant and take into account only the most consuming part of the algorithm.
Also, we can do some tricks to speed up our computations, but the number of executions will remains proportional to O(n) no matter what (again, unless we store every player entered in a table and then only iterate it's table, this way we reduce the problem to O(p) where p it's in the worst case = n but never bigger (considering you can't have more than one player per sqm -> I'm considering this because the OP script consider this as well.).

 

[tetra20]

The arguing was about if he changed the number of the sqms to be checked. The algorithm it's O(n) since it checks are linearly correspondent to the number of elements in positions table.

Scorpion's version is also O(n) despite using 3 fors, that's because he uses a different match in the fors to iterate over possible positions described as values of a tridimensional vector: x, y and z
Mathematically, there's no way to do this with less than O(n) comparisons (unless we cheat a little but will cost of O(n) memory, it's a simple tradeoff afterall) so we are really on the maximum efficiency here.

The only room for improvement are the hidden factors, that's because when we say it's O(n) we ignore the hidden constant and take into account only the most consuming part of the algorithm.
Also, we can do some tricks to speed up our computations, but the number of executions will remains proportional to O(n) no matter what (again, unless we store every player entered in a table and then only iterate it's table, this way we reduce the problem to O(p) where p it's in the worst case = n but never bigger (considering you can't have more than one player per sqm -> I'm considering this because the OP script consider this as well.).

You Dashed away from the point..I said it's O(1) not O(n) Because the size of the array is of constant size.. it's not changing ,each time it's the same operations done for every player,it does N operations but the Time complexity is O(1) and so it the Memory it's O(1)

For example,this little code:

for i = 1,100 do
    print(i)
end

Or this Code:

local n = Any_number
if(n < 11)
   //do things
  return true
end
for i = 1,n do
   print(i)
end

This is not O(n), it's O(1),the same goes the script above,the size of array is constant,it doesn't change(unless you changed it manually,and that is not related to complexity)

The operations done is as you said N operations

 

[Night Wolf]

I'm not dashing away, read my previous comment. Literally the first line explain the discussion:
The arguing was about if he changed the number of the sqms to be checked. The algorithm it's O(n) since it checks are linearly correspondent to the number of elements in positions table.

You can't say an algorithm is O(1) because the input is fixed in a value, otherwise all we had to do is use fixed inputs for everything and then we'll have optimal execution time in all of them xD.

to further explain, imagine a square 5x5.

You can iterates it like this:

local y = 1
for i = 1, 5*5 do
if i > 5 then
y = math.ceil(i/5)
end
x = (i % 5) + 1
print(x, y)
end

or like this:

for i = 1, 5 do
for j = 1, 5 do
print(i, j)
end
end

That's not because we have two fors that the first one is better. It's not because of the size of as well. You gotta take into account the computations and how they grow accordingly to the size of the square.

I understand what you tried to say, but the algorithms works using the position table as input, and it's linearly bounded to it. That's why it's O(n) and not O(1)

 

[tetra20]

What you said is true
I'll just give my perspective on this matter(cause it's confusing somehow xD)

Let this be our code:

for i = 1, 5 do
for j = 1, 5 do
print(i, j)
end
end

Say we run this code t times
So in total,we do around t*25 operation..Can you say this is an O(25t)? Ofcourse not,because constant are removed from Big-O
It becomes O(t) where t is the number of times we ran the code
But if we did this(i changed 5 to n)

for i = 1, n do
for j = 1, n do
print(i, j)
end
end

and we ran this code t times too
it becomes O(t*n^2) Which is what you said above
So from the first code
Let t = 1
It becomes O(25)

 

[Night Wolf]

It's a common mistake, but look:
in the square problem, let's be 'n' the side of the square. You have a O(n*n) on the first algorithm and O(n^2) on the second, which is basically the same thing.

In your codes, the print will be executed 25 times. The big O notation doesn't care about this. It wants to know how proportional the execution growth would be based on the size of the loops.
If you write it as n, then you have O(n*n), and changing n = 5 and getting 25 times just prove the correctness of this method.

You're doing the process from the end to the beggining when it should be looked the other way around:
1- Check how the execution grows based on the inputs
2- Find the formula
3- Apply for specific cases to check the result.

I highly suggest you to watch some videos or try some competition problems about the matter: Time Complexity - InterviewBit
Understanding time complexity is a difficult task and very easy to do it wrongly. It takes a lot of study to learn how to acknowledge some of them.

 

[tetra20]

Still Something doesn't make sense to me..

When our code had only constant numbers

for i = 1, 5 do
for j = 1, 5 do
print(i, j)
end
end

You said it was O(N^2)
So What would an O(1) look like..?
In other words,Can you provide me a code including a loop and you call it O(1)?