lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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 <> wrote:
> Quoth Romulo <>, 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]
>   ---> Drake Wilson