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。