Clojure cercare prestazioni vettore vs set

Question

Ho una piccola collezione di oggetti ordinati meno di 50 Mi capita spesso di controllare se un particolare elemento è nella collezione o no,

questo,

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

prende 10 ms se tuttavia utilizzo un set,

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

Richiede sempre almeno il doppio. Quello che non capisco è che il set dovrebbe essere ottimizzato per le ricerche perché il filtro è più veloce?

Answer 1

Il filtro è pigro. Dato che non stai valutando il risultato di (filter (fn [[k]] (= k 15)) a), in realtà non fa altro che fare una sequenza lenta.

Infatti, (fn [[k]] (= k 15)) non è nemmeno corretto ma non lo si vede perché non viene valutato.

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

si desidera qualcosa di simile

(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 

Al posto della non corretta:

(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 è una funzione pigro. Prova ad aggiungere first per forzare la valutazione della sequenza lazy generata dalla funzione filter. C'è anche un piccolo errore nella funzione anonima:

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

set ordinato:

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

speranza che rende sence.