Re: filter an array in place
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: filter an array in place
- From: Drake Wilson <drake@...>
- Date: 2011年1月14日 07:22:30 -0700
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