Clojure mirar hacia arriba vector rendimiento vs conjunto

Question

tengo una pequeña colección de elementos ordenados de menos de 50 que con frecuencia comprobar si un artículo particular está en la colección o no,

esto,

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

toma 10 ms si uso un conjunto sin embargo,

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

Siempre lleva al menos el doble. Lo que no entiendo es que el set se supone que está optimizado para búsquedas, ¿por qué es más rápido el filtro?

Answer 1

El filtro es flojo. Como no está evaluando el resultado de (filter (fn [[k]] (= k 15)) a), realmente no hace nada más que hacer una secuencia perezosa.

De hecho, (fn [[k]] (= k 15)) ni siquiera es correcto pero no lo ve porque no se ha evaluado.

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

quieres algo como

(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 

En lugar de la incorrecta:

(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 es una función perezoso. Intente agregar first para forzar la evaluación de la secuencia diferida generada por la función filter. También hay un pequeño error en su función anónima:

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

conjunto ordenado:

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

Esperanza que hace SENCE.