- 中央値はソートすれば簡単に求められるが、ソートのコストのため、単一要素選択問題でも O(n log n) の限界に縛られる
- quickselect は必要な側だけを再帰的に探索することで、平均 O(n) で kth 要素や中央値を見つけられる
- ランダムピボットは実運用でうまく機能するが、悪いピボットを選び続けると一度に 1 要素しか除去できず、O(n²) まで悪化する
- median-of-medians は 5 個ずつにまとめたグループの中央値からさらに中央値を選び、最悪の場合でも少なくとも 30% の要素を除去できるようにする
- 実際の実装ではピボット計算コストが大きくなることがあり、C++ 標準ライブラリのように quickselect と heapselect を組み合わせた introselect のほうが、より実用的な選択になることがある
ソートで中央値を求めるときの限界
- 最も単純な中央値計算は、リストをソートした後に中央インデックスの値を選ぶ方式である
- 奇数長のリストは中央の要素を返し、偶数長のリストは中央 2 要素の平均を返す
- 比較ベースのソートの最速時間計算量は O(n log n) なので、この方式の実行時間もソートに支配される
- コードが単純という利点はあるが、中央値 1 つだけを見つけるには必要以上の作業をしている
平均 O(n) を実現する quickselect
- quickselect は Tony Hoare が作った再帰アルゴリズムで、中央値だけでなくリストの任意の kth 要素も見つけられる
- 基本的な流れは、ピボットを基準にリストを分割した後、kth 要素が含まれる側だけを続けて探索する方式である
- リストからピボット (pivot) を 1 つ選ぶ
- ピボット以下の要素とピボット超過の要素にリストを分ける
- 求める kth 要素がどちら側にあるかを判断し、その部分リストでのみ再帰呼び出しを行う
- 右側の部分リストへ進むときは、すでに除外した左側要素数ぶんだけ k の値を調整する
- 例のリスト
[9,1,0,2,3,4,6,8,7,10,5] では長さが 11 なので 6 番目に小さい要素を探し、ピボットに応じて範囲を狭めて最終的に 5 を返す
quickselect_median はリスト長が奇数なら中央インデックス 1 つを quickselect で見つけ、偶数なら中央 2 つのインデックスを見つけて平均を取る- ピボットがリストをほぼ半分ずつに分ければ、処理量は
n + n/2 + n/4 + ... = 2n となり O(n) になる
最悪の場合を避けるには良いピボットが必要
- quickselect の平均 O(n) は、ピボット選択が十分に良好であるという条件に依存している
- 各段階で最大値をピボットに選ぶような不運が続くと、各段階で 1 要素しか除去できず O(n²) になる
- 最悪の場合でも線形時間を保証するには、quickselect に十分に良いピボットを線形時間で与える必要がある
- このピボット選択アルゴリズムは 1973 年に Blum, Floyd, Pratt, Rivest, Tarjan によって開発され、関連論文は 1973 paper にある
median-of-medians によるピボット選択
- median-of-medians は quickselect が使う良いピボットを選ぶ手順である
- 実装の流れは次のとおり
- 要素数が 5 未満なら既存のソートベース中央値関数を使う
- リストを 5 個ずつのグループに分ける
- 5 個に満たない不完全なグループは単純化のため捨てる
- 各グループをソートし、インデックス 2 の中央値を集める
- 集めた中央値リストから再び中央値を見つけ、ピボットとして返す
- 各グループのサイズは固定の 5 個なので、グループごとのソートは定数時間として扱え、全体では O(n) の作業である
- 中央値たちの中央値を見つける再帰呼び出しは、サイズ
n/5 の部分問題として解析に含まれる
なぜ少なくとも 30% を除去できるのか
- 5 個組のグループをソートして列として並べ、各列の中央値をさらにソートして中央値たちの中央値を選ぶと考えると、ピボットの質を分析できる
- ピボットが可能な限り前方に偏る最悪の場合でも、特定の象限の要素はピボットより小さいか大きいかが保証される
- 各列から 3 要素を取り、列の半分を考えると、少なくとも
3/5 * 1/2 * n = 3/10 n 個の要素を除去できる
- 除去保証比率: {p:30}
- 全体の実行時間は次の漸化式で表せる
T(n) = n + T(n/5) + T(7n/10)
- ここで
n は分割処理、T(n/5) は median-of-medians の計算、T(7n/10) は quickselect の再帰探索に対応する
- この漸化式には再帰項が 2 つあるため単純なマスター定理は適用できず、帰納法が直感的な証明方法になる
組み合わせた結果: 線形時間で中央値を見つける
- quickselect は十分に良いピボットが与えられれば、中央値を線形時間で見つけられる
- median-of-medians は quickselect に必要な良いピボットを O(n) で選べる
- 2 つのアルゴリズムを組み合わせると、中央値またはリストの n 番目の要素を 線形時間 で見つけるアルゴリズムになる
実際の実装での選択
- 実運用では、ランダムなピボット選択でほぼ常に十分である
- median-of-medians も線形時間だが、実際にはピボット計算コストが大きく遅くなることがある
- C++ 標準ライブラリは introselect を使っており、heapselect と quickselect を組み合わせ、O(n log n) の上界を持つ
- introselect は通常は高速だが上界の悪いアルゴリズムから始め、効果的なピボットを選べないときには、より遅いが上界の良いアルゴリズムへ切り替える
- quickselect 関数が調べた要素数の比較では、決定的ピボットはランダムピボットよりほぼ常に少ない要素しか考慮しなかったが、この比較には median-of-medians の計算コストは含まれていない
- 2017 年に出た new paper は、median-of-medians アプローチを他の選択アルゴリズムと競争可能にする内容を扱っている
1件のコメント
Hacker Newsのコメント
約4年前にいくつかの中央値アルゴリズムを比較したのですが、記事が予想よりずっと長くなりました :)
https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/
10〜15年前、複数キロバイトのログ項目からパースした数十億個の値の中央値を定期的に求める必要がありました。当時、大規模処理にはMapReduceを使っていて、この規模のデータでは線形時間であるだけでなく、できれば単一パスで複数マシンに分散できる方式が必要でした。
データの精度と範囲が分かっていたことが役に立ちました。値は整数ミリ秒単位のタイミングなので負ではなく、90パーセンタイルが1秒よりずっと小さいことも分かっていました。
通常、中央値を求めるにはソートに近い処理が必要ですが、こうした条件ではバケットソートが可能になります。キーを整数ミリ秒のタイミング、値を出現回数とする辞書、つまりヒストグラムを作ればよいのです。
最大タイミングは分からないので辞書サイズが爆発しないよう、999msを超える値はすべて999msのバケットに入れました。すると0〜999のキーと値で、合計2000個程度の整数に制限されます。この点が一般的なバケットソートとは異なり、MapReduceで分散しても単一パスで非常に簡単に処理でき、その後ヒストグラムから中央値を取り出せばよかったのです。
10,000という数字は適当に挙げたものですが、望む信頼水準に必要なサンプル数は統計的に計算できますし、それほど巨大にはならないと思います。
私が扱った一部のシステムでは、Prometheusがレイテンシに約10秒の上限を設けているかのように振る舞っていました。そのため、その上限を超えるリクエストは実際にはもっと長くても、すべて10秒として入っていました。興味深いです。
2017年にmedian-of-mediansアプローチを他の選択アルゴリズムと競争可能にした新しい論文が出ており、論文著者のAndrei Alexandrescuが教えてくれたという追記があります。
彼は2016年に自分のアルゴリズムについての発表もしています。話が面白い人なので強くおすすめします。
There's Treasure Everywhere - Andrei Alexandrescu
https://www.youtube.com/watch?v=fd1_Miy1Clg
ソフトウェアを使う人なら、見つけられるAndreiの文章や発表をすべて聞いて読んでみることをおすすめします。この発表も本当に宝物です。
学部時代にmedian-of-medians quickselectアルゴリズムを学び、本当に印象的でした。自分で実装してみましたが、ひどく遅かったです。実行時間は線形に増えましたが、それが意味を持つにはリストに少なくとも数十億個の項目が必要でした。
この話を大学院生の友人としていたら、「遅いけれど、重要なのは未ソートのリストからO(n)時間で選択できることを証明している点なんだ。かつてはそれが可能かどうかも分からなかったし、今は可能だと分かったのだから、もっと速い線形アルゴリズムもあり得る」というようなことを言われました。
あまりに単純でありながら深い教訓だったので、危うく大学院に出願しそうになりました。その友人がこの会話を覚えているかは分かりませんが、私の教育における転換点のような瞬間でした。
「すでに何らかのアルゴリズムが存在すると分かっているのだから、より速いアルゴリズムもあり得る」とも考えられます。O(n)アルゴリズムの存在が、O(n log n)アルゴリズムの存在より強いシグナルになる理由は何でしょうか？
このアルゴリズムの定数係数は22くらいだった気がしますが、もしかすると関連アルゴリズムだったのかもしれません。
median-of-medians アルゴリズムの面白い点のひとつは、著者リストが完全にスター級だということ
Manuel Blum - 1995年チューリング賞受賞者
Robert Floyd - 1978年チューリング賞受賞者
Ron Rivest - 2002年チューリング賞受賞者
Bob Tarjan - 1986年チューリング賞受賞者であり、1982年の第1回 Nevanlinna 賞受賞者
Vaughan Pratt - このリストで唯一チューリング賞受賞者ではないが、Stanford 名誉教授で、Sun Microsystems になる前の SUN プロジェクトを率い、Sun 初期には研究責任者および Sun ロゴのデザイナーとして重要な役割を果たし、Pratt 素数性証明書のようなクールなものも数多く残している
独立したチューリング賞が4つに SPARCstation まで、この論文には全部そろっている
著者リストは確かに印象的
KMP アルゴリズムの「P」も Pratt
return l[len(l) / 2]Python の専門家ではないが、Python で
/演算子は浮動小数点数を返すのでは？ 配列インデックスに浮動小数点数を使う代わりに、整数除算の//を使わない理由は何だろう？かなり大きな配列でなければ問題にならないかもしれないが、それでもかなりコードスメルがする。Python 初心者で2つの演算子が別々にあることを知らなかったのなら見逃せるかもしれないが、記事には片方の分岐では整数除算を使い、もう片方では浮動小数点除算を使う、さらに奇妙なコードもある
def quickselect_median(l, pivot_fn=random.choice):if len(l) % 2 == 1:return quickselect(l, len(l) // 2, pivot_fn)else:return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +quickselect(l, len(l) / 2, pivot_fn))コメントが50件もあるのに誰もこれに気づいていないようで、平均的なPython コード品質に対する自分の既存の偏見がさらに強まっただけだった
浮動小数点数で配列をインデックス指定すると例外が発生するはず
擬似コードの代わりに、擬似コードのように見える実際のプログラミング言語を選んだのであり、説明用としてはおそらくちゃんと動くコードだと思う
原文は本当に面白く読んだが、「各ステップで最大要素をピボットに選ぶと O(n) ではなく O(n²) になり得る」という部分は引っかかった
敵対的入力が心配なら、データを先に O(n) でシャッフルすれば、そうした事態が強制的に起きるのを防げる。データが大きすぎてシャッフルしにくいなら、バケットがシャッフル可能なサイズまで小さくなった時点で一度だけ混ぜればよい
シャッフルしていれば、最悪ケースが実際には起こらないことを確率が保証する。誰かが「技術的には」可能だと言うなら、「技術的には」攻撃者が256ビット秘密鍵の全ビットを当てることもできる、と答えるだろう
私たちの世界は確率の上に成り立っている。すべての秘密鍵は、誰かが正確に当てることはできないという数学的な不可能性に守られている
私が読んだ限りでは、シャッフル後の quickselect は実用上 O(n)
それでも乱数を信頼できるなら、O(n) を超える実行時間になる確率は非常に低い
Floyd-Rivest もそれをやってのける。記憶が正しければ、少し効率がよい
ただし私はその仕組みを最後まで理解できなかった
https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
n 番目の要素を選ぶとき、n が非常に小さいか非常に大きいなら median-of-medians が最善ではないかもしれない
代わりに [1] のように偏ったピボットを使ったり、私が「j 番目 of k 番目」と呼んでいる方法を使えたりする。Floyd-Rivest も高速化できる
よく実装された quickselect と比べてスループットが1.2〜2.0倍出る趣味プロジェクトがある: https://github.com/koskinev/turboselect
高速で汎用的なインプレース選択アルゴリズムに関する資料があれば興味がある
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24
全データをメモリに保存しなくても、任意の分位数の近似値を計算できるストリーミングアルゴリズムを使うこともできる
近似計算を許容できるのか？ 誤差限界を決めるにはデータについてどんな仮定が必要か？ その仮定が有効であり続けていることをどう検証するのか？
個人的には、ストリーミング中央値近似方式を検討せざるを得ない状況になるまでは、原文に出ている quickselect アルゴリズムのほうに傾くと思う