[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: filter an array in place
- From: Axel Kittenberger <axkibe@...>
- Date: Fri, 14 Jan 2011 15:37:00 +0100
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" <email@example.com>:
> Quoth Axel Kittenberger <firstname.lastname@example.org>, 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