Re: filter an array in place

[Axel Kittenberger <axkibe@...>]

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 <drake@begriffli.ch> wrote:
> Quoth Romulo <romuloab@gmail.com>, on 2011-01-14 11:55:23 -0200:
>> I've submitted a variant of your code to LuaSnippets[1]. 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
> general.
>
>> --rb
>>
>> [1] http://snippets.luacode.org/snippets/Filter_a_table_in-place_2_120
>
>   ---> Drake Wilson
>
>