第2章

追い越し数の問題

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

どんな問題？

配列（またはリスト）の中のある要素について、「自分より右にある、自分より大きい要素の個数」を数える、というのが今回の話です。この個数のことを追い越し数（surpasser count）と呼びます。

言葉の定義

たとえば文字列 GENERATING の各文字について追い越し数の個数を書き並べると、次のようになります。

G  E  N  E  R  A  T  I  N  G 5  6  2  5  1  4  0  1  0  0

最大値は6で、これは最初の E の追い越し数の個数です（右にある N, R, T, I, N, G の 6 文字はすべて E より大きい）。

この章のゴール 長さ n > 1 の配列について、追い越し数の個数の最大値を O(n log n) で求める。

まずは素直な仕様

仕様を書き下す

入力はリストとして与えられるとします。「追い越し数の個数の最大値」を求める関数を msc（maximum surpasser count）と呼ぶことにすると、こう書けます。

msc :: Ord a ⇒ [a] → Int msc xs = maximum [scount z zs | z : zs ← tails xs] scount x xs = length (filter (x <) xs)
Dart // x より大きい要素の個数 int scount<T extends Comparable<T>>(T x, List<T> xs) => xs.where((y) => x.compareTo(y) < 0).length; // 空でない末尾部分すべてに scount を適用し、その最大値を返す（O(n^2)） int msc<T extends Comparable<T>>(List<T> xs) { var best = 0; for (var i = 0; i < xs.length; i++) { final z = xs[i]; final zs = xs.sublist(i + 1); final c = scount(z, zs); if (c > best) best = c; } return best; }

意味は次のとおりです。

tails [] = [] tails (x : xs) = (x : xs) : tails xs
Dart // 空でない末尾部分を長い順に列挙（sync* generator） Iterable<List<T>> tails<T>(List<T> xs) sync* { for (var i = 0; i < xs.length; i++) { yield xs.sublist(i); } }

この msc は動きますが、二乗時間かかってしまいます（各末尾部分について線形時間の scount を呼ぶため）。もっと速くしたい、というのが本題です。

分割統治法で攻める

基本の作戦

目標が O(n log n) なので、リストを半分ずつに分けて解く（分割統治法）を狙いましょう。もし次を満たす線形時間の関数 join があれば、うまくいきます。

msc (xs ++ ys) = join (msc xs) (msc ys)

そうすれば、時間計算量は T(n) = 2T(n/2) + O(n) となり、これを解くと T(n) = O(n log n) です。

残念な観察 実はこのままではダメです。「msc xs（最大値ひとつ）」だけの情報では、半分ずつ計算した結果を組み合わせるには情報が足りなさすぎるのです。

情報を増やす：追い越し数の「表」を作る

そこで、「最大値ひとつ」ではなく、すべての要素についての追い越し数の個数を並べた表を扱うことにします。

table xs = [(z, scount z zs) | z : zs ← tails xs]
Dart // 各要素 z について (z, その右にある z より大きい要素の個数) を並べた表 List<(T, int)> table<T extends Comparable<T>>(List<T> xs) => [ for (var i = 0; i < xs.length; i++) (xs[i], scount(xs[i], xs.sublist(i + 1))), ]; // msc = 表の第2成分の最大値 int mscFromTable<T extends Comparable<T>>(List<T> xs) => table(xs).map((p) => p.$2).reduce((a, b) => a > b ? a : b);

この表さえ計算できれば、msc は「表の第2成分の最大値」として msc = maximum · map snd · table と書けます。目標を「table を O(n log n) で作ること」に置き換えます。

知りたいのは、次を満たす線形時間の join があるかどうかです。

table (xs ++ ys) = join (table xs) (table ys)

導出には、tails についての次の性質を使います。

tails (xs ++ ys) = map (++ ys) (tails xs) ++ tails ys

これは「連結したリストの末尾部分」を、「前半の末尾部分（それぞれに後半を付け足したもの）」と「後半の末尾部分」に分けられる、ということです。

join の候補を計算で導く

table (xs ++ ys) を、上の性質を使って書き換えていきます。

table (xs ++ ys) = {定義より} [(z, scount z zs) | z : zs ← tails (xs ++ ys)] = {tails の分割統治性より} [(z, scount z zs) | z : zs ← map (++ ys) (tails xs) ++ tails ys] = {← を ++ に対して分配} [(z, scount z (zs ++ ys)) | z : zs ← tails xs] ++ [(z, scount z zs) | z : zs ← tails ys] = {scount z (zs ++ ys) = scount z zs + scount z ys より} [(z, scount z zs + scount z ys) | z : zs ← tails xs] ++ [(z, scount z zs) | z : zs ← tails ys] = {table の定義と ys = map fst (table ys) より} [(z, c + scount z (map fst (table ys))) | (z, c) ← table xs] ++ table ys

これから、join の第一の候補が得られます。

join txs tys = [(z, c + tcount z tys) | (z, c) ← txs] ++ tys tcount z tys = scount z (map fst tys)
Dart // 表側で「z より大きい第1成分」の個数を数える int tcount<T extends Comparable<T>>(T z, List<(T, int)> tys) => scount(z, tys.map((p) => p.$1).toList()); // 単純に連結する版（tcount で毎回 tys を走査するため線形にならない） List<(T, int)> joinSlow<T extends Comparable<T>>( List<(T, int)> txs, List<(T, int)> tys) => [ for (final (z, c) in txs) (z, c + tcount(z, tys)), ...tys, ];
まだ遅い この定義のままだと、txs の各要素について tcount z tys を計算するのに tys 全体を走査するので、線形時間になりません。もう一工夫が必要です。

