[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:15:24 +0100
No, using table.remove repeatedly is at least n*log(n) if not n^2.
On Fri, Jan 14, 2011 at 3:07 PM, Drake Wilson <email@example.com> wrote:
> Quoth Romulo <firstname.lastname@example.org>, on 2011-01-14 11:55:23 -0200:
>> I've submitted a variant of your code to LuaSnippets. My function
>> removes a element according to the predicated, instead of keeping it.
>> The function is optimized to avoid unnecessary table assignments by
>> finding contiguous slots "marked" as to-be-kept.
> That doesn't look like an optimization at all. As far as I know it's
> going to be N table assignments either way, with N being the length of
> the original list. The only 'optimization' one could do in that
> regard while preserving ordering would be to skip kept items at the
> very beginning, and I'd hardly consider that worth the complexity in
>>  http://snippets.luacode.org/snippets/Filter_a_table_in-place_2_120
> ---> Drake Wilson