第4章

選択問題

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

どんな問題？

2つの集合 X と Y があって、共通の要素はないとします。両方合わせたときに、小さい方から k 番目の要素を見つけたい、というのが今回の問題です。

言葉の約束 「k 番目に小さい要素」とは、それより小さい要素がちょうど k 個ある要素のことです。0番目に小さい要素 = 最小の要素、1番目に小さい要素 = 2番目に小さい要素、という数え方です。

どれくらい速く求められる？

速さは、X と Y の持ち方によって変わります。

この章のねらい 高速なアルゴリズムはまた分割統治法の一例です。証明の要は「マージ」と「選択」の間にある特別な関係。本章では、
  1. その関係をはっきり述べる
  2. リスト版の分割統治アルゴリズムを式変形で導く
  3. それを配列版として実装する
という順で進めます。

定式化と第一歩

問題を式で書く

互いに素な2つのソート済みリスト xs, ys に対して、求めたい値はこう書けます。

smallest :: Ord a ⇒ Int → ([a], [a]) → a smallest k (xs, ys) = union (xs, ys) !! k
Dart // 仕様: 互いに素な2つの昇順リストをマージし、0-index で k 番目を返す T smallestSpec<T extends Comparable<T>>(int k, List<T> xs, List<T> ys) { return union(xs, ys)[k]; }

xs !! k は「リスト xs の 0 から数えて位置 k の要素」です。union は、互いに素で各々ソート済みの2つのリストをマージする関数で、次のように定義されます。

union (xs, [ ]) = xs union ([ ], ys) = ys union (x : xs, y : ys) | x < y = x : union (xs, y : ys) | x > y = y : union (x : xs, ys)
Dart // 互いに素で各々昇順の2つのリストをマージする（< と > のみ、= は現れない前提） List<T> union<T extends Comparable<T>>(List<T> xs, List<T> ys) { final result = <T>[]; var i = 0, j = 0; while (i < xs.length && j < ys.length) { final c = xs[i].compareTo(ys[j]); if (c < 0) { result.add(xs[i++]); } else { result.add(ys[j++]); // 互いに素なので c == 0 は起きない } } result.addAll(xs.sublist(i)); result.addAll(ys.sublist(j)); return result; }

分解の道具（式 4.1）

これから分割統治にするため、!! と union の「分解の仕方」を用意しておきます。length xs を |xs| と略記すると、まず次が成り立ちます。

(xs ++ ys) !! k = if k < |xs| then xs !! k else ys !! (k − |xs|) (4.1)
気持ち 「連結したリストの k 番目」は、k が前半にあれば前半の k 番目、後半にあれば「後半の (k − 前半の長さ) 番目」に等しい、という当たり前の事実です。

もう1つの道具（式 4.2）

xs ++ ys と us ++ vs がソート済みで互いに素とし、さらに次を仮定します。

union (xs, vs) = xs ++ vs かつ union (us, ys) = us ++ ys

言い換えると、「xs のすべての要素は vs のすべての要素より小さい」「us のすべての要素は ys のすべての要素より小さい」ということです。このとき、

union (xs ++ ys, us ++ vs) = union (xs, us) ++ union (ys, vs) (4.2)

が成り立ちます。union を中置の ∪ で書けば、こう見た目がすっきりします。

(xs ++ ys) ∪ (us ++ vs) = (xs ∪ us) ++ (ys ∪ vs)

「abide（アバイド）」ってなに？

これは、リスト差 \\ についての似た恒等式と同じ形をしています。

(xs ++ ys) \\ (us ++ vs) = (xs \\ us) ++ (ys \\ vs)
用語メモ：abide 2つの演算子 ++ と ∪（または ++ と \\）がこのように協力し合う関係を「互いに abide する」といいます。
"abide" は "above-beside" の短縮で、「同じ高さの絵を左右に並べる」演算と「同じ幅の絵を上下に並べる」演算が入れ替え可能である、という絵のイメージから来ています。

記号 ◁ の意味

以降、条件 union (xs, ys) = xs ++ ys を xs ◁ ys と略記します。

読み方 xs ◁ ys は「xs の要素はすべて ys の要素より小さい」ということ。空でないリストどうしに限れば、◁ は推移的な関係になります（xs ◁ ys かつ ys ◁ zs なら xs ◁ zs）。

分割統治で解く

ねらいの式

次の式をうまく小さくすることが目標です。

smallest k (xs ++ [a] ++ ys, us ++ [b] ++ vs)

ここで a と b は、それぞれのリストの「真ん中あたりの要素」を取り出したものだと思ってください。a < b の場合だけ扱えば十分で、a > b の場合は完全に対称（同じ議論の左右をひっくり返すだけ）です。

直観 a < b なら、リストが昇順であることから xs ++ [a] のどの要素も [b] ++ vs のどの要素より小さい、つまり (xs ++ [a]) ◁ ([b] ++ vs) が成り立ちます。ここが式 (4.2) を使うためのカギです。

場合分け

p = length xs, q = length us とおきます。式 (4.1) と (4.2)、そして abides の性質を使って計算を丁寧に進めると、次の2つの場合に分かれます。

