Ricerca binaria in clojure (implementazione/prestazioni)

Question

Ho scritto una funzione di ricerca binaria come parte di un programma più grande, ma sembra essere più lenta di quanto dovrebbe essere e la profilazione mostra molte chiamate ai metodi in clojure.lang.Numbers .

La mia comprensione è che Clojure può usare le primitive quando può determinare che può farlo. Le chiamate ai metodi in clojure.lang.Numbers sembrano indicare che non sta usando le primitive qui.

Se le variabili di ciclo vengono forzate in ints, si lamenta correttamente che gli argomenti ricorrenti non sono primitivi. Se ho forzato anche quelli, il codice funziona di nuovo, ma di nuovo è lento. La mia unica ipotesi è che (quot (+ low-idx high-idx) 2) non stia producendo un primitivo ma non sono sicuro di dove andare da qui.

Questo è il mio primo programma in Clojure quindi sentitevi liberi di farmi sapere se ci sono più modi puliti/funzionali/Clojure per fare qualcosa.

(defn binary-search 
    [coll coll-size target] 
    (let [cnt (dec coll-size)] 
    (loop [low-idx 0 high-idx cnt] 
     (if (> low-idx high-idx) 
     nil 
     (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)] 
      (cond 
      (= mid-val target) mid-idx 
      (< mid-val target) (recur (inc mid-idx) high-idx) 
      (> mid-val target) (recur low-idx (dec mid-idx)) 
      )))))) 

(defn binary-search-perf-test 
    [test-size] 
    (do 
    (let [test-set (vec (range 1 (inc test-size))) test-set-size (count test-set)] 
     (time (count (map #(binary-search2 test-set test-set-size %) test-set))) 
    ))) 

Answer 1

Prima di tutto, è possibile utilizzare l'applicazione di ricerca binaria fornita da java.util.Collections:

(java.util.Collections/binarySearch [0 1 2 3] 2 compare) 
; => 2 

Se si salta il compare, la ricerca sarà ancora più veloce, a meno che la collezione comprende bigints, nel qual caso romperà.

Per quanto riguarda l'implementazione pura Clojure, si può accennare coll-size con ^long nel parametro vettore - o forse solo chiedere per la dimensione del vettore all'inizio del corpo della funzione (che è un'operazione di tempo molto veloce, costante), sostituisce la chiamata (quot ... 2) con (bit-shift-right ... 1) e utilizzare la matematica non selezionata per i calcoli dell'indice. Con alcune modifiche aggiuntive una ricerca binaria potrebbe essere scritto come segue:

(defn binary-search 
    "Finds earliest occurrence of x in xs (a vector) using binary search." 
    ([xs x] 
    (loop [l 0 h (unchecked-dec (count xs))] 
     (if (<= h (inc l)) 
     (cond 
      (== x (xs l)) l 
      (== x (xs h)) h 
      :else nil) 
     (let [m (unchecked-add l (bit-shift-right (unchecked-subtract h l) 1))] 
      (if (< (xs m) x) 
      (recur (unchecked-inc m) h) 
      (recur l m))))))) 

Questo è ancora notevolmente più lento rispetto alla variante di Java:

(defn java-binsearch [xs x] 
    (java.util.Collections/binarySearch xs x compare)) 

binary-search come sopra definito sembra prendere circa il 25% in più di tempo di quanto questo java-binsearch.

Answer 2

in Clojure 1.2.x è possibile forzare solo variabili locali e non possono attraversare chiamate di funzioni. a partire da Clojure 1.3.0 Clojure può utilizzare numeri primitivi per le chiamate di funzione, ma non per le funzioni di ordine superiore come map.

se si utilizza clojure 1.3.0+ allora si dovrebbe essere in grado di realizzare questo tipo Uso dei suggerimenti

come per qualsiasi problema di ottimizzazione clojure il primo passo è quello di trasformare il (set! *warn-on-reflection* true) quindi aggiungere tipo suggerimenti fino a quando non è più si lamenta.

user=> (set! *warn-on-reflection* true)           
true 
user=> (defn binary-search 
    [coll coll-size target] 
    (let [cnt (dec coll-size)] 
    (loop [low-idx 0 high-idx cnt] 
     (if (> low-idx high-idx) 
     nil 
     (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)] 
      (cond 
      (= mid-val target) mid-idx 
      (< mid-val target) (recur (inc mid-idx) high-idx) 
      (> mid-val target) (recur low-idx (dec mid-idx)) 
      )))))) 
NO_SOURCE_FILE:23 recur arg for primitive local: low_idx is not matching primitive, 
had: Object, needed: long 
Auto-boxing loop arg: low-idx 
#'user/binary-search 
user=> 

Per rimuovere questo è possibile digitare accennare l'argomento Coll-size

(defn binary-search 
    [coll ^long coll-size target] 
    (let [cnt (dec coll-size)] 
    (loop [low-idx 0 high-idx cnt] 
     (if (> low-idx high-idx) 
     nil 
     (let [mid-idx (quot (+ low-idx high-idx) 2) mid-val (coll mid-idx)] 
      (cond 
      (= mid-val target) mid-idx 
      (< mid-val target) (recur (inc mid-idx) high-idx) 
      (> mid-val target) (recur low-idx (dec mid-idx)) 
      )))))) 

è comprensibilmente difficile collegare l'auto-boxing sulla linea 10 al parametro Coll-size, perché passa attraverso cnt quindi high-idx quindi mid-ixd e così via, quindi generalmente mi avvicino a questi problemi digitando tutto finché non trovo quello che fa scomparire gli avvertimenti, quindi rimuovi i suggerimenti fino a quando non vengono rimossi