第12章

接尾辞に順位を付ける

（やさしい版） Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）

どんな問題？

リストの要素それぞれに「順位（rank）」を付けることを考えます。順位とは「自分より小さい要素がいくつあるか」を表す数です。

具体例 rank [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]

先頭の 51 より小さい要素は 3 つ（38, 29, 38）→ 順位 3
29 より小さい要素は 0 個 → 順位 0
63 より小さい要素は 5 つ → 順位 5

同点の要素は同じ順位になります。ここでは 0 から数え始めています。

この章のテーマは、リスト自身ではなくリストの「接尾辞（tails）」に順位を付けることです。接尾辞とは、リストの途中から末尾までを切り取った断片のことです。

なぜ驚きなのか

長さ n のリスト自身に順位を付ける: Θ(n log n) でできる。
2つの接尾辞を辞書順で比べるだけで最悪 Θ(n) かかるので、素朴には接尾辞に順位を付けるのに Θ(n² log n) かかりそう。
ところが、実は Θ(n log n) で済む——リスト自身に順位を付けるのと同じ計算量！

「意外だけれど本当」というのがこの章の面白さです。

仕様

接尾辞（tails）とは

Haskell では、リストの接尾辞のことを tails と呼びます。ここでは空でない接尾辞だけを長い順に返す関数として定義します（標準ライブラリの tails は空リストも返すので、少し違います）。

tails :: [a] → [[a]] tails [ ] = [ ] tails xs = xs : tails (tail xs)

Dart // 空でない接尾辞だけを長い順に返す List<List<T>> tails<T>(List<T> xs) { final result = <List<T>>[]; for (var i = 0; i < xs.length; i++) { result.add(xs.sublist(i)); } return result; }

たとえば tails [3, 1, 4] は [[3, 1, 4], [1, 4], [4]] を返します。

順位付け rank の仕様

順位付け rank はそのまま次のように書けます。

rank :: Ord a ⇒ [a] → [Int] rank xs = map (λx → length (filter (< x) xs)) xs

Dart // 素朴版: 各要素について「自分より小さい要素の個数」を数える (O(n^2)) List<int> rankNaive<T extends Comparable<T>>(List<T> xs) { return [ for (final x in xs) xs.where((y) => y.compareTo(x) < 0).length, ]; }

これは長さ n のリストに対して素朴には Θ(n²) 手順ですが、後で Θ(n log n) に改善できます。

目的の関数 ranktails

目的は接尾辞に順位を付けることなので、単純に組み合わせて次のように仕様化します。

ranktails :: Ord a ⇒ [a] → [Int] ranktails = rank · tails

Dart // 仕様そのままの実装: 接尾辞のリストに rank を適用 // 接尾辞同士の比較は辞書順で行う List<int> ranktailsSpec<T extends Comparable<T>>(List<T> xs) { final ts = tails(xs); int cmpList(List<T> a, List<T> b) { final n = a.length < b.length ? a.length : b.length; for (var i = 0; i < n; i++) { final c = a[i].compareTo(b[i]); if (c != 0) return c; } return a.length - b.length; } return [ for (final t in ts) ts.where((u) => cmpList(u, t) < 0).length, ]; }

この章のゴール ranktails を Θ(n log n) 手順で実行できるように実装すること。

rank の性質

順序を保存するという性質

rank の一番大切な性質は「相対順序を保存する」ことです。つまり、rank xs さえ分かれば、xs の要素同士の大小関係はすべて分かります（要素そのものが何かは分からなくても）。

そこで、xs ≈ ys を「rank xs = rank ys」の意味に定めます。xs ≈ ys なら、両者の相対順序は同じです。次のような同値関係が成り立ちます。

xs ≈ zip xs xs　　および　　zip (zip xs ys) zs ≈ zip xs (zip ys zs)

rank · select · rank = rank · select

もう一つ大事な性質です。select :: [a] → [a] を、次を満たす関数とします。

(i) select xs の要素はすべて xs にも入っている。
(ii) 任意の f について select · map f = map f · select（select の選び方は要素の中身に依らない）。

