Re: filter an array in place

[Drake Wilson <drake@...>]

Quoth Romulo <romuloab@gmail.com>, on 2011-01-14 12:52:13 -0200:
> 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).

I don't have a version at LuaSnippets.  I posted a function to the
list.  If someone reposted it at LuaSnippets, that's news to me.

Running your LuaSnippets version with:

  local n = 0
  local r = {1,2,3,4,5,6,7,8,9}
  local t = setmetatable({}, {__index = r, __newindex = function(_,k,v) r[k]=v; n=n+1 end})
  remove_in_place(t, function(x) return x==9 end)
  print(n)

and with that #array in the beginning replaced with len(array), where:

  function len(t) local i = 0; repeat i = i + 1 until t[i] == nil; return i-1 end

says it does 9 assignments, not 1.  (Verifying that len does no
assignments is left as an exercise.)

I also still think that (a) such an optimization isn't worth it even
for in-place operation unless you expect most of your lists to have a
large pile of unfiltered elements at the beginning, and (b) if I
wanted to do that "optimization" I would do it with an initial scan
loop rather than crazifying the entire inner loop with edge detection
(and quite possibly slowing it down in the process anyway).

> 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.

If you're using a proxy table your invocation of the length operator
probably fails, incidentally, per the above.  (I don't believe __len
works on tables in 5.1.)

> --rb

That's also the last I'm going to say on this topic.

   ---> Drake Wilson