Page 2 of 2
Re: Color Wars
Posted: 16 Jun 2009, 18:16
by lurker
And it will skip one of two adjacent items, and still crash if the last one is removed.
Re: Color Wars
Posted: 16 Jun 2009, 19:21
by zwzsg
KDR_11k wrote:It's still O(n┬▓)
How so? It's just a single "for" loop from N to 1. Looks O(n) to me.
lurker wrote:And it will skip one of two adjacent items, and still crash if the last one is removed.
Why does it skip adjacent item? When I was looping 1 to N, yes, it was skipping items (hence the repeat I had before), but now that I'm looping downard, I don't understand what would make it skip items. As for the crash, it didn't happen ingame (and the table does end up empty).
But I'm all ears for better replacment.
Re: Color Wars
Posted: 16 Jun 2009, 20:48
by Tobi
table.remove() is O(n) in general: it needs to shift all other elements to ensure there are no gaps in the array. So table.remove() in a loop over the same array is O(n^2).
(Unless you're only removing the last element of the array all the time.)
Re: Color Wars
Posted: 16 Jun 2009, 20:52
by zwzsg
Ok, thanks for the explanation. (So the previous was like O(n^3) ;p ?)
Re: Color Wars
Posted: 16 Jun 2009, 21:41
by lurker
I already started writing you something, but had to go away for a couple hours. It looked n^2 before to me. You're right, it won't error any more because you changed the loop direction; I was distracted by rewriting it for performance to really notice that.
Code: Select all
local removeBlocks = {}
local removeCount = 0
for k = 1,#ActiveBlocks do
if frame >= ActiveBlocks[k].Birthday then
removeCount = removeCount + 1
removeBlocks[removeCount] = k
end
end
if removeCount > 0 then
local moveTo = removeBlocks[1]
local moveFrom = moveTo
local removeIndex = 1
while moveFrom <= #ActiveBlocks do
if removeIndex <= removeCount then
while removeBlocks[removeIndex] == moveFrom do
removeIndex = removeIndex + 1
moveFrom = moveFrom + 1
end
activeBlocks[moveTo] = activeBlocks[moveFrom]
moveTo = moveTo + 1
moveFrom = moveFrom + 1
end
for k = moveTo,moveFrom do activeBlocks[k] = nil
end