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

Question

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

我的理解是，如果Clojure能够确定可以使用原语，它就可以使用原语。对clojure.lang.Numbers中的方法的调用似乎表明它在这里没有使用原语。

如果我强制循环变量为int，它会正确地报告递归参数不是原生的。如果我也强迫它们，代码会再次工作，但同样很慢。我唯一的猜测是(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实现，您可以在参数向量中使用^long来提示coll-size --或者可能只是在函数体的开头询问向量的大小(这是一个非常快速、恒定的操作)，用(bit-shift-right ... 1)替换(quot ... 2)调用，并使用未经检查的数学方法计算索引。通过一些额外的调整，二进制搜索可以写成如下：

(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似乎比这个java-binsearch多花了大约25%的时间。

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

要删除它，可以键入hint the 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))
            ))))))

可以理解，将第10行上的自动装箱连接到coll-size参数是很困难的，因为它依次经过cnt、high-idx和mid-ixd，依此类推，所以我通常通过键入提示来处理这些问题，直到我找到使警告消失的提示，然后删除提示，只要它们一直存在