このとき次が成り立ちます。

rank · select · rank = rank · select(12.1)

この式の使いどころ

select = id（そのまま返す関数）→ rank · rank = rank：一度順位を付けたリストにもう一度順位を付けても同じ。
select = tail → rank · tail · rank = rank · tail：先に順位を付けてから tail しても、順序関係は変わらない。

証明は本文では読者への練習問題として残されています。

refinement（精緻化）: 演算 ≪

順位付けを「別の順位付けで細かく分ける」ための演算 ≪ を、次のように定義します。「refined by」（〜で精緻化）と読みます。

xs ≪ ys = rank (zip xs ys)(12.2)

Dart // 演算 ≪ : (xs, ys) のペア列に順位を付ける // 比較はペア (辞書順) で行うので、ys が xs の同順位を細分する List<int> refine(List<int> xs, List<int> ys) { final pairs = [for (var i = 0; i < xs.length; i++) (xs[i], ys[i])]; int cmpPair((int, int) a, (int, int) b) { final c = a.$1.compareTo(b.$1); return c != 0 ? c : a.$2.compareTo(b.$2); } return [ for (final p in pairs) pairs.where((q) => cmpPair(q, p) < 0).length, ]; }

具体例 [3, 1, 3, 0, 1] ≪ [2, 0, 3, 4, 0] = [2, 1, 3, 0, 1]

左側の xs では 3 が2つ、1 が2つと同順位が重複していた。
右側の ys の値で「同順位のときの並び順」を決めると、同順位が分かれる場合がある。

この ≪ は結合的です。つまり (xs ≪ ys) ≪ zs = xs ≪ (ys ≪ zs)。証明は次のとおりです。

(xs ≪ ys) ≪ zs = {(12.2)} rank (zip (rank (zip xs ys)) zs) = {zip us vs ≈ zip (rank us) vs より} rank (zip (zip xs ys) zs) = {zip (zip xs ys) zs ≈ zip xs (zip ys zs) より} rank (zip xs (zip ys zs)) = {同様に} xs ≪ (ys ≪ zs)

大事な観察 xs の順位付けがすでに「全部違う数（＝ 0…n−1 の順列）」になっていれば、それ以上どんな ys で精緻化しても変わりません。順列になったら、そこが終着点です。

よりよいアルゴリズム

「先頭 k 文字」だけで順位付けする一般化

分割統治で tails を分ける手（tails (xs ⧺ ys) の分解）はうまくいきません。そこで別の方針として、ranktails を関数 rats に一般化します。

アイデアは、辞書順比較を「先頭 k 文字だけ」の比較に置き換えることです。xs <_k ys = take k xs < take k ys と定めて、次のように定義します。

rats k = rank · map (take k) · tails(12.3)

Dart // rats k xs : 各接尾辞の「先頭 k 文字」だけで順位を付ける List<int> rats<T extends Comparable<T>>(int k, List<T> xs) { final prefixes = [ for (final t in tails(xs)) t.sublist(0, t.length < k ? t.length : k), ]; int cmpList(List<T> a, List<T> b) { final n = a.length < b.length ? a.length : b.length; for (var i = 0; i < n; i++) { final c = a[i].compareTo(b[i]); if (c != 0) return c; } return a.length - b.length; } return [ for (final p in prefixes) prefixes.where((q) => cmpList(q, p) < 0).length, ]; }

rats と ranktails の関係 ranktails xs = rats (length xs) xs。つまり rats は ranktails の一般化。名前は rank と tails を縮めたもので、計算式が短くなるので便利。

速さのカギとなる性質

次の性質が ranktails を速くするカギです。

rats (2∗k) xs = rats k xs ≪ shiftBy k (rats k xs)(12.4)

この式と shiftBy の定義は後で証明します。ポイントを言葉で説明すると：

xs ≈ map (take 1) (tails xs) なので、rats 1 = rank。
(12.4) を使えば rats 1 → rats 2 → rats 4 → …… と、見る文字数を倍々に増やしていける。
順位付けが順列になった時点で終了。

初期アルゴリズム

