Print Page - (length my-list)

Title: (length my-list) - O(n) or O(1) ?
Post by: itistoday on December 03, 2007, 07:00:06 PM

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

Title: Re: (length my-list) - O(n) or O(1) ?
Post by: Cyril on December 04, 2007, 03:29:33 AM

~~Quote from: "itistoday"~~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?

Title:
Post by: Lutz on December 04, 2007, 04:46:01 AM

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

Title:
Post by: itistoday on December 04, 2007, 07:01:32 AM

Thanks guys!

~~Quote from: "Lutz"~~For 'last' the optimization was never done, but is trivial to add for 9.2.9.

That would be just hunky-dory! :-D

Title: Re: (length my-list) - O(n) or O(1) ?
Post by: Cyril on December 04, 2007, 12:46:37 PM

~~Quote from: "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.

Title: Re: (length my-list) - O(n) or O(1) ?
Post by: itistoday on December 04, 2007, 02:07:12 PM

~~Quote from: "Cyril"~~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?

newLISP Fan Club

Forum => newLISP newS => Topic started by: itistoday on December 03, 2007, 07:00:06 PM