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

 

[ScorpionOT]

Wow. I'm impressed after all the shitposting I did this turned into an actual educational argument. Kudos to both of you, and sorry if I offended anyone. I was purely trying to find my match, or a teaching therein.

 

[tetra20]

Wow. I'm impressed after all the shitposting I did this turned into an actual educational argument. Kudos to both of you, and sorry if I offended anyone. I was purely trying to find my match, or a teaching therein.

Shitposting is the road to glory(If you never shitposted,you never tried and never had the courage to make a mistake)

 

[Summ]

Regarding the actual topic:
1) You can use 2 different action ids. One for the lever outside of the area and one for the lever inside of the area. This saves you from checking every single tile for the player.
2) Looping an array of positions (like you do it) should be faster than looping over the coordinates and constructing the positions to check for.
3) You may consider using getSpectators (especially for larger areas). This function would even find stacked players (on a single tile) if you need that (e.g. for teleporting all players out of an area).
4) You can use #positions instead of table.maxn(positions)


Regarding the time complexity topic:
The amount of positions that have to be checked is constant, it does not depend on the input. Therefore, the time complexity is O(1).

 

[Night Wolf]

We say it to be O(1) when no matter the input, the number of executions will always be the same.
a simply print("hi") can be said to be a O(1) because it's just a singular computation.

You can have it tied to a loop, but the number of executions won't be O(1), it would rely on the bounds of the loop.
But for some specific cases, you can say it is O(1) when the loop is a very insignificant part of the algorithm. Let's say you have something that orders an array and then return the 5 first digits of it.
This may as well be a top 5 algorithm.

Remember, big O notation is only relevant when you are considering a very large number as input. If you have 10 players and want return the first one, we won't be able to say the part that returns the 5 firsts are irrelevant.

So: Considering 100k players in your database, the order would require at least O(n^log(n)) for a comparison algorithm. It's more or less 1,7kk computations. After this, will have to do 5 computations.
Scale is really important here, after all, would you bother to improve 1,7 billion comparisons or 5?
For this case we can assume the + c constant attached as 0. It's not that it has only 1 execution, but the value will always be so insignificant near the other one that we can simply ignore it and call it O(1) (as constant).

But remember, this isn't constant thought.

imagine it written like this:

function getHighscores(players, tops)
table.sort(players) -- O(#players * log2(#players))
local tb = {}
for i = 1, tops do
tb[#tb + 1] = players
end
return tb
end


it relies not only from the number of players in the table players, but also from the number of tops we want. It doesn't matter if we remove the parameter tops and put it hardcoded in the for, the algorithm is still dependent of it.

 

[ScorpionOT]

Regarding the actual topic:
1) You can use 2 different action ids. One for the lever outside of the area and one for the lever inside of the area. This saves you from checking every single tile for the player.
2) Looping an array of positions (like you do it) should be faster than looping over the coordinates and constructing the positions to check for.
3) You may consider using getSpectators (especially for larger areas). This function would even find stacked players (on a single tile) if you need that (e.g. for teleporting all players out of an area).
4) You can use #positions instead of table.maxn(positions)


Regarding the time complexity topic:
The amount of positions that have to be checked is constant, it does not depending on the input. Therefore, the time complexity is O(1).

>2) Looping an array of positions (like you do it) should be faster than looping over the coordinates and constructing the positions to check for.
Care to elaborate why on this? Even if the "benchmark" I did returned faster and less memory consuming than his? I mean, obviously taking into account all the pointers left through the thread. Oh, also:

5) Save a globalstorage to confirm the lever has already been pulled and there is somebody inside. It depends on the scenario, but this is usually when the area is too big to constantly check, and it could be set to -1 (or nil) onDeath from player or when the other lever is pulled.

 

[tetra20]

Scale is really important here, after all, would you bother to improve 1,7 billion comparisons or 5?
For this case we can assume the + c constant attached as 0. It's not that it has only 1 execution, but the value will always be so insignificant near the other one that we can simply ignore it and call it O(1) (as constant).

