Re: Map and filter without intermediate tables

[Geoff Leyland <geoff_leyland@...>]

On 7/06/2012, at 7:27 PM, steve donovan wrote:

> On Thu, Jun 7, 2012 at 5:39 AM, Geoff Leyland <geoff_leyland@fastmail.fm> wrote:
>> I did, and it was slower than using intermediate tables (and more complicated.  It did save some memory though).  Is it a dead-end idea, or is it that my implementation [1] is brain dead?
> 
> Well, ipairs is _always_ going to be slower than numeric-for, so I'd
> expect any performance-conscious person to override __len as well.

I don't know how to compute in advance the length of the result of filtering a table with an arbitrary filter, so I can't always rely on __len.  You can use __len if you're using intermediate tables, which is another reason they might be better.

In any case, a quick and dirty benchmark says that luajit can run pairs(t) as fast as for i = 1, #t (which surprised me), and writing pairs out long-hand:

local i = 1
while true do
  local v = t[i]
  if not v then break end
  -- to something with i and v
  i = i + 1
end

fares very well.  In any case, I think neither imap nor ifilter in the example use the built-in ipairs iterator.

> This is then definitely going to be faster:
> 
> function imapi (f,t)
>  local i,n = 0,#t
>  return function()
>    i = i + 1
>    if i > n then return end
>    return i,f(t[i])
>  end
> end

It would be nice, but I don't think I can make it work in general.

> (Note that LuaJIT has a Lua-5.2 compatibility mode which allows nice
> things like __pairs and __len)

But as I said to Dirk, they don't actually make much difference (unless you can educate me on the filter and __len problem)