Color Wars

[lurker]

And it will skip one of two adjacent items, and still crash if the last one is removed.

[zwzsg]

It's still O(n┬▓)

How so? It's just a single "for" loop from N to 1. Looks O(n) to me.

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.

[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.)

[zwzsg]

Ok, thanks for the explanation. (So the previous was like O(n^3) ;p ?)

[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