Re: filter an array in place

[Axel Kittenberger <axkibe@...>]

Sorry my fault. I thought you  ment no optimization to the table.remove() solutions. Instead or coming up with tricky algorithms I'd really ask the OP if inplace is such a hard requirement. Out of place makes the code a simple one-two liner and is O(n)
Am 14.01.2011 15:22 schrieb "Drake Wilson" <drake@begriffli.ch>:
> 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
>