[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Deleting all elements from a table
- From: Jürgen Hötzel <juergen@...>
- Date: Thu, 14 Sep 2006 19:01:59 +0200
On Thu, Sep 14, 2006 at 12:34:23PM -0400, Leo Razoumov wrote:
> On 9/13/06, Roberto Ierusalimschy <firstname.lastname@example.org> 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
> 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.