ranktails = applyUntil isperm rerankings · rank rerankings = map rerank (iterate (∗2) 1) rerank k rs = rs ≪ shiftBy k rs

Dart // 初期アルゴリズム: 一度だけ入力を rank し、以降は整数リストの上で // k = 1, 2, 4, 8, ... と再順位付けを繰り返す List<int> ranktailsIter<T extends Comparable<T>>(List<T> xs) { var rs = rankNaive(xs); var k = 1; while (!isperm(rs)) { rs = rerank(k, rs); k *= 2; } return rs; } List<int> rerank(int k, List<int> rs) => refine(rs, shiftBy(k, rs));

補助関数はそれぞれ次のとおりです。

applyUntil :: (a → Bool) → [a → a] → a → a applyUntil p (f : fs) x = if p x then x else applyUntil p fs (f x)

Dart // 述語 p が真になるまで関数列 fs を順に適用していく A applyUntil<A>(bool Function(A) p, Iterable<A Function(A)> fs, A x) { var current = x; final it = fs.iterator; while (!p(current) && it.moveNext()) { current = it.current(current); } return current; }

順位付けが順列かどうかを判定する isperm は、Haskell の配列を使って線形時間で書けます。¹

isperm :: [Int] → Bool isperm is = and (elems (accumArray (∨) False (0, n−1) (zip is (repeat True)))) where n = length is

Dart // 整数リスト is が 0..n-1 の順列かを線形時間で判定 bool isperm(List<int> is) { final n = is.length; final seen = List.filled(n, false); for (final i in is) { if (i < 0 || i >= n) return false; seen[i] = true; } return seen.every((b) => b); }

ここまでの計算量

最初の rank：入力そのものを見る。ここだけが入力を触る。
それ以降の rerank：整数リスト（順位）だけを触る。
最悪でも log n 回の再順位付けで終わる。

rank が Θ(n log n)、shiftBy が Θ(n) と仮定すると、この段階では Θ(n log² n)。目標の Θ(n log n) にはまだ届いていない。

証明: (12.4) と shiftBy の導出

下ごしらえの補題

まず、要素がすべて非空のリストのリストは、先頭のリストと残りのリストから zipWith (:) で復元できます。

all (not · null) xss ⇒ xss = zipWith (:) (map head xss) (map tail xss)

括弧を減らすため、結論部を次のように書き直します（ここで fork (f, g) x = (f x, g x)。zipWith (:) は非カリー化として扱う）。

id = zipWith (:) · fork (map head, map tail)(12.5)

rats (k+1) の変形

rats (k+1) = {(12.3)} rank · map (take (k+1)) · tails = {(12.5)、map (take (k+1)) · tails は非空} rank · zipWith (:) · fork (map head, map tail) · map (take (k+1)) · tails

ここで fork (f, g) · h = fork (f · h, g · h) と、次の 2 つが成り立ちます（snoc x xs = xs ⧺ [x]）。

map head · map (take (k+1)) · tails = id map tail · map (take (k+1)) · tails = snoc [ ] · tail · map (take k) · tails

これを使って続けます。

rank · zipWith (:) · fork (map head, map tail) · map (take (k+1)) · tails = {上の等式より} rank · zipWith (:) · fork (id, snoc [ ] · tail · map (take k) · tails)

次に zipWith (:) ≈ zip（非カリー化）を使うと、

rats (k+1) = rank · zip · fork (id, snoc [ ] · tail · map (take k) · tails)

となります。rank · zip = (≪) が (12.2) から言えて、しかも xs ≪ ys = xs ≪ rank ys なので、

rats (k+1) = (≪) · fork (id, rank · snoc [ ] · tail · map (take k) · tails)

rank · snoc [ ] = lift · rank（ただし lift = snoc 0 · map (+1)）ですから、

rats (k+1) = (≪) · fork (id, lift · rank · tail · map (take k) · tails)

ここで lift · rank · tail ≈ lift · tail · rank を示せば、右側を rats k に置き換えられます。

