Re: Deleting all elements from a table

[Jürgen Hötzel <juergen@...>]

On Thu, Sep 14, 2006 at 12:34:23PM -0400, Leo Razoumov wrote:
> On 9/13/06, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
> >> local k= next(t)
> >> while k ~= nil do
> >>  t[k]= nil
> >>  k= next(t)
> >> end
> >
> >It may be worth remembering that the above loop is quadratic in time.
> >
> >-- Roberto
> >
> 
> Roberto,
> I am sorry but I think this loop is linear in time (number of elements
> in table 't').
> next(t) is equivalent to next(t,nil) and returns the head element of
> the table in constant time. The loop itself is linear in time. Overall
> it is O(t) -- linear time.

next(t) returns the first non-nil value. If you remove the first N
elements, next(t) has to loop over the first N nil values before it returns
the next element (i assume storage in a array). I recommend reading "The
implementation of Lua 5.0": great. 

Jürgen