Búsqueda binaria en clojure (implementación/rendimiento)

Question

Escribí una función de búsqueda binaria como parte de un programa más grande, pero parece ser más lenta de lo que debería y el perfil muestra muchas llamadas a métodos en clojure.lang.Numbers .

Según entiendo, Clojure puede usar primitivas cuando puede determinar que puede hacerlo. Las llamadas a los métodos en clojure.lang.Numbers parecen indicar que no está utilizando primitivas aquí.

Si fuerzo las variables de bucle a las entradas, se queja correctamente de que los argumentos recurrentes no son primitivos. Si los coacciono también, el código funciona nuevamente, pero de nuevo es lento. Mi única conjetura es que (quot (+ low-idx high-idx) 2) no está produciendo un primitivo, pero no estoy seguro de dónde ir desde aquí.

Este es mi primer programa en Clojure, así que siéntase libre de decirme si hay formas más limpias/funcionales/Clojure de hacer algo.

(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

En primer lugar, se puede utilizar la aplicación binario de búsqueda proporcionada por java.util.Collections:

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

Si se salta el compare, la búsqueda será más rápido todavía, a menos que la colección incluye bigints, en cuyo caso voy a romper.

En cuanto a su implementación Clojure pura, puede insinuar coll-size con ^long en el vector de parámetros - o simplemente pedir el tamaño del vector al principio del cuerpo de la función (es una operación de tiempo constante y muy rápida), reemplazar la llamada (quot ... 2) con (bit-shift-right ... 1) y usa matemáticas sin verificar para los cálculos del índice. Con algunos ajustes adicionales una búsqueda binaria se podría escribir de la siguiente manera:

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

Esto sigue siendo notablemente más lento que la variante de Java:

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

binary-search como se definió anteriormente parece tener aproximadamente un 25% más de tiempo que esto java-binsearch.

Answer 2

en Clojure 1.2.x solo puede forzar las variables locales y no pueden cruzar llamadas de funciones. que comienza en Clojure 1.3.0 Clojure puede usar números primitivos en llamadas a funciones pero no a través de funciones de orden superior como map.

si está utilizando clojure 1.3.0+, entonces debería ser capaz de lograr esto utilizando el tipo insinúa

como con cualquier problema de optimización clojure el primer paso es activar la (set! *warn-on-reflection* true) a continuación, añadir toques de tipo hasta que ya no se queja

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=> 

eliminar esta se puede escribir insinuar el argumento coll de tamaño

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

es comprensiblemente difícil conectar la auto-boxing en la línea 10 al parámetro coll de tamaño, ya que pasa a través de cnt luego high-idx y luego mid-ixd y así sucesivamente, por lo que generalmente me acerco a estos problemas por tipo, insinuándolo todo hasta que encuentro el que hace que desaparezcan las advertencias, luego borro sugerencias siempre y cuando permanezcan fuera