There is a interface 'Counted' that a lot of Clojure data structures implement to indicate that they provide O(1) for (count).
Thanks, Stu On Fri, Mar 13, 2009 at 4:59 AM, Christophe Grand <christo...@cgrand.net>wrote: > > Christian Vest Hansen a écrit : > > I think that count is O(n) for lists, no? > > > > Count is O(1) for lists but O(n) for a chain of conses. > > Clojure > user=> (let [l (apply list (range 100000))] (time (dotimes [_ 1000000] > (count l)))) > "Elapsed time: 169.710116 msecs" > nil > user=> (let [l (apply list (range 400000))] (time (dotimes [_ 1000000] > (count l)))) > "Elapsed time: 167.664046 msecs" > nil > user=> (let [l (reduce #(cons %2 %1) nil (range 100000))] (time (dotimes > [_ 100] (count l)))) > "Elapsed time: 662.121862 msecs" > nil > user=> (let [l (reduce #(cons %2 %1) nil (range 1000000))] (time > (dotimes [_ 100] (count l)))) > "Elapsed time: 5316.110567 msecs" > nil > > > -- > Professional: http://cgrand.net/ (fr) > On Clojure: http://clj-me.blogspot.com/ (en) > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
