clojure中的二进制搜索(实现/性能)

Question

我写了一个二进制搜索函数作为一个更大的程序的一部分,但它似乎比它应该慢,并且分析显示了很多对clojure.lang.Numbers方法的调用.

我的理解是,当Clojure可以确定它可以这样做时,它可以使用原语.对clojure.lang.Numbers中方法的调用似乎表明它不是在这里使用原语.

如果我将循环变量强制为int,它会正确地抱怨recur参数不是原始的.如果我也强迫那些,代码再次起作用,但又很慢.我唯一的猜测是(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,搜索会更快,除非集合包含bigint,在这种情况下它会破坏.

至于你的纯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.