Head holding in Clojure

Question

After reading the paragraph about preserving the head in “Clojure Programming” (page 98), I could not understand what was happening in the split-with example. I tried experimenting with repl, but that made me more confused.

 (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) "Elapsed time: 1910.401711 msecs" [12 9999988] (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count b) (count a)])) "Elapsed time: 3580.473787 msecs" [9999988 12] (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count b)])) "Elapsed time: 3516.70982 msecs" [9999988] 

As you can see from the last example, if I do not calculate a , the time grows somehow. I guess I missed something, but what?

Answer 1

Count - O (1). That is why your measurements are not dependent on this.

Answer 2

The count function is O (1) for Counted collections, which includes vectors and lists.

On the other hand, sequences are not taken into account , which makes count O (n) for them. The important part here is that the take-while and drop-while functions return sequences. The fact that they are also lazy is not the main factor here.

Answer 3

When using time a as a reference, run the tests many times to get an accurate result.

 user> (defn example2 [] (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) #'user/example2 user> (dorun (take 1000 (repeatedly example2))) nil user> (time (example2)) "Elapsed time: 614.4 msecs" [12 9999988] 

I blame variance at runtime because the hotspot compiler has not yet fully opposed the classes created. Several times I ran the first and second examples and got mixed relative results:

run the example twice:

 autotestbed.core> (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) "Elapsed time: 929.681423 msecs" [12 9999988] autotestbed.core> (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) "Elapsed time: 887.81269 msecs" [12 9999988] 

then run the example two times:

 core> (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) "Elapsed time: 3838.751561 msecs" [12 9999988] core> (time (let [r (range 1e7) a (take-while #(< % 12) r) b (drop-while #(< % 12) r)] [(count a) (count b)])) "Elapsed time: 970.397078 msecs" [12 9999988] 

sometiems, second example just as fast

Answer 4

The binding in the let form is complete, even we do not use this value.

 (let [x (println "Side effect")] 1) 

The code above prints "Side Effect" and returns 1.

All three examples use the same binding in the let form, so I don't see any difference here. By the way, on my machine all your fragments took about the same time.

The real difference when trying something like this:

 (time (let [r (range 2e7) a (take 100 r) b (drop 100 r)] [(count a)])) "Elapsed time: 0.128304 msecs" [100] (time (let [r (range 2e7) a (take 100 r) b (drop 100 r)] [(count b)])) "Elapsed time: 3807.591342 msecs" [19999900] 

Due to the fact that b and a are lazy sequences, count works in O(n) time. But in the first example, we do not calculate the counter for b, so it works almost immediately.

Answer 5

the time it shows is completely system dependent .... if you restart it, it will show some elapsed time for each execution