Re: filter an array in place

[Drake Wilson <drake@...>]

Quoth Axel Kittenberger <axkibe@gmail.com>, on 2011-01-14 15:15:24 +0100:
> No, using table.remove repeatedly is at least n*log(n) if not n^2.

Sorry, but what are you talking about?

The function I posted does not use table.remove.  It filters in-place
by copying individual items and then setting nils, and is O(N) in the
length of the original list.

Romulo said he submitted a variant of that function to LuaSnippets
which was "optimized to avoid unnecessary table assignments" by doing
a bunch of contiguous slots at once, and I said that I didn't think
this was an optimization because the number of table assignments was
ultimately the same.  Eir snippet also does not use table.remove.

I mentioned in my earlier post that I didn't like the table.remove
solutions much because they tended to be O(N^2).

What is your above sentence referencing?

   ---> Drake Wilson