Page 1 of 1
(length my-list) - O(n) or O(1) ?
Posted: Tue Dec 04, 2007 3:00 am
by itistoday
Does (length) calculate the size of a list by iterating through its elements or is there a value stored somewhere internally?
Re: (length my-list) - O(n) or O(1) ?
Posted: Tue Dec 04, 2007 11:29 am
by Cyril
itistoday wrote:Does (length) calculate the size of a list by iterating through its elements or is there a value stored somewhere internally?
I haven't look in C sources of newLISP, but direct timing reveals that answer is O(1). There is another wonder here: '(push elt lst -1)' works in a constant time. Therefore I believe that the pointer to the last element of a list is stored somewhere. But then '(last lst)' works in a linear time. Why? Maybe Lutz will explain?
Posted: Tue Dec 04, 2007 12:46 pm
by Lutz
You got it right Cyril, a pointer to the last element is stored in the list envelope to optimize appending a list. For 'last' the optimization was never done, but is trivial to add for 9.2.9.
Lutz
Posted: Tue Dec 04, 2007 3:01 pm
by itistoday
Thanks guys!
Lutz wrote:For 'last' the optimization was never done, but is trivial to add for 9.2.9.
That would be just hunky-dory! :-D
Re: (length my-list) - O(n) or O(1) ?
Posted: Tue Dec 04, 2007 8:46 pm
by Cyril
Cyril wrote:I haven't look in C sources of newLISP, but direct timing reveals that answer is O(1).
Oops! Wrong! It's
O(n)! Very, very evil typo. Sorry, folks. And nobody have corrected me. :-( But you should'n trust me, try it yourself:
Code: Select all
(setq x (sequence 1 (eval-string (main-args 2))))
(setq a (time-of-day))
(setq y (length x))
(setq b (time-of-day))
(println (- b a))
(exit)
This gives 380ms for 5000000 and 770ms for 10000000 on my system.
Re: (length my-list) - O(n) or O(1) ?
Posted: Tue Dec 04, 2007 10:07 pm
by itistoday
Cyril wrote:Oops! Wrong! It's O(n)! Very, very evil typo. Sorry, folks. And nobody have corrected me. :-(
Are you saying that's what I get for trusting you? ;)
Yeah. That's a problem I think... Lutz?