[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: filter an array in place
- From: Drake Wilson <drake@...>
- Date: Fri, 14 Jan 2011 07:22:30 -0700
Quoth Axel Kittenberger <email@example.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