lift (rank (tail xs)) ≈ lift (tail (rank xs)) ⇐ {xs ≈ ys ⇒ lift xs ≈ lift ys} rank (tail xs) ≈ tail (rank xs) ≡ {≈ の定義} rank (rank (tail xs)) = rank (tail (rank xs)) ⇐ {(12.1) を 2 度使う（subseq = id と subseq = tail）} true

したがって、

rats (k+1) xs = rank xs ≪ shift (rats k xs)(12.6)

ここで shift = lift · tail、lift is = map (+1) is ⧺ [0] です。

shiftBy の姿を得る

次に shift (is ≪ js) = shift is ≪ shift js と ≪ の結合性を使って (12.6) を展開すると、

rats k xs = rs ≪ shift rs ≪ shift² rs ≪ ⋯ ≪ shift^k−1 rs

（rs = rank xs、shift^k は shift の k 回合成）。ここから項をまとめて、

rats (2∗k) xs = rats k xs ≪ shift^k (rats k xs)

を得ます。shiftBy k = shift^k と置けば (12.4) が示せます。実際に閉じた式で書くと、

shiftBy k rs = map (+k) (drop k rs) ⧺ [k−1, k−2 .. 0]

Dart // shiftBy k rs = shift を k 回合成したもの // 前半は「k 個先の順位に k を足したもの」、末尾に降順の埋め草 [k-1, ..., 0] List<int> shiftBy(int k, List<int> rs) { final n = rs.length; final kk = k < n ? k : n; final head = [ for (var i = kk; i < n; i++) rs[i] + k, ]; final tail = [for (var j = kk - 1; j >= 0; j--) j]; return [...head, ...tail]; }

となり、これは Θ(n) で評価できます（n = length rs）。

rank をよりよく計算する

試験官のやり方

次に rank 自体を高速化します。イメージは試験官が候補者に順位を付ける方法です。

候補者と点数の組を、点数で並べ替える。
同点の候補者を 1 つのグループにまとめる。
1 番目のグループの候補者は順位 0、2 番目のグループは g₀（＝ 1 番目のグループの人数）、3 番目のグループは g₀ + g₁、……と付ける。
最後に元の候補者順に並べ直す。

これを式にすると、

rank = resort · concat · label · psort · zip [0..]

Dart // 高速な rank: psort で同点をまとめ、label で通し番号を付け、resort で元位置に戻す List<int> rankFast<T extends Comparable<T>>(List<T> xs) { final indexed = [for (var i = 0; i < xs.length; i++) (i, xs[i])]; final groups = psort<int, T>(indexed, (a, b) => a.compareTo(b)); final labeled = label<int>(groups); final flat = [for (final grp in labeled) ...grp]; return resort(xs.length, flat); }

分割ソート psort

