比較回数の少ない二分木探索

common lisp algorithm

今日、会社の同僚や先輩と、通常のものより比較回数が少なくてすむ二分木探索の実装方法や性能について、(以前見た or 書いた覚えはあるが忘れていたので)あれこれ話していた。
その結果、(一部は自分の中で)一応の結論を得たので、書いておく。
※ 以下に書いていることは、ちゃんと確認した訳ではないので不正確な可能性有り。特に、数値に関しては(僕が出した適当なものなので)鵜呑みにはしないこと。

二つの実装

まずは、オーソドックスだと思われる二分木探索の方法をWikipediaから引用する。

探索


1. ルートから手順を開始する。
2. 着目しているノードと目的の値を比較する。等しいか、着目ノードが存在しなければ終了。
3. 「目的の値 < 着目しているノード」なら左の子、「着目しているノード < 目的の値」なら右の子へ移って繰り返し。


探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。

http://ja.wikipedia.org/wiki/2%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8/


これをcommon lispで実装したのが、次のコード。

;; 二分木用の構造体: 二分木はリストとして表現する。
(defstruct (bin-tree (:type list))
  left value right)

;; オーソドックスな二分木探索
(defun bin-tree-search1 (key tree &optional (< #'<))
  (when tree
    (cond ((funcall < key (bin-tree-value tree))
           (bin-tree-search1 key (bin-tree-left tree) <))  ; keyは、ノードの値より小さい?
          ((funcall < (tree-key tree) key)
           (bin-tree-search1 key (bin-tree-right tree) <)) ; keyは、ノードの値より大きい?
          (t t))))                                         ; key == ノードの値

この関数では、探索が(成功か失敗かで)終了するまでの間に、探索パス上の各ノードに対して(大まかに云えば)平均して1.5回ずつ＜関数を呼び出している*1。


これに対して、比較回数が少ない(と思われる)実装方法は、以下の通り。

(defun bin-tree-search2 (key tree &optional (< #'<))
  (nlet self ((tree tree) (candidate most-negative-fixnum)) ; XXX: keyはfixnumと仮定
    (if (null tree)
        (not (funcall < candidate key)) ; 最後にkeyとcandidateを比較:  (= key candidate)と等価
      (if (funcall < key (bin-tree-value tree))     ; keyはノードの値より小さい?
          (self (bin-tree-left tree) candidate)                ; 小さい場合:     candidateを引き継ぐ。        ※ key != ノードの値なので
        (self (bin-tree-right tree) (bin-tree-value tree)))))) ; 小さくない場合: ノードの値をcandidateにする。※ key != candidateなので

この関数では、探索パス上の各ノードに対して＜関数を一回ずつ呼び出し、終端ノードに達した際に、もう一度＜関数を呼び出している。

比較回数

で、両者の比較回数(＜関数の呼び出し回数)だが、「前者:後者=1.5:1.0」くらいではないかというのが今日の結論(だった)。

概算に用いた式(一回の検索で要する比較回数の計算式)を書いてみると次のような感じになる。

  • -

bin-tree-search1: （（log(n)-0.5）*1.5*2+ log(n)*1.5*3）/2 = 1.5*log(n)-0.372
bin-tree-search2: log(n)+1
log(n): 木の高さ=探索パスの最大長。nは二分木の要素数+1。
※ なお、二分木は完全にバランスしていると仮定する。
※ また、入力の半分は不成功探索、もう半分は成功探索となり、キーは完全にランダムとする。

  • -


実際に試したみたのが、次のコード。
だいたい予想通りの結果となる。

;; 高さheightの完全二分木生成
(defun gen-complete-binary-tree (height)
  (nlet self ((height height) (num 0))
    (when (plusp height)
      (make-bin-tree :left  (self (1- height) (- num (expt 2 (- height 2))))
                     :value num
                     :right (self (1- height) (+ num (expt 2 (- height 2))))))))

> (gen-complete-binary-tree 3)
--> (((NIL -3 NIL) -2 (NIL -1 NIL)) 0 ((NIL 1 NIL) 2 (NIL 3 NIL)))

;; 高さ20の二分木
(defparameter *tree* (gen-complete-binary-tree 20))

;; bin-tree-search1の計時
>(time
  (let* ((cnt 0)
        (<-with-count (lambda (a b)
                        (incf cnt)
                        (< a b)))
        (size (length (flatten *tree*)))
        (rs (make-random-state)))
   (dotimes (i size)
     (bin-tree-search1 (- size (random (* size 2) rs)) *tree* <-with-count))
   cnt))
Evaluation took:
  0.717 seconds of real time
  0.716045 seconds of total run time (0.712045 user, 0.004000 system)
  [ Run times consist of 0.012 seconds GC time, and 0.705 seconds non-GC time. ]
  99.86% CPU
  2,274,074,536 processor cycles
  8,388,608 bytes consed
--> 30921953  ; この数は、生成される乱数によって変動する


;; bin-tree-search2の計時
>(time
  (let* ((cnt 0)
        (<-with-count (lambda (a b)
                        (incf cnt)
                        (< a b)))
        (size (length (flatten *tree*)))
        (rs (make-random-state)))
   (dotimes (i size)
     (bin-tree-search1 (- size (random (* size 2) rs)) *tree* <-with-count))
   cnt))
Evaluation took:
  0.667 seconds of real time
  0.668042 seconds of total run time (0.656041 user, 0.012001 system)
  [ Run times consist of 0.032 seconds GC time, and 0.637 seconds non-GC time. ]
  100.15% CPU
  2,117,311,408 processor cycles
  8,388,608 bytes consed
--> 22020075  ; この数は、入力によらず一定


;; (/ bin-tree-search1 bin-tree-search2)
> (float (/ 30921953 22020075))
--> 1.404262   ; 差は、1.4倍程度

感想とか

最初の方は、「オーソドックスな方は、一つのノード辺りの比較回数は多いけど、成功探索の場合にパスが短くてすむから、結局あんまり変わらないかも」とか思ったりもしたのだが、結構大きな差があった。
何となく、成功探索は失敗探索に比べて速い、という印象があったのだが、(上で挙げた仮定のもとでは)二分木ではそれほどは違いがないようだ(全体の要素の半分が葉ノードにあるので、考えてみれば当たり前なのかもしれないが)。
実際の場面では、いろいろと条件が複雑になるので、上で挙げたのと全く同じ結果になることはないとは思うが、覚えておいても損はないだろう。
まあ、「実際の場面」で二分木探索を実装する機会はあまりなさそうだけれど。

*1:keyがノードの値より小さい場合は一回、それ以外の場合は二回呼び出す。二分木がバランスしていて、キーの入力がランダムだと仮定すれば、keyがノードの値より小さい場合と大きい場合が半々となるので、平均して1.5回

*2:成功探索時: 探索パスの最後でキーが一致する可能性と、それ以前に一致する可能性はだいたい半々なので、おおまかに考えると(log(n)+log(n)-1)/2 == log(n)-0.5番のノードで探索が成功終了する(ような気がする)。そして、それぞれのノードに対して平均1.5回ずつ比較を行うので、(log(n)-0.5)*1.5。... 正確な計算は面倒なのでパス。

*3:不成功探索時: 終端ノードまでのノードに対して、平均1.5回ずつ比較を行う。