fetburner.core

コアダンプ

Deforestation で強連結成分分解を改善する

 この記事は ML Advent Calendar 2020 の10日目の記事です.

 本記事では,強連結成分分解を行うアルゴリズムの一種である Kosaraju のアルゴリズムに対して deforestation を施し,トポロジカルソートの結果をリストとして保持することなく計算できることを観察します.

12/11 Kosaraju のアルゴリズムを勘違いしていたので実装を修正しました.根本的な勘違いのせいで TaPL 27章みたいな事になっており,厳しい…

強連結成分分解とは?

 皆さん強連結成分分解はご存じでしょうか?これは読んで字のごとく,有向グラフを強連結成分——任意の2点間に有向路が存在する極大な部分グラフ——に分割する操作で,分解してできた強連結成分を縮約すると DAG が得られる嬉しさがあります.

 ML Advent Calendar を読むような人々にはコンパイラの実装にも使われると言うと嬉しさが伝わるのではないでしょうか?例えば,以下のような相互再帰を考えてみましょう.

let rec s x y z = (x z) (y z)
    and k x y = x
    and i x = s k k x

元ネタの SKI コンビネータ計算的に i は恒等関数になるはずで,気持ちとしては型チェックが通ってほしいのですが,これは型エラーになってしまいます. 何しろ多相再帰に型を付ける時は,まず関数自身1を単相として型を付けてから,その後で型変数を量化しますからね2. この例だと let rec を使わずに書いてやれば型チェックが通るんですが,下の例のようにコンパイラには let rec を取り除くのが難しいプログラムもある訳です.

let rec alternate x y = Seq.cons x (alternate' x y)
    and alternate' x y = Seq.cons y (alternate' x y)

Haskell みたいに全部の定義が相互再帰的な言語で上手く多相型を付けようと思うと,できるだけ小さな let rec に分割したい気持ちになりますが,この操作がまさに強連結成分分解な訳ですね. 相互再帰的に定義された変数を頂点,変数の依存関係を辺としたグラフに対して強連結成分分解を計算すると,最低限 let rec で纏めるべき変数のグループと,それらグループをどんな順番に let rec で定義すれば良いかが分かります.

Kosaraju のアルゴリズム

 強連結成分分解を行うアルゴリズムの一種です.その内容は単純明快,一旦グラフにトポロジカルソートを施した後,依存されてるやつから順番に DFS を行い,まだ追加されていない頂点を取れるだけ取ってきたものを強連結成分とする訳ですね.12/11 追記 これは僕の勘違いで,依存しているやつから順番に逆グラフで DFSが必要でした.トポロジカルソートも DFS で求められるので,全ての頂点に対して DFS を2回ずつ行えばそれで事足ります.3

 まぁこればっかりは実装を見た方が早いですね.簡単のために,頂点を 0 から n-1 までの int として,DFS で頂点に訪れたかどうかを bool の配列で扱い,頂点を受け取って隣接する頂点のリストを返す関数で隣接リストを表現しています.

(* 12/11 正しいプログラムに修正 *)

(* dfs es is_visited v vs
    隣接リスト es で与えられるグラフに対して DFS を行い,
    頂点 v とその依存している頂点(間接的に依存しているものも含める)を
    トポロジカルソートしたリストを `vs` の前に連結したリストを返す *)
let rec dfs :
  (int -> int list) ->
  bool array ->
  int ->
  int list ->
  int list
= fun es is_visited v vs ->
  if is_visited.(v)
  then vs
  (* v が依存している頂点を全て追加した後で v を追加する *)
  else (is_visited.(v) <- true; v :: List.fold_right (dfs es is_visited) (es v) vs)

(* sort n es
    隣接リスト es で与えられる n 頂点のグラフに対してトポロジカルソートを行い,
    依存関係順に並べた頂点のリストを返す *)
let sort :
  int ->
  (int -> int list) ->
  int list
= fun n es ->
  let is_visited = Array.make n false in
  List.fold_right (dfs es is_visited) (List.init n Fun.id) []