ケース1：k ≤ p+q のとき

これは「求めたい順位が、xs+a+us の中で決まる」場合。答えの候補は左寄りにあるので、右側の [b] ++ vs は捨てて構いません。

smallest k (xs ++ [a] ++ ys, us ++ [b] ++ vs) = smallest k (xs ++ [a] ++ ys, us) (a < b の場合)

ケース2：k > p+q のとき

これは「答えは xs+a+us より右にある」場合。左側の xs ++ [a] を捨てて、k を p+1 だけ引いて再帰します。

smallest k (xs ++ [a] ++ ys, us ++ [b] ++ vs) = smallest (k−p−1) (ys, us ++ [b] ++ vs) (a < b の場合)
まとめ（a < b の場合）
smallest k (xs ++ [a] ++ ys, us ++ [b] ++ vs) | k ≤ p+q = smallest k (xs ++ [a] ++ ys, us) | k > p+q = smallest (k−p−1) (ys, us ++ [b] ++ vs) where (p, q) = (length xs, length us)
Dart // a < b の場合の場合分け（zs = xs ++ [a] ++ ys, ws = us ++ [b] ++ vs 前提） // k ≤ p+q なら右側 [b] ++ vs を捨て、k > p+q なら左側 xs ++ [a] を捨てる T smallestLtCase<T extends Comparable<T>>( int k, List<T> xs, T a, List<T> ys, List<T> us, T b, List<T> vs) { final p = xs.length, q = us.length; if (k <= p + q) { return smallestList(k, [...xs, a, ...ys], us); } else { return smallestList(k - p - 1, ys, [...us, b, ...vs]); } }
a > b の場合はまったく対称に、左右の役割を入れ替えたバージョンが成り立ちます。

導出の骨子（式変形の流れ）

ケース1の計算だけ、要点をつまんで紹介します（詳しくは通常版を参照）。

  1. 定義を展開：smallest = union … !! k に開く。
  2. ys を分ける：ys = ys₁ ++ ys₂ で、(xs ++ [a] ++ ys₁) ◁ ([b] ++ vs) かつ us ◁ ys₂ となるように分割する。
  3. abides を使う：union を2つの独立な union の連結に分解する。
  4. (4.1) で片方を捨てる：k が左に収まるので右側の union は不要。
  5. もう一度 abides を戻す：ys₂ を [ ] とみなして union をまとめ直し、定義に戻して結論を得る。

基底ケースと最終プログラム

あとは、どちらかのリストが空のときの処理を書けば完成です。

smallest k ([ ], ws) = ws !! k smallest k (zs, [ ]) = zs !! k smallest k (zs, ws) = case (a < b, k ≤ p+q) of (True, True) → smallest k (zs, us) (True, False) → smallest (k−p−1) (ys, ws) (False, True) → smallest k (xs, ws) (False, False) → smallest (k−q−1) (zs, vs) where p = (length zs) div 2 q = (length ws) div 2 (xs, a : ys) = splitAt p zs (us, b : vs) = splitAt q ws
Dart // リスト版の分割統治：各再帰でどちらかを半分にする（ただしリストのままだと線形時間止まり） T smallestList<T extends Comparable<T>>(int k, List<T> zs, List<T> ws) { if (zs.isEmpty) return ws[k]; if (ws.isEmpty) return zs[k]; final p = zs.length ~/ 2; final q = ws.length ~/ 2; final xs = zs.sublist(0, p), a = zs[p], ys = zs.sublist(p + 1); final us = ws.sublist(0, q), b = ws[q], vs = ws.sublist(q + 1); final aLtB = a.compareTo(b) < 0; final kInLeft = k <= p + q; return switch ((aLtB, kInLeft)) { (true, true) => smallestList(k, zs, us), (true, false) => smallestList(k - p - 1, ys, ws), (false, true) => smallestList(k, xs, ws), (false, false) => smallestList(k - q - 1, zs, vs), }; }
注意：この段階ではまだ速くない リストのままだと、length や splitAt でリスト全体を走査するため、実行時間は xs, ys の長さに線形にとどまります。仕様（マージして k 番目を取る）と同じで、うれしくありません。
真価は次のステップ、配列で持ったときに出ます。

配列で持って対数時間に

基本アイデア：分割ではなくインデックスを動かす

xs, ys が配列で与えられていれば、リストそのものを2つに分ける必要はありません。配列を固定したまま、「今見ている区間」を表す2つのインデックス (lx, rx) だけを動かせば十分です。

より正確に言うと、リスト xs を配列 xa と (lx, rx) の組で表し、xs = map (xa!) [lx .. rx−1] と抽象化します。ここで (!) は Haskell の Data.Array における配列アクセスで、定数時間で動きます。

immutable な配列 Data.Array の配列は一度作ったら書き換えない（immutable な）配列です。書き換えができない代わりに、アクセス (!) が定数時間、というのが売りです。

リスト xs を 0 から始まる配列 xa に変換するには次のようにします。

