Re: filter an array in place

[Eike Decker <zet23t@...>]

>> Is there any other more elegant way?
>
> process the list in reverse.
>
> for index=#tab,1,-1 do
>  local val = tab[index]
>   if val == "a" then -- could be any other complex condition
>     table.remove(tab, index)
>   end
> end
>
>
> --
> Robert G. Jakabosky
>
(I've fixed the local value)

I also think that this is the most elegant and most efficient
solution. The case of total removal would be O(n), same as no removal.
The worst case is probably an array where the first half or quarter
(or sqrt(#)?) of the array is to be removed. This is btw. also the
reason why I would like to have the table.remove function to be
extended: table.remove (table [, pos]) to table.remove (table [,
pos,[n]]). So I would like to have it extended that way, that one can
remove multiple elements at on go. I think this change wouldn't be a
problem since it should be fully backward compatible (unless someone
is passing more than supposed to that function).
The filter function would look like that then:

function filter (filter)
local n = 0
for i=#t,1,-1 do
  local v = t[i]
  if filter(v) then
    n = n  + 1
  elseif n>0 then
    table.remove(t,i,n)
  end
end
if n > 0 then table.remove(t,1,n) end
end
---
If table.remove was implemented this way, copying the array values
around in case of removal of large chunks would be much more efficient
(I don't have to tell you). This would then change the worst case to a
version where the first half of the array is to be filtered in each
2nd case - so the worst case would be still twice as efficient as with
the table.remove implementation right now. And the average case would
be improved probably even more.


Cheers,
Eike