(* scc n es es'
    グラフの隣接リストが es で,
    逆グラフの隣接リストが es' で与えられる n 頂点のグラフに対して強連結成分分解を施した結果を返す *)
let scc :
  int ->
  (int -> int list) ->
  (int -> int list) ->
  int list list
= fun n es es' ->
  let is_visited = Array.make n false in
  List.fold_left (fun vss v ->
    if is_visited.(v)
    then vss
    else dfs es is_visited v [] :: vss) [] (sort n es');;

(* 使用例 *)
scc 7 
  (function
  | 0 -> [1]
  | 1 -> [2]
  | 2 -> [0; 3]
  | 3 -> [4]
  | 4 -> [3; 5; 6]
  | 5 -> []
  | 6 -> [])
  (function
  | 0 -> [2]
  | 1 -> [0]
  | 2 -> [1]
  | 3 -> [2; 4]
  | 4 -> [3]
  | 5 -> [4]
  | 6 -> [4]);;
(* - : int list list = [[2; 0; 1]; [4; 3]; [6]; [5]] *)

Deforestation

 ところで,先ほどの Kosaraju のアルゴリズムの実装ではトポロジカルソートした結果をリストとして生成していましたが,この手の途中計算で必要になったデータ構造を作らないようにして,メモリ使用量を減らせないものでしょうか?

 その糸口は List.fold_right がどのような関数かを観察することで見えてきます.標準ライブラリの実装を見てみましょう.

let rec fold_right f l accu =
  match l with
    [] -> accu
  | a::l -> f a (fold_right f l accu)

どうやら,引数で与えられたリストが空リスト [] の場合は accu を,コンス a :: l の場合は f a (fold_right f l accu) を返しています. ここで,List.fold_right f (List.cons 1 (List.cons 2 (List.cons 3 (List.cons 4 [])))) accu を計算すると f 1 (f 2 (f 3 (f 4 accu))) になると考えると,何かが見えてきませんか?4 そう,List.fold_right f l accu とは l のコンスを f に,空リストを accu に置き換えたものに過ぎないのです.

 では,トポロジカルソートする時に空リストにコンスを繰り返してリストを作り,後でその空リストとコンスを置き換えるなら,最初から空リストとコンスを適当なものに置き換えて計算できないでしょうか? この目論見は上手くいって,途中計算に必要なメモリ使用量を削減することができます.極力元のコードの形を保つために,ファンクタを使ったその効率的な実装をお見せしましょう.

12/11 追記 Kosaraju のアルゴリズムを勘違いしていて,List.fold_right ではなく List.fold_left が必要になったのでこの辺りの議論は前提から覆ってしまいました.一応 List.fold_right に直せなくもないけど,クロージャのせいで結局頂点数に比例したメモリを使ってしまうのでアレ.

一応その実装もここに残しておきます.

module F
  (* トポロジカルソートソートの結果を作る時に使う,リストの実装  *)
  (L : sig
    type t
    val nil : t
    val cons : int -> t -> t
  end)
= struct
  (* dfs es is_visited v vs
      隣接リスト es で与えられるグラフに対して DFS を行い,
      頂点 v とその依存している頂点(間接的に依存しているものも含める)を
      トポロジカルソートしたリストを `vs` の前に連結したリストを返す *)
  let rec dfs :
    (int -> int list) ->
    bool array ->
    int ->
    L.t ->
    L.t
  = fun es is_visited v vs ->
    if is_visited.(v)
    then vs
    (* v が依存している頂点を全て追加した後で v を追加する *)
    else (is_visited.(v) <- true; L.cons v (List.fold_right (dfs es is_visited) (es v) vs))

  (* sort n es
      隣接リスト es で与えられる n 頂点のグラフに対してトポロジカルソートを行い,
      依存関係順に並べた頂点のリストを返す *)
  let sort :
    int ->
    (int -> int list) ->
    L.t
  = fun n es ->
    let is_visited = Array.make n false in
    List.fold_right (dfs es is_visited) (List.init n Fun.id) L.nil
end

(* 普通に頂点のリストを返してくれるトポロジカルソートの実装 *)
module M = F
  (struct
    type t = int list
    let nil = []
    let cons = List.cons
  end)

(* scc n es es'
    グラフの隣接リストが es で,
    逆グラフの隣接リストが es' で与えられる n 頂点のグラフに対して強連結成分分解を施した結果を返す *)
let scc :
  int ->
  (int -> int list) ->
  (int -> int list) ->
  int list list
= fun n es es' ->
  let is_visited = Array.make n false in
  let module N = F
    (struct
      type t = int list list -> int list list
      type elt = int
      let nil = Fun.id
      let cons v k l = k @@
        if is_visited.(v)
        then l
        else M.dfs es is_visited v [] :: l
    end) in
  N.sort n es' [];;

(* 使用例 *)
scc 7 
  (function
  | 0 -> [1]
  | 1 -> [2]
  | 2 -> [0; 3]
  | 3 -> [4]
  | 4 -> [3; 5; 6]
  | 5 -> []
  | 6 -> [])
  (function
  | 0 -> [2]
  | 1 -> [0]
  | 2 -> [1]
  | 3 -> [2; 4]
  | 4 -> [3]
  | 5 -> [4]
  | 6 -> [4]);;
(* - : int list list = [[2; 0; 1]; [4; 3]; [6]; [5]] *)

 本記事の例は foldr/build と呼ばれる最適化に対応していて,GHC のようなコンパイラでは自動的に行ってくれるのだから驚きです. とはいえ,OCaml でプログラムを書く時も,データ構造を抽象化しておけばお相伴に与ることができる時もあるでしょう. 僕が実際に競プロで使っているライブラリは,リストに限らず配列やグラフの実装についてもファンクタで抽象化しています.

まとめ

 本記事では,強連結成分分解を行うアルゴリズムの一種である Kosaraju のアルゴリズムに対して deforestation を施し,トポロジカルソートの結果をリストとして保持することなく計算できることを観察しましたOCamlHaskell とは評価戦略が異なるのですが,GHC で行われている最適化が参考になることもあります.ライブラリを書く時はとりあえずデータ構造をファンクタとかで抽象化しておけば,今回のように計算途中でリスト等を作らない形にできるかもしれません.

結局 DFS を2回行うのは変わってないのですが,まぁこれは適当にインライン展開してプログラム運算を行えば何とかなると思います.Tarjan のアルゴリズムになるだけのような気もしないでもないですが.


  1. この例では sk,およびi

  2. 多相再帰型推論は決定不能なので

  3. 気の利いた図の一つでもあれば良かったんですが,時間が無いので省略します.多分強連結成分分解で検索すれば良い感じのが出るかと.

  4. List.cons x xsx :: xs を返す関数で,List.cons 1 (List.cons 2 (List.cons 3 (List.cons 4 [])))[1; 2; 3; 4] を仰々しく(リストとは空リストにコンスを繰り返して作られるものと強調して)書いたにすぎません