M. Adams 等の R6RS equal? の find 手続き

M. D. Adams, R. K. Dybvig, Efficient Nondestructive Equality Checking for Trees and Graphs, 2008 (以下、 ADAMS2008 と略す) の find 手続きについて。 結論は先送りで、 気になった点を備忘録として残しておきます。

SRFI-85 で提案されて、 R6RS Scheme が採用した循環グラフ対応型 equal? を作るには決定性状態遷移機械 (DFA) の等価性検査が必要になります。 DFA の等価性検査と言えば union-find 算法を使うのですけど、 こいつは遅いので、 Adams 等は乱択による改良案を提唱しています。

ところで、 union-find の find 手続きには数通りの書き方があり、 Adams 等は、 親リンクを祖母リンクへすげかえていく方式を採用しています。

⇒ ADAMS2008 Figure 4.

 (define (find b)
  (let ((n (unbox b)))
   (if (box? n)
    (let loop ((b b) (n n))
     (let ((nn (unbox n)))
      (if (box? nn)
       (begin (set-box! b nn) (loop n nn))
       n)))
    b)))

Adams 等の実装では、 素集合を表す木の親を指すリンクを box オブジェクトにしています。 find 手続きに渡す引数は、 その box オブジェクトで、 リンクを辿って根を探して返します。 根の box には数値で木の序数が入っています。

他に良く使われているのを目にする find 手続きの方式は、 親リンクを根へのリンクにすげかえるやりかたです。

 (define (find b)
  (let ((n (unbox b)))
   (if (box? n)
    (let ((r (find n)))
     (set-box! b r)
     r)
    b)))

Adams 等版と比較するため、 これを 2 段の末尾再帰ループにします。 その際、 後段ループの実行順を再帰呼び出し版の逆にしても結果は変わりませんし、 その方が途中経路を覚えておかずにすみます。

 (define (find b)
  (let ((n (unbox b)))
   (if (box? n)
    (let pass1 ((r n) (n (unbox n)))
     (if (box? n)
      (pass1 n (unbox n))
      (let pass2 ((b b) (n (unbox b)))
       (if (box? n)
        (begin (set-box! b r) (pass2 n (unbox n)))
        r))))
    b)))

素朴な union-find 算法では、 find のどちらの方式を使っても、 アッカーマン関数のオーダーで動くことが知られています。 問題は、 Adams 等の改良案の場合で、 乱択で union-find 手続きの実行回数を減らします。 ということは、 find 手続きのループを一段に減らす方が全体としての性能が改善する可能性がありえます。 それを踏まえて、 あえて find 手続きを祖母リンクへの差し替え版を採用している可能性があります。 逆に、 乱択でまびいてしまっているため、 祖母リンクへの差し替えでは根へのリンクへの到達が遅れ、 ループを二段にして一気に根へすげかえる方が性能が良くなるかもしれません。 それとも、 ひょっとすると、 素朴な場合と同様、 find のどの方式でも同じように性能が良くなる可能性もあります。 もちろん、 それどころか find 関数ではなくハッシュ表へのエントリ追加が律速部かもしれません。 もっとも、 ADAMS2008 のベンチマークの素朴な union-find は遅くはなっているものの、 データの規模よりもデータの構造への依存の方が大きいようにも読めるので、 ハッシュ表へのエントリ追加は律速部ではない可能性はあります。