[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Clean the table
- From: Enrico Colombini <erix@...>
- Date: Wed, 06 Feb 2002 10:53:57 +0100
"Marcos E. Wurzius" <marcos@novanis.com.br> wrote Tue, 29 Jan 2002:
>I have a table:
>t={ 1,2,3,4,...9999,10000; a="new", b="old"}
>
>Which is the best and faster way to clean
>the lfieldlist "[1]...[10000]" from the table?
>
>I do:
>
>for i=1,getn(t) do tremove(t,i) end
>
>but it's very slow.
Apart from the other suggested solutions, you should remove array elements
backwards:
for i = 1, getn(t) do tremove(t, getn(t)) end
or, better and faster:
for i = 1, getn(t) do tremove(t) end
The difference in running time *is* significant: adding or removing from
the beginning of an array appears to run in O(n) time, while acting on the
end of the array seems to run in constant time (disclaimer: just my
hurriedly-run tests).
So your loop takes O(n^2) time if run forwards, O(n) time if run backwards;
on my machine, for 10000 elements I get approx. 12 seconds against 0.05
seconds.
Enrico