(length my-list) - O(n) or O(1) ?

[itistoday]

Does (length) calculate the size of a list by iterating through its elements or is there a value stored somewhere internally?

[Cyril]

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?

[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

[itistoday]

Thanks guys!

For 'last' the optimization was never done, but is trivial to add for 9.2.9.

That would be just hunky-dory! :-D

[Cyril]

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 Expand

(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.

[itistoday]

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?