psort :: Ord b ⇒ [(a, b)] → [[a]] psort xys = pass xys [ ] pass [ ] xss = xss pass (e@(x, y) : xys) xss = step xys [ ] [x] [ ] xss where step [ ] as bs cs xss = pass as (bs : pass cs xss) step (e@(x, y') : xys) as bs cs xss | y' < y = step xys (e : as) bs cs xss | y' = y = step xys as (x : bs) cs xss | y' > y = step xys as bs (e : cs) xss

Dart // psort: 第2成分でソートしつつ、同点をランに束ねて返す (三項クイックソート) // 入力: [(a, b), ...] と b 用の比較関数 // 出力: [[a, a, ...], [a], ...] (同一 b の a たち) List<List<A>> psort<A, B>(List<(A, B)> xys, int Function(B, B) cmp) { List<List<A>> pass(List<(A, B)> xys, List<List<A>> xss) { if (xys.isEmpty) return xss; final pivotY = xys[0].$2; final as = <(A, B)>[]; // pivot 未満 final bs = <A>[xys[0].$1]; // pivot と同点 final cs = <(A, B)>[]; // pivot 超 for (var i = 1; i < xys.length; i++) { final e = xys[i]; final c = cmp(e.$2, pivotY); if (c < 0) as.add(e); else if (c == 0) bs.add(e.$1); else cs.add(e); } return pass(as, [bs, ...pass(cs, xss)]); } return pass(xys, []); }

図 12.1 分割ソート（partition sorting）

psort（partition sort の略）は、点数で並べ替えつつ同点の候補者をランに束ねます。図 12.1 の実装は三項クイックソート（先頭要素を枢軸に使う）で、最悪 Θ(n²)。枢軸に中央値を選べば Θ(n log n) になります。

label と resort

label :: [[a]] → [[(a, Int)]] label xss = zipWith tag xss (scanl (+) 0 (map length xss)) tag xs k = [(x, k) | x ← xs]

Dart // label: 各グループに「そのグループの先頭順位」を付与する // (先頭グループは 0、2番目は先頭グループのサイズ、…) List<List<(A, int)>> label<A>(List<List<A>> xss) { final result = <List<(A, int)>>[]; var k = 0; for (final xs in xss) { result.add([for (final x in xs) (x, k)]); k += xs.length; } return result; }

resort :: [(Int, Int)] → [Int] resort ijs = elems (array (0, length ijs − 1) ijs)

Dart // resort: (元位置, 順位) のリストから配列を作り、元位置順に順位を並べ直す // n を明示的に渡す (Haskell の length ijs) List<int> resort(int n, List<(int, int)> ijs) { final arr = List.filled(n, 0); for (final (i, j) in ijs) { arr[i] = j; } return arr; }

resort は連想リスト ijs から配列を作ってそのまま要素を取り出します。第 1 成分が [0 .. n−1] の順列であることが前提。array と elems が線形時間なので、resort も線形時間です。

最終アルゴリズム

partition で書き直す

rank = resort · concat · label · partition と分解できるので、ranktails を partition ベースで書き直せます。

partition :: Ord a ⇒ [a] → [[Int]] partition = psort · zip [0..]

Dart // partition: xs を「同値な位置」でグループ化して位置のリストのリストを返す List<List<int>> partition<T extends Comparable<T>>(List<T> xs) { final indexed = [for (var i = 0; i < xs.length; i++) (i, xs[i])]; return psort<int, T>(indexed, (a, b) => a.compareTo(b)); }

この置き換えの利点「rank が順列を返す」＝「partition の結果がすべてシングルトン（長さ 1 のリスト）」と言い換えられるので、isperm を all single に置き換えられる。

ranktails = resort · concat · label · applyUntil (all single) repartitions · partition repartitions = map repartition (iterate (∗2) 1) repartition k iss = partition (zip rs (shiftBy k rs)) where rs = resort (concat (label iss))

Dart // partition ベースの ranktails: rank ではなく「グループ分け」を保持したまま // k = 1, 2, 4, ... で細分し、全グループが単独になったら終了 List<int> ranktailsPartition<T extends Comparable<T>>(List<T> xs) { final n = xs.length; var iss = partition(xs); var k = 1; while (!iss.every((g) => g.length == 1)) { iss = repartitionSlow(n, k, iss); k *= 2; } final labeled = label<int>(iss); final flat = [for (final g in labeled) ...g]; return resort(n, flat); } // rs = resort(concat(label(iss))) を作ってから partition(zip(rs, shiftBy(k, rs))) List<List<int>> repartitionSlow(int n, int k, List<List<int>> iss) { final labeled = label<int>(iss); final flat = [for (final g in labeled) ...g]; final rs = resort(n, flat); final ss = shiftBy(k, rs); // partition (zip rs ss) 相当: (位置 i, (rs[i], ss[i])) をペアの辞書順で psort final pairs = [for (var i = 0; i < n; i++) (i, (rs[i], ss[i]))]; int cmpPair((int, int) a, (int, int) b) { final c = a.$1.compareTo(b.$1); return c != 0 ? c : a.$2.compareTo(b.$2); } return psort<int, (int, int)>(pairs, cmpPair); }

ここまでの計算量は前と同じですが、さらなる最適化への扉が開きます。

あと 2 段階の最適化

ステップ 1： 次の等式を使う。

partition (zip xs ys) = concatMap (psort · map (install ys)) (partition xs)(12.7)

install ys i = (i, ys !! i)(12.8)

式 (12.7) の意味ペアのリストを分割するとき、まず第 1 成分だけで分割し、次に各ランの中で第 2 成分を埋め込んで再度分割ソートして連結すればよい。各ランは位置のリストなので、あとから正しい第 2 成分を配列で取ってこられる。

安定性についての注意厳密には (12.7) は psort が安定ソートでないと成り立たない。図 12.1 の psort は安定ではないので、左辺と右辺で各ラン内の並びは違うことがある。だが「各ラン内の並べ替えは同一視する」意味なら成り立ち、ranktails の計算はランの中身の順序に依らないので問題ない。

この式を使って repartition を書き直すと：

repartition k iss = {定義。rs = resort (concat (label iss)) と置く} partition (zip rs (shiftBy k rs)) = {(12.7)} concatMap (psort · map (install (shiftBy k rs))) (partition rs) = {iss = partition xs ⇒ rs = rank xs、かつ partition · rank = partition} concatMap (psort · map (install (shiftBy k rs))) iss

よって

repartition k iss = concatMap (psort · map (install rs)) iss where rs = shiftBy k (resort (concat (label iss)))

ステップ 2： (12.8) の install はリスト索引 (!!) を使っているため定数時間ではありません。定数時間の配列索引 (!) を使うように書き直します。

(shiftBy k (resort (concat (label iss)))) !! i = {shiftBy の定義} (map (+k) (drop k (resort (concat (label iss)))) ⧺ [k−1, k−2 .. 0]) !! i = {算術。n = length(concat (label iss))、j = i+k とおく} if j < n then k + (resort (concat (label iss))) !! j else n−i−1 = {resort の定義と elems a !! i = a ! i より} if j < n then k + array (0, n−1) (concat (label iss)) ! j else n−i−1

最終形

ranktails :: Ord a ⇒ [a] → [Int] ranktails xs = (resort n · concat · label · applyUntil (all single) (repartitions n) · psort · zip [0..]) xs where n = length xs resort n = elems · array (0, n−1) label iss = zipWith tag iss (scanl (+) 0 (map length iss)) tag is j = [(i, j) | i ← is] repartitions n = map (repartition n) (iterate (∗2) 1) repartition n k iss = concatMap (psort · map install) iss where install i = (i, if j < n then k + a ! j else n−i−1) a = array (0, n−1) (concat (label iss))

Dart // 最終アルゴリズム (図 12.2 に対応) // 各ランの中では (!) による定数時間の配列索引で第2成分を作る List<int> ranktailsFinal<T extends Comparable<T>>(List<T> xs) { final n = xs.length; final indexed = [for (var i = 0; i < n; i++) (i, xs[i])]; var iss = psort<int, T>(indexed, (a, b) => a.compareTo(b)); var k = 1; while (!iss.every((g) => g.length == 1)) { iss = repartitionFinal(n, k, iss); k *= 2; } final labeled = label<int>(iss); final flat = [for (final g in labeled) ...g]; return resort(n, flat); } List<List<int>> repartitionFinal(int n, int k, List<List<int>> iss) { // a[i] = 現在の順位 (label + concat の結果を配列化) final a = List.filled(n, 0); var base = 0; for (final g in iss) { for (final i in g) { a[i] = base; } base += g.length; } // 各ランを (i, install(i)) で再ソート (install の値は int) final result = <List<int>>[]; for (final g in iss) { if (g.length == 1) { result.add(g); continue; } final tagged = [ for (final i in g) (i, (i + k < n) ? k + a[i + k] : n - i - 1), ]; result.addAll(psort<int, int>(tagged, (a, b) => a.compareTo(b))); } return result; }

図 12.2 ranktails の最終アルゴリズム

入力の長さ n は一度だけ計算し、必要な補助関数に渡しています。

計算量の解析

再帰式で見積もる

長さ n のリストに対する k 回の再分割の総比較回数を T(n, k) と置きます。本質的には、次元 k の n 個のベクトルを各次元について順に分割ソートしていると見なせます。

ベクトルの第 1 成分：入力の要素。
それ以降の成分：直前までの成分でのソート結果から動的に決まる整数。

ここでは（図 12.1 の実装と違って）各分割ステップが可能な枢軸の中央値を選ぶと仮定します。n 要素の分割には n−1 回の比較が要るので、次のような漸化式になります。

T(0, k) = 0 T(n, 0) = 0 T(n, k) = (max x : 1 ≤ x ≤ n : n−1 + T(x, k−1) + 2 T((n−x)/2, k))

不等式で押さえる

帰納法で T(n, k) ≤ n(log n + k) を示します。それには次の不等式（1 ≤ x ≤ n）を確かめればよく、これは高校程度の計算で示せます。

n−1 + x(log x + k−1) + (n−x)[log(n−x) + k−1] ≤ n(log n + k)

最終的な計算量 k = log n を代入すれば、比較回数は高々 2n log n。総実行時間は Θ(n log n)——目標達成！

実験結果

これだけ計算的な工夫をしても、実際にナイーブ版より速いのか？　3 つのバージョンを比較しました。

(A) ranktails の仕様そのままだが、rank だけ分割ソートで実装。
(B) 再順位付けを繰り返す改良版。
(C) 図 12.2 の最終プログラム。

それぞれを、図 12.1 の psort（＝三項クイックソート、末尾に 1）と、マージソートに基づく Θ(n log n) 版（末尾に 2）で走らせました。

ファイル	サイズ	文字種	AlgA1	AlgB1	AlgC1	AlgA2	AlgB2	AlgC2
dna	10424	5	0.08	0.10	0.08	0.04	0.08	0.16
ps	367639	87	2.76	10.96	2.32	3.18	22.50	3.54
txt	148480	72	0.48	3.08	0.72	0.86	6.06	1.28
ptt5	513216	159	—	136.38	8.70	611.3	37.78	6.32
alla	1000	1	2.96	0.10	0.02	0.18	0.06	0.02

図 12.3 各種ファイルに対する実行時間（秒）

入力は 5 種類：(i) DNA ファイル、(ii) PostScript ファイル、(iii) 『不思議の国のアリス』のテキスト alice29.txt、(iv) 同コーパスの画像ファイル ptt5、(v) 「a」を 1000 個並べたファイル alla。ptt5 行の AlgA1 欄が空欄なのは、12 時間経っても終わらず打ち切ったためです。

実験からの発見

予想どおり、AlgB1・B2 は明確な優位を示さなかった。
最後の 2 行以外では、ナイーブ版でも優位版とほぼ同等。
三項クイックソートに基づく版は、マージソート版より約 2 倍高速。
しかし ptt5（ヌル文字だらけ）や alla（「a」だけ）のような偏った入力では、優位版が圧倒的に速い。
総合的には AlgC1 が最良。

Dart // 動作確認: "banana" の接尾辞に順位を付ける // 接尾辞は "banana", "anana", "nana", "ana", "na", "a" // 辞書順では "a"(0), "ana"(1), "anana"(2), "banana"(3), "na"(4), "nana"(5) // よって ranktails("banana") = [3, 2, 5, 1, 4, 0] void main() { final xs = 'banana'.split(''); print(rankNaive(['c'.codeUnits[0], 'a'.codeUnits[0], 'b'.codeUnits[0]])); // [2, 0, 1] print(ranktailsSpec(xs)); // [3, 2, 5, 1, 4, 0] print(ranktailsIter(xs)); // [3, 2, 5, 1, 4, 0] print(ranktailsPartition(xs)); // [3, 2, 5, 1, 4, 0] print(ranktailsFinal(xs)); // [3, 2, 5, 1, 4, 0] }

最後に

最終アルゴリズムは Larsson and Sadakane (1999) の接尾辞ソートアルゴリズムと密接に関係しています。実はこの章全体が彼らの研究に触発されたものです。

参考文献

Larsson, N. J. and Sadakane, K. (1999). Faster suffix sorting. Research Report LU-CS-TR-99-214, Department of Computer Science, Lund University, Sweden.

Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences. Cambridge, UK: Cambridge University Press.