速くするためのカギ：表をソートしておく

tys が第1成分について昇順にソートされていれば、tcount はもっと速く計算できます。次のように書き換えられるからです。

tcount z tys = {tcount と scount の定義より} length (filter (z <) (map fst tys)) = {filter p · map f = map f · filter (p · f ) より} length (map fst (filter ((z <) · fst) tys)) = {length · map f = length より} length (filter ((z <) · fst) tys) = {tys が第1引数でソート済み} length (dropWhile ((z ≥) · fst) tys)

したがって、次が成り立ちます。

tcount z tys = length (dropWhile ((z ≥) · fst) tys)    (2.1)

これを踏まえて、table の定義自体を「第1成分でソート済み」に変えてしまいます。

table xs = sort [(z, scount z zs) | z : zs ← tails xs]
Dart // 第1成分（要素値）で昇順ソート済みの表 List<(T, int)> tableSorted<T extends Comparable<T>>(List<T> xs) { final t = table(xs); t.sort((a, b) => a.$1.compareTo(b.$1)); return t; }

ソート済み版に対して同じ計算をやり直すと、join は次のように書けます（⋀⋀ は「ソート済みの2つのリストをマージ」する演算子）。

join txs tys = [(x, c + tcount x tys) | (x, c) ← txs] ⋀⋀ tys    (2.2)

再帰の形にまとめる

あとは join の場合分けを整理します。

再帰ケースを詳しく見ましょう。

join txs@((x, c) : txs′) tys@((y, d) : tys′)    (2.3)

（Haskell で @ は「別名」を導入します。txs は (x, c) : txs′ の別名、という意味です。）

(2.2) を使うと、(2.3) は次のように書き換えられます。

((x, c + tcount x tys) : [(x, c + tcount x tys) | (x, c) ← txs′]) ⋀⋀ tys

⋀⋀ が最初に取り出す要素はどちら側かを、x と y を比べて決めます。

最適化 length tys を毎回計算しないよう、join の追加の引数として長さ n を持ち回します。マージが進むと tys が1つ短くなる（x ≥ y のとき）ので、n を n−1 に減らしていきます。

最終形

まとめると、table は次の分割統治法アルゴリズムで計算できます。

table [x] = [(x, 0)] table xs = join (m − n) (table ys) (table zs) where m = length xs n = m div 2 (ys, zs) = splitAt n xs join 0 txs [] = txs join n [] tys = tys join n txs@((x, c) : txs′) tys@((y, d) : tys′) | x < y = (x, c + n) : join n txs′ tys | x ≥ y = (y, d) : join (n−1) txs tys′
Dart // n は「右半分に残っている要素数」＝ tys 側の length。 // マージ中、tys から要素を1つ取り出すたびに n を1減らす。 List<(T, int)> joinFast<T extends Comparable<T>>( int n, List<(T, int)> txs, List<(T, int)> tys) { final out = <(T, int)>[]; var i = 0, j = 0; while (i < txs.length && j < tys.length) { final (x, c) = txs[i]; final (y, d) = tys[j]; if (x.compareTo(y) < 0) { // tys の第1成分はすべて x より大きい → tcount x tys = n out.add((x, c + n)); i++; } else { out.add((y, d)); j++; n--; // tys が1つ短くなった } } // 残りを追加 for (; i < txs.length; i++) { final (x, c) = txs[i]; out.add((x, c + n)); // ここで tys が空なら n = 0 } for (; j < tys.length; j++) { out.add(tys[j]); } return out; } // 分割統治で表を構築（O(n log n)） List<(T, int)> tableDC<T extends Comparable<T>>(List<T> xs) { if (xs.length == 1) return [(xs[0], 0)]; final m = xs.length; final n = m ~/ 2; final ys = xs.sublist(0, n); final zs = xs.sublist(n); return joinFast(m - n, tableDC(ys), tableDC(zs)); } // 最終形の msc int mscFast<T extends Comparable<T>>(List<T> xs) => tableDC(xs).map((p) => p.$2).reduce((a, b) => a > b ? a : b);

join は線形時間で動くので、全体は O(n log n) 時間で table を、そして msc を計算できます。

Dart // 動作確認: GENERATING の各文字の追い越し数 void main() { final xs = 'GENERATING'.split(''); print(msc(xs)); // 6 print(mscFast(xs)); // 6 // 追い越し数の一覧（元の並び順）: // G:5, E:6, N:2, E:5, R:1, A:4, T:0, I:1, N:0, G:0 for (var i = 0; i < xs.length; i++) { print('${xs[i]}: ${scount(xs[i], xs.sublist(i + 1))}'); } }

まとめ

計算量の下限 実は table の計算については、これより速いアルゴリズムは作れません。理由は、xs の要素がすべて相異なるとき、table xs だけで xs をソートする順列（並べ替え方）を完全に決められるからです（table xs は reverse xs の転倒表（inversion table）にあたる）。比較に基づくソートには Ω(n log n) 必要なので、table の計算にも同じだけ必要です。

元の Rem (1998b) の解は違うアプローチで、反復＋二分探索を使うそうです。手続き型プログラマなら分割統治法でも解けるでしょうが、多くは省メモリのために、配列を直接書き換えるやり方を選ぶでしょう。

この章のポイントは：

参考文献

Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching, second edition. Reading, MA: Addison-Wesley.

Rem, M. (1988a). Small programming exercises 20. Science of Computer Programming 10 (1), 99–105.

Rem, M. (1998b). Small programming exercises 21. Science of Computer Programming 10 (3), 319–25.

1同名の Haskell 標準関数は少し違い、空になりうるリストの、空になりうる末尾部分を返します。