Geek Answers Handbook

Clojure search performance vector and set

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

(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. I don’t understand that the set should be optimized for searching, why is the filter faster?

+5
source share
2 answers

The filter is lazy. Since you are not evaluating the result (filter (fn [[k]] (= k 15)) a), it does nothing but lazy consistency.

In fact, it’s (fn [[k]] (= k 15))not entirely correct, but you don’t see it because it is not being 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]

Do 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 wrong one:

(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
+11

filter - . first, , filter. :

(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"

:

(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"

, .

+3

More articles:


All Articles