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 

Answer 2

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" 

希望这是SENCE。