Queues (was Re: Lua design : why no lists ?)

[Mark Hamburg <mhamburg@...>]

The one downside to the PiL approach to queues is that, based on my
understanding of the array optimization in Lua, it eventually moves out of
the array optimized range. (Okay. It also eventually overflows the integer
capabilities of double but that takes a really long time.) Moving out of the
array optimized range incurs both speed and space costs.

Another option if amortized constant time for insertion and deletion from a
queue is sufficient is to use two Lua tables as stacks. One maintains an in
stack and an out stack. When the out stack is empty, you pop all of the
elements from the in stack one at a time and push them on the out stack.
Every element will be pushed twice and popped twice while making it through
the queue and hence the since those are constant time operations the
amortized time is constant. The flip from in stack to out stack, however,
takes time proportional to the number of items in the queue and hence any
given dequeue operation may not take constant time.

But the PiL approach is probably simpler and avoids creating as many tables.

Mark

P.S. Actually, table.insert and table.remove are not constant time
operations since they depend on table.getn which depends to some extent on
the number of tables with an n field. That, however, is a hash lookup so the
cost grows very slowly.

on 9/15/04 4:30 AM, Enrico Colombini at erix@erix.it wrote:

> On Tuesday 14 September 2004 18:43, Asko Kauppi wrote:
>> There are, as you know, 'table.insert' and 'table.remove'.
> 
> Also, if I remember well, Roberto's book ("Programming in Lua") shows how to
> make fast lists or queues with open-ended arrays. 'table.insert' and
> 'table.remove' can be quite inefficient if done at the start of a large
> array.
> [by "array" I mean "numerically-indexed table]
> 
> Enrico
>