第5章
対ごとの和のソート
（やさしい版）
Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）
どんな問題？
2つのリスト xs と ys があるとき、そのすべての組み合わせについて和を作り、それを小さい順に並べる、という問題を考えます。
Haskell 風に書くと、こうなります。
sortsums :: [A] → [A] → [A]
sortsums xs ys = sort [x ⊕ y | x ← xs, y ← ys]
Dart
// A は今回は int、⊕ は加算 add とする（アーベル群の一例）。
typedef A = int;
A add(A x, A y) => x + y;
A negate(A x) => -x;
A sub(A x, A y) => add(x, negate(y)); // ⊖
// 素朴版: すべての x ⊕ y を作ってソート
List<A> sortsumsNaive(List<A> xs, List<A> ys) {
final sums = <A>[
for (final x in xs)
for (final y in ys) add(x, y),
];
sums.sort();
return sums;
}
ここで xs と ys の長さがどちらも n だとすると、和の個数は n2 個になります。この n2 個の和を並べ替えるには、比較を何回すればよいでしょうか？
この章のテーマ
素直にやると O(n2 log n) 回の比較が必要です。でも、演算 ⊕ が「アーベル群」の性質（引き算ができる、順序を入れ替えても同じ、など）を満たすとき、Lambert (1992) は比較の回数だけなら O(n2) 回に減らせることを示しました。この章では、その巧妙な分割統治アルゴリズムを Haskell で実装します。
はじめに
問題設定
まず前提を整理します。A は「小さい・大きい」が決まっている（線形順序が入っている）集合とします。演算 (⊕) :: A → A → A は単調とします。単調とは、次のことを言います。
x ≤ x′ かつ y ≤ y′ ⇒ x ⊕ y ≤ x′ ⊕ y′
この前提のもとで sortsums xs ys を計算するのに何回の比較が必要か、を考えるのが本章のテーマです。
素朴な上界と下界
- 上界：n2 個の和を単にソートすれば O(n2 log n) 回で済みます。⊕ の単調性は使いません。
- 下界：⊕ について「単調」以上の情報がないなら、これはそのまま下界にもなります。つまり単調性だけでは漸近的な回数は減らせず、定数倍しか良くなりません。
アーベル群という追加条件
ここで (⊕, A) がアーベル群だと仮定を強めます。つまり、
- ⊕ は結合的で可換
- 単位元 e がある
- 逆元をとる演算 negate :: A → A があって x ⊕ negate x = e
このとき Lambert (1992) は、sortsums を O(n2) 回の比較で計算できることを証明しました。ただし彼のアルゴリズムは、比較以外に Cn2 log n 回の追加操作を要し、しかも定数 C はかなり大きいです。
未解決問題
Harper ら (1975) が最初に提起してから 35 年以上経った今も、「sortsums を比較 O(n2) 回かつ他の操作も O(n2) 回で計算できるか？」は未解決です。
Lambert のアルゴリズム
下界 Ω(n2 log n) の証明（単調性のみのとき）
⊕ が単調としか分かっていないとき、なぜ n2 log n 回の比較が必要かを示します。xs と ys をどちらも昇順にソートし、次の n × n 行列を考えます。
[[x ⊕ y | y ← ys] | x ← xs]
単調性から、この行列は各行も各列も昇順になります。これは標準ヤング盤と呼ばれる対象の一例です。Knuth (1998) の第 5.1.4 節・定理 H により、1 から n2 をこの行列に割り当てる方法はちょうど
E(n) = (n2)! / ( (2n−1)!/(n−1)! · (2n−2)!/(n−2)! · … · n!/0! )
通りあります。すなわち、入力をソートしうる潜在的な並べ替えがちょうど E(n) 通りあるということです。log E(n) = Ω(n2 log n) が知られているので、少なくともこの回数の比較が必要だと分かります。
2つの基本事実
ここからが Lambert のアルゴリズムの本題です。まず、引き算にあたる演算 (⊖) を次で定義します。
x ⊖ y = x ⊕ negate y
このとき次の2つが成り立ちます。
x ⊕ y = x ⊖ negate y (5.1)
x ⊖ y ≤ x′ ⊖ y′ ≡ x ⊖ x′ ≤ y ⊖ y′ (5.2)
(5.1) は簡単ですが、(5.2) の証明にはアーベル群の性質がすべて必要です（本書では演習）。この2つが意味するのは、
- (5.1)：「和を並べる問題」は「引き算を並べる問題」に置き換えられる。
- (5.2)：「2つのリスト間の引き算を並べる問題」は、1つのリスト内の引き算を並べる問題に置き換えられる。
ラベル付き引き算のリスト
(5.1) と (5.2) を使うため、どの位置から来たかのラベルを付けた引き算のリスト subs xs ys を作ります。
subs :: [A] → [A] → [Label A]
subs xs ys = [(x ⊖ y, (i, j)) | (x, i) ← zip xs [1..], (y, j) ← zip ys [1..]]
Dart
// ラベル付きの値。値と、(xsの何番目, ysの何番目) の1始まりインデックス。
typedef Label = (A, (int, int));
// subs xs ys = [(x ⊖ y, (i, j)) | x ← xs, y ← ys]
List<Label> subs(List<A> xs, List<A> ys) {
final out = <Label>[];
for (var i = 0; i < xs.length; i++) {
for (var j = 0; j < ys.length; j++) {
out.add((sub(xs[i], ys[j]), (i + 1, j + 1)));
}
}
return out;
}
ここで Label a は (a, (Int, Int)) の別名です。各項 x ⊖ y に「x が xs の何番目か、y が ys の何番目か」が付いています。このラベル情報は後で必要になります。
(5.1) をそのまま使うと、和のソートは引き算のソート＋ラベル剥がしで得られます。
sortsums xs ys = map fst (sortsubs xs (map negate ys))
sortsubs xs ys = sort (subs xs ys)
Dart
// 和のソートは「y を否定してから引き算のソート」＋ラベル剥がし
List<A> sortsums(List<A> xs, List<A> ys) {
final negYs = [for (final y in ys) negate(y)];
return [for (final t in sortsubs(xs, negYs)) t.$1];
}
// 参考: 素朴な sortsubs（比較で直接ソート）
List<Label> sortsubsNaive(List<A> xs, List<A> ys) {
final s = subs(xs, ys);
s.sort((p, q) => p.$1.compareTo(q.$1));
return s;
}
速くするためのカギ：table を作る
次に (5.2) を活用し、sortsubs xs ys を二次回数の比較で計算する方法を作ります。table というリストを次のように構成します。
table :: [A] → [A] → [(Int, Int, Int)]
table xs ys = map snd (map (tag 1) xxs /\/\ map (tag 2) yys)
where xxs = sortsubs xs xs
yys = sortsubs ys ys
tag i (x,(j,k)) = (x,(i,j,k))
Dart
// (i, j, k) の三つ組。i は「どちらから来たか」(1: xs, 2: ys)。
typedef Triple = (int, int, int);
typedef Tagged = (A, Triple);
// ソート済みの2つのリストを比較のみでマージ（安定）
List<Tagged> mergeTagged(List<Tagged> a, List<Tagged> b) {
final out = <Tagged>[];
var i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i].$1.compareTo(b[j].$1) <= 0) {
out.add(a[i++]);
} else {
out.add(b[j++]);
}
}
out.addAll(a.sublist(i));
out.addAll(b.sublist(j));
return out;
}
Tagged tag(int i, Label lab) {
final (x, (j, k)) = lab;
return (x, (i, j, k));
}
// table xs ys = map snd (map (tag 1) xxs /\/\ map (tag 2) yys)
List<Triple> table(List<A> xs, List<A> ys) {
final xxs = sortsubsPrime(xs);
final yys = sortsubsPrime(ys);
final merged = mergeTagged(
[for (final e in xxs) tag(1, e)],
[for (final e in yys) tag(2, e)],
);
return [for (final e in merged) e.$2];
}
ここで /\/\ はソート済みの2つのリストをマージする演算です。要するに table は、
- xs 内の引き算をソートしたリスト xxs と、ys 内の引き算をソートしたリスト yys を用意し、
- それぞれの要素に「どちらから来たか」の目印（タグ 1 か 2）を付け、
- マージしたもの、
から得られます。
重要な観察
(5.2) より、x ⊖ y のラベルが (i, j)、x′ ⊖ y′ のラベルが (k, ℓ) のとき、
x ⊖ y ≤ x′ ⊖ y′ ⇔ table の中で (1, i, k) が (2, j, ℓ) より前にある
つまり、table さえ作ってしまえば、あとはA 上の比較を一切追加せずに sortsubs xs ys を計算できます。
Haskell の配列で高速化
前後関係を素早く調べるため、table を Haskell の配列に変換します。
mkArray xs ys = array b (zip (table xs ys) [1..])
where b = ((1,1,1), (2,p,p))
p = max (length xs) (length ys)
Dart
// (i, j, k) → 順位（1始まり）の辞書。定数時間の前後関係チェックに使う。
class OrderTable {
final Map<Triple, int> _pos;
OrderTable(this._pos);
int posOf(Triple t) => _pos[t]!;
}
OrderTable mkArray(List<A> xs, List<A> ys) {
final t = table(xs, ys);
final m = <Triple, int>{};
for (var idx = 0; idx < t.length; idx++) {
m[t[idx]] = idx + 1;
}
return OrderTable(m);
}
ライブラリ Data.Array の array は、境界（最小と最大の添字の対）と、添字–値の関連リストから配列を作ります。a = mkArray xs ys とすると、a ! (1,i,k) < a ! (2,j,ℓ) が「(1, i, k) が (2, j, ℓ) より前」に対応します。配列の添字参照 (!) は定数時間なので、前後関係チェックも定数時間です。
これを使って、Haskell のユーティリティ sortBy で sortsubs xs ys を計算できます。
sortsubs xs ys = sortBy (cmp (mkArray xs ys)) (subs xs ys)
cmp a (x,(i,j)) (y,(k,ℓ))
= compare (a ! (1,i,k)) (a ! (2,j,ℓ))
Dart
// 事前に構築した OrderTable を使い、A 上の比較を一切使わずに sortsubs を計算
int cmp(OrderTable a, Label p, Label q) {
final (_, (i, j)) = p;
final (_, (k, l)) = q;
return a.posOf((1, i, k)).compareTo(a.posOf((2, j, l)));
}
List<Label> sortsubs(List<A> xs, List<A> ys) {
final a = mkArray(xs, ys);
final s = subs(xs, ys);
s.sort((p, q) => cmp(a, p, q));
return s;
}
compare は型クラス Ord のメソッドです。ちなみに sort = sortBy compare、/\/\ = mergeBy compare です。sortBy の分割統治的な定義は割愛します。
ここまでのまとめと残された課題
ここまでのコードを図 5.1 にまとめます。ただし sortsubs′ xs = sortsubs xs xs の定義が残っています。この定義をそのまま sortsums に使うと再帰が整礎的にならない（うまく減らないため止まらない）ので、別の方法で計算する必要があります。
sortsums xs ys = map fst (sortsubs xs (map negate ys))
sortsubs xs ys = sortBy (cmp (mkArray xs ys)) (subs xs ys)
subs xs ys = [(x ⊖ y, (i, j)) | (x, i) ← zip xs [1..], (y, j) ← zip ys [1..]]
cmp a (x,(i,j)) (y,(k,ℓ))
= compare (a ! (1,i,k)) (a ! (2,j,ℓ))
mkArray xs ys = array b (zip (table xs ys) [1..])
where b = ((1,1,1), (2,p,p))
p = max (length xs) (length ys)
table xs ys = map snd (map (tag 1) xxs /\/\ map (tag 2) yys)
where xxs = sortsubs′ xs
yys = sortsubs′ ys
tag i (x,(j,k)) = (x,(i,j,k))
図 5.1 sortsubs′ を除く sortsums の完全なコード
計算量の内訳
sortsubs xs ys の計算は O(mn log mn) ステップですが、table の構成以外に A 上の比較は使いません。table の構成には O(m2 + n2) 回の比較と、sortsubs′ xs、sortsubs′ ys の構成に必要な比較しか要りません。あとは sortsubs′ を二次回数の比較で計算できればゴールです。
分割統治
ラベルなしで見た基本アイデア
ラベルをいったん忘れ、[x ⊖ y | x ← xs, y ← ys] を xs ⊖ ys と書くと、分割統治の核心は次の恒等式です。
(xs ++ ys) ⊖ (xs ++ ys)
= (xs ⊖ xs) ++ (xs ⊖ ys) ++ (ys ⊖ xs) ++ (ys ⊖ ys)
つまり、左辺のリストをソートしたいなら、右辺の4つのリストを別々にソートしてマージすればよいということです。
ラベル付き版の合成則
ラベルを付けると少し複雑になります。m = length xs として、次のようにラベルをずらします。
subs (xs ++ ys) (xs ++ ys)
= subs xs xs ++ map (incr m) (subs xs ys) ++
map (incl m) (subs ys xs) ++ map (incb m) (subs ys ys)
incl m (x,(i,j)) = (x, (m+i, j))
incr m (x,(i,j)) = (x, (i, m+j))
incb m (x,(i,j)) = (x, (m+i, m+j))
Dart
// ラベルの片方 / 両方に m をずらすヘルパ
Label incl(int m, Label e) { final (x, (i, j)) = e; return (x, (m + i, j)); }
Label incr(int m, Label e) { final (x, (i, j)) = e; return (x, (i, m + j)); }
Label incb(int m, Label e) { final (x, (i, j)) = e; return (x, (m + i, m + j)); }
sortsubs′ の実装
sortsubs′ [ ] = [ ]
sortsubs′ [w] = [(w ⊖ w, (1,1))]
sortsubs′ ws = foldr1 (/\/\) [xxs,
map (incr m) xys,
map (incl m) yxs,
map (incb m) yys]
where xxs = sortsubs′ xs
xys = sortBy (cmp (mkArray xs ys)) (subs xs ys)
yxs = map switch (reverse xys)
yys = sortsubs′ ys
(xs, ys) = splitAt m ws
m = length ws div 2
incl m (x,(i,j)) = (x, (m+i, j))
incr m (x,(i,j)) = (x, (i, m+j))
incb m (x,(i,j)) = (x, (m+i, m+j))
switch (x,(i,j)) = (negate x, (j,i))
Dart
// ソート済みラベル列を比較のみでマージ
List<Label> mergeLabels(List<Label> a, List<Label> b) {
final out = <Label>[];
var i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i].$1.compareTo(b[j].$1) <= 0) {
out.add(a[i++]);
} else {
out.add(b[j++]);
}
}
out.addAll(a.sublist(i));
out.addAll(b.sublist(j));
return out;
}
// switch (x,(i,j)) = (negate x, (j,i))
Label switchLbl(Label e) {
final (x, (i, j)) = e;
return (negate(x), (j, i));
}
// sortsubs′ ws : ws 内の全ての x ⊖ y をソート
List<Label> sortsubsPrime(List<A> ws) {
if (ws.isEmpty) return const [];
if (ws.length == 1) {
return [(sub(ws[0], ws[0]), (1, 1))];
}
final m = ws.length ~/ 2;
final xs = ws.sublist(0, m);
final ys = ws.sublist(m);
final xxs = sortsubsPrime(xs);
final yys = sortsubsPrime(ys);
final xys = sortsubs(xs, ys);
final yxs = [for (final e in xys.reversed) switchLbl(e)];
// xxs ∪ (incr m xys) ∪ (incl m yxs) ∪ (incb m yys) を全部マージ
final parts = [
xxs,
[for (final e in xys) incr(m, e)],
[for (final e in yxs) incl(m, e)],
[for (final e in yys) incb(m, e)],
];
return parts.reduce(mergeLabels);
}
図 5.2 sortsubs′ のコード
手順を言葉で説明すると、sortsubs′ ws は次のように動きます。
- ws をちょうど半分に分けて xs, ys とする。
- sortsubs′ xs と sortsubs′ ys を再帰的に計算する。
- sortsubs xs ys は前節のアルゴリズム（table と配列を使う方法）で計算する。
- sortsubs ys xs は、sortsubs xs ys を反転して各要素を否定するだけでよい：
sortsubs ys xs = map switch (reverse (sortsubs xs ys))
switch (x,(i,j)) = (negate x, (j,i))
Dart
// sortsubs ys xs は sortsubs xs ys から追加比較なしで得られる
List<Label> sortsubsFlipped(List<A> xs, List<A> ys) =>
[for (final e in sortsubs(xs, ys).reversed) switchLbl(e)];
計算量の解析
結論の数式
比較回数 C(n) は C(n) = 2C(n/2) + O(n2) を満たし、解は C(n) = O(n2)。
つまり sortsums は O(n2) 回の比較で計算できます。
いっぽう、比較以外も含めた総時間 T(n) は T(n) = 2T(n/2) + O(n2 log n) を満たし、解は T(n) = O(n2 log n) です。log の因子を消すには sortBy cmp を二次時間で計算できればよいのですが、それはまだ実現できていません。
実用上の注意
比較を他の操作（配列参照など）で置き換える分だけ余計な仕事が増えるので、このアルゴリズムは実際に動かすとかなり遅いです。理論的な興味が主眼です。
Dart
// 動作確認: xs = [1, 4, 7], ys = [2, 3, 5]
void main() {
final xs = [1, 4, 7];
final ys = [2, 3, 5];
// 素朴版
print(sortsumsNaive(xs, ys));
// [3, 4, 5, 6, 7, 8, 9, 10, 12]
// Lambert 流（table + 分割統治）
print(sortsums(xs, ys));
// 同じく [3, 4, 5, 6, 7, 8, 9, 10, 12]
}
おわりに
対ごとの和のソート問題は、Open Problems Project (Demaine et al., 2009) の問題 41 として掲載されています。これは計算幾何学などの分野で研究者が関心を持つ未解決問題を集めたウェブリソースです。
この問題の最も古い記録は Fedman (1976) で、そこでは問題を Elwyn Berlekamp に帰しています。これらの文献はいずれも問題を「アーベル群の元」ではなく「数」の言葉で扱っていますが、本質は同じです。
参考文献
Demaine, E. D., Mitchell, J. S. B. and O'Rourke, J. (2009). The Open Problems Project. http://mave.smith.edu/~orourke/TOPP/.
Fedman, M. L. (1976). How good is the information theory lower bound in sorting? Theoretical Computer Science 1, 355–61.
Harper, L. H., Payne, T. H., Savage, J. E. and Straus, E. (1975). Sorting X + Y. Communications of the ACM 18 (6), 347–9.
Knuth, D. E. (1998). The Art of Computer Programming: Volume 3, Sorting and Searching, second edition. Reading, MA: Addison-Wesley.
Lambert, J.-L. (1992). Sorting the sums (xi + yj) in O(n2) comparisons. Theoretical Computer Science 103, 137–41.