This part is true,As an example of what you said.. Modulo operation where it depends on the number of digits O(m),it can be brushed as O(1) since most of number dealt with have m <= 18..

Not sure about the rest honestly..

 

[Night Wolf]

Regarding the actual topic:
1) You can use 2 different action ids. One for the lever outside of the area and one for the lever inside of the area. This saves you from checking every single tile for the player.
2) Looping an array of positions (like you do it) should be faster than looping over the coordinates and constructing the positions to check for.
3) You may consider using getSpectators (especially for larger areas). This function would even find stacked players (on a single tile) if you need that (e.g. for teleporting all players out of an area).
4) You can use #positions instead of table.maxn(positions)


Regarding the time complexity topic:
The amount of positions that have to be checked is constant, it does not depending on the input. Therefore, the time complexity is O(1).

1) Yes, this would reduce half of the work.
2) Absolutely right, it's the same case of processing in the loop and pre processing earlier.
3) I wouldn't recommend, as far as I remember this function checks for stackpos too, increasing the time a little bit.
4) Always use the language operator unless your table have nil values, otherwise #table will return the last consecutive index

The time complexity depends on table position, it is O(n) and not O(1)

 

[peXu]

Shitposting is the road to glory(If you never shitposted,you never tried and never had the courage to make a mistake)

Don't confuse shitposting with simply being wrong. Being overconfident, arrogant and rude towards others are some of the worst junior programmer traits to deal with.

Regarding the actual topic:
Regarding the time complexity topic:
The amount of positions that have to be checked is constant, it does not depending on the input. Therefore, the time complexity is O(1).

As @Night Wolf said - I believe we should consider the positions table as the input when calculating the cost of this function. After all, it's a function which purpose is to check some area for existing players, it would only seem logical to me to take that area as an input. Also, this whole discussion is a nice example of premature optimization.

 

[tetra20]

Don't confuse shitposting with simply being wrong. Being overconfident, arrogant and rude towards others are some of the worst junior programmer traits to deal with.

As shitposting,i just meant trying to help..
Being rude or overconfident,that's another story,which is a bad thing..

 

[ScorpionOT]

Don't confuse shitposting with simply being wrong. Being overconfident, arrogant and rude towards others are some of the worst junior programmer traits to deal with.

Not disagreeing with overconfidence, arrogant and rude being unruly in a learning environment, specially when its stated in such a way to come off as a figure of authority when one clearly possesses no such role to functionally bear a demeanor of sorts. That being said, I still don't understand why you guys think checking for the predefined static positions (even though it's a matrix of just three vectors) is more efficient than dynamically checking for the same predefined static positions (even though the references and pointers to said positions should preferably be declared in an efficient manner too), although accessed as a subspace or an area of limits (do correct me if I am wrong).

Please provide us with literature or practical examples in the day-to-day developing. I did see @Night Wolf book reference and I plan on checking it out later.

Also, this whole discussion is a nice example of premature optimization.

Also, this. Isn't this really what this whole thread is about? I do believe as long as OTServ distributions keep using a heavily modular system with no sort of optimization inherent to its unfolding, or perhaps a sustainable definition of progress embedded to its infrastructure, it will keep being inefficient regardless of whatever code optimizations in function to time or aspect of development you wish to presume. Again, please do correct me if I am wrong (which I probably am).

 

[Night Wolf]

You can read several algorithms books such as The Algorithm Design Manual, The Art of the computer programming (Knuth 1, 2, 3, 4 and I guess there's a five now too) but it will be too in depth.
I would recommend for a starting reader to check out the Cracking the Code Interview which goes through many algorithms and explains techniques of optimizations.

After some experience and practice, you'll notice that it all comes down to the tradeoff: RAM x Memory. If you have to calcule the vector in the meantime, it makes sense that it would take some time more than just reading the positions written.

In one way we have our ram working to generate the positions, in the other they are already there. Ofc for this kind of example this makes no change at all, but make a script that does this two ways for a 10k+ vector and things will start to be more interesting.