Clojure查找性能向量vs集

Question

我有一小部分小于50的分类物品我经常检查特定物品是否在集合中,

这个,

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

如果我使用一套,需要10毫秒,

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

它总是需要至少两倍.我不明白的是,set应该针对查找进行优化,为什么过滤更快？

Answer 1

过滤器是懒惰的.因为你没有评估(filter (fn [[k]] (= k 15)) a)它的结果, 所以除了做一个懒惰的序列之外什么都不做.

事实上, (fn [[k]] (= k 15))甚至不正确,但你没有看到它,因为它没有被评估.

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

你想要的东西

(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

而不是错误的:

(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