The Author Online Book Forums are Moving

The Author Online Book Forums will soon redirect to Manning's liveBook and liveVideo. All book forum content will migrate to liveBook's discussion forum and all video forum content will migrate to liveVideo. Log in to liveBook or liveVideo with your Manning credentials to join the discussion!

Thank you for your engagement in the AoF over the years! We look forward to offering you a more enhanced forum experience.

294119 (38) [Avatar] Offline
#1
The following statement is made:

Finally, you can count the number of items in a list in constant time using the count function:

Isn't the time to count the number of items in a list O(n), not O(1)?

I thought that an advantage of using vectors instead of lists was the time to count items.

Francis Avila (16) [Avatar] Offline
#2
In Clojure, lists (true PersistentLists which are introduced in this section, not generic sequences) keep track of their length so they implement count in constant time. The tail of a list can never change so its length can never change; so the count of a list is essentially cached inside it.

However, lists do not provide constant-time member access, which is probably what you are thinking of. Vectors provide (amortized) O(1) access to their members, but lists still only provide O(n) access.

Under the covers, Clojure uses the clojure.lang.Counted interface for data structures countable in O(1). Every "real" data structure (maps, lists, vectors) implements it, but lazy sequences do not. In particular, it is impossible to count the length of a lazy sequence without realizing it, which is where your O(n) (or worse, non terminating!) behavior comes back in.
294119 (38) [Avatar] Offline
#3
Thank you for a very thorough response to my question!