Clojure look up performance vector vs set

Question

I have a small collection of sorted items less than 50 I frequently check if a particular item is in the collection or not,

this,

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (filter (fn [[k]] (= k 15)) a))))

takes 10 ms if I use a set however,

(time
 (let [a (sorted-set 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)]
   (dotimes [i 100000]
   (a 15))))

It always takes at least twice as much. What I do not understand is, set is supposed to be optimized for look ups why is filter faster?

Answer 1

Filter is lazy. Since you're not evaluating the result of (filter (fn [[k]] (= k 15)) a) it doesn't really do anything but make a lazy sequence.

In fact, (fn [[k]] (= k 15)) isn't even correct but you don't see that because it's not evaluated.

(let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
     (filter (fn [[k]] (= k 15)) a))
=> java.lang.UnsupportedOperationException: nth not supported on this type: Integer
    [Thrown class java.lang.RuntimeException]

You want something like

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (some (fn [k] (= k 15)) a))))

"Elapsed time: 173.689 msecs"
nil

Instead of the incorrect:

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (filter (fn [[k]] (= k 15)) a))))

"Elapsed time: 33.852 msecs"
nil

Answer 2

filter is a lazy function. Try adding first in order to force the evaluation of the lazy sequence generated by the filter function. There is also a minor error in your anonymous function:

(time
 (let [a [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]]
   (dotimes [i 100000]
     (first (filter (fn [k] (= k 15)) a)))))

"Elapsed time: 126.659769 msecs"

sorted set:

(time
 (let [a (sorted-set 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)]
   (dotimes [i 100000]
   (a 15))))
"Elapsed time: 19.467465 msecs"

Hope that makes sence.