Бинарный поиск в clojure (реализация / исполнение)

Question

Я написал бинарную функцию поиска как часть более крупной программы, но она кажется медленнее, чем должна быть, и профилирование показывает много вызовов методов в clojure.lang.Numbers.

Насколько я понимаю, Clojure может использовать примитивы, когда он может определить, что он может это сделать.Вызовы методов в clojure.lang.Numbers, похоже, указывают на то, что здесь не используются примитивы.

Если я приведу переменные цикла к целочисленным значениям, он будет жаловаться на то, что возвращаемые аргументы не являются примитивными.Если я приведу их в действие, код снова заработает, но опять-таки он будет медленным.Мое единственное предположение, что (quot (+ low-idx high-idx) 2) не производит примитив, но я не уверен, куда идти дальше.

Это моя первая программа в Clojure, поэтому не стесняйтесь сообщать мне, если есть более чистые/ функциональный / Clojure способы сделать что-то.

(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

Прежде всего, вы можете использовать реализацию двоичного поиска, предоставленную java.util.Collections:

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

Если вы пропустите compare, поиск будет еще быстрее, если коллекция не содержит bigints,в этом случае он сломается.

Что касается вашей чистой реализации Clojure, вы можете намекнуть coll-size с ^long в векторе параметров - или, возможно, просто запросить размер вектора в началетело функции (это очень быстрая операция с постоянным временем), замените вызов (quot ... 2) на (bit-shift-right ... 1) и используйте непроверенную математику для вычисления индекса.С некоторыми дополнительными настройками бинарный поиск может быть записан следующим образом:

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

Это все еще заметно медленнее, чем вариант Java:

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

binary-search, как определено выше, кажется, занимаетпримерно на 25% больше времени, чем это java-binsearch.

Answer 2

в Clojure 1.2.x вы можете вызывать только локальные переменные, и они не могут пересекать вызовы функций. начиная с Clojure 1.3.0 Clojure может использовать примитивные числа при вызове функций, но не через функции высшего порядка, такие как map.

если вы используете clojure 1.3.0+, вы сможете выполнить это, используя подсказки типа

Как и при любой проблеме оптимизации clojure, первым шагом является включение (set! *warn-on-reflection* true), а затем добавление подсказок типа до тех пор, пока он больше не будет жаловаться.

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

, чтобы удалить это, вы можете напечатать подсказку аргумента размера колла

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

понятно, что соединить автобокс в строке 10 с параметром coll-size, потому что он проходит через cnt, high-idx, mid-ixd и т. Д., Поэтому я обычно подхожу к этим проблемам по типу намекая на все, пока я не найду тот, который заставляет предупреждения исчезнуть, затем удаляйте подсказки, пока они не исчезли