xa = listArray (0, length xs − 1) xs

入り口の関数

smallest :: Int → (Array Int a, Array Int a) → a smallest k (xa, ya) = search k (0, m+1) (0, n+1) where (0, m) = bounds xa (0, n) = bounds ya
Dart // 配列版の入口。区間は半開 [lx, rx), [ly, ry) として渡す。 T smallest<T extends Comparable<T>>(int k, List<T> xa, List<T> ya) { return search(k, xa, ya, 0, xa.length, 0, ya.length); }

bounds は配列の下限・上限を返す関数（ここではどちらも 0 始まり）。実際の計算は、内部関数 search が受け持ちます。

本体：search（図4.1）

search k (lx, rx) (ly, ry) | lx == rx = ya ! k | ly == ry = xa ! k | otherwise = case (xa ! mx < ya ! my, k ≤ mx+my) of (True, True) → search k (lx, rx) (ly, my) (True, False) → search (k−mx−1) (mx, rx) (ly, ry) (False, True) → search k (lx, mx) (ly, ry) (False, False) → search (k−my−1) (lx, rx) (my, ry) where mx = (lx+rx) div 2; my = (ly+ry) div 2
Dart // 配列を固定し、区間 [lx, rx), [ly, ry) の中央 mx, my を比較して // 4通りで枝刈り。各再帰で必ず片方の幅が半分になる。 T search<T extends Comparable<T>>( int k, List<T> xa, List<T> ya, int lx, int rx, int ly, int ry) { if (lx == rx) return ya[k]; if (ly == ry) return xa[k]; final mx = (lx + rx) ~/ 2; final my = (ly + ry) ~/ 2; final xLtY = xa[mx].compareTo(ya[my]) < 0; final kInLeft = k <= mx + my; return switch ((xLtY, kInLeft)) { (true, true) => search(k, xa, ya, lx, rx, ly, my), (true, false) => search(k - mx - 1, xa, ya, mx, rx, ly, ry), (false, true) => search(k, xa, ya, lx, mx, ly, ry), (false, false) => search(k - my - 1, xa, ya, lx, rx, my, ry), }; }
なぜ対数時間になる？

おまけ：多重集合（重複あり）の場合

ここまでは「互いに素で、しかも狭義の昇順」を仮定してきました。もし重複を許した弱昇順（≤ で並んだ）のリスト（＝多重集合／バッグ）にしたい場合はどうでしょうか。

マージ関数を、union の <, > を ≤, ≥ に置き換えた merge にします。

merge ([ ], ys) = ys merge (xs, [ ]) = xs merge (x : xs, y : ys) | x ≤ y = x : merge (xs, y : ys) | x ≥ y = y : merge (x : xs, ys)
Dart // 重複を許した弱昇順の2つのリストをマージ（≤ / ≥ で場合分け） List<T> merge<T extends Comparable<T>>(List<T> xs, List<T> ys) { final result = <T>[]; var i = 0, j = 0; while (i < xs.length && j < ys.length) { if (xs[i].compareTo(ys[j]) <= 0) { result.add(xs[i++]); } else { result.add(ys[j++]); } } result.addAll(xs.sublist(i)); result.addAll(ys.sublist(j)); return result; }
気をつけること 多重集合の場合、merge (xs, ys) !! k は「合わせたリストの k 番目に小さい要素」とは必ずしも一致しません（重複の数え方が変わるため）。
ただし、◁ を ⊴（xs ⊴ ys ⇔ xs の任意の x と ys の任意の y について x ≤ y）に置き換え、場合分けの a < b, a > b をそれぞれ a ≤ b, a ≥ b に緩めれば、上で行った計算はそのまま通用します。

おわりに

この章のふりかえり

ちなみに、本章の内容はもともと Bird (1997) として別の題名で発表されたものですが、そちらはマージと選択の関係の扱いにかなり難儀していました。その後、Jeremy Gibbons (1997) がずっと単純な道筋を見つけ、本章の計算はほぼ彼の筋道に沿ったものになっています。

Dart // 動作確認: 互いに素な2つの昇順リストから k 番目に小さい要素を求める void main() { final xs = [1, 3, 5, 7, 9, 11]; final ys = [2, 4, 6, 8, 10, 12]; // マージ結果は [1..12]。0-index の 4 番目 = 5 print(smallest(4, xs, ys)); // 5 print(smallestList(4, xs, ys)); // 5（リスト版の分割統治） // 端の例 print(smallest(0, xs, ys)); // 1（最小） print(smallest(11, xs, ys)); // 12（最大） }

参考文献

Bird, R. S. (1997). On merging and selection. Journal of Functional Programming 7 (3), 349–54.

Gibbons, J. (1997). More on merging and selection. テクニカルレポート CMS-TR-97-08, Oxford Brookes University, UK.

1「Pearl 1（最小の空き番号）」で使ったのと同じ形の恒等式です。

2"abide" は above-beside の短縮形。同じ高さの絵を横並びに、同じ幅の絵を上下に並べる2つの演算が入れ替え可能である、という図形のイメージから来ている用語です。