Re: filter an array in place

[Kristofer Karlsson <kristofer.karlsson@...>]

If that's a problem, the patch should be easy:
for i = 1,#t do

     local v = t[i]

     if predicate(v) then
                     if j ~= i then


          t[j] = v
                     end


        j = j + 1

     end

  end

For the use case you said, where only the last element is removed, there should be no redundant table sets.

On Fri, Jan 14, 2011 at 3:52 PM, Romulo <romuloab@gmail.com> wrote:

On Fri, Jan 14, 2011 at 12:07, 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.

Consider the case where you want to remove only the last slot. In my
version, there will be no assigment at all (just the nils at the end).
In your version at LuaSnippets, you will assign all slots from 1 to
n-1 (thus, "removing" the last slot).

The problem with assignment isn't really a problem as long as
assignment is cheap. If you are using a proxy table, or if there are
collateral effects on it, then it might not be the case.


--rb