この記事は自動翻訳されたものであり、原文は英語です。 原文を読む
なぜソートはこれ以上高速化できないのか
100個のものをソートするには、少なくとも525回の比較が必要です。今日のアルゴリズムに限った話ではありません。これから先も決して変わることはありません。
性能に関する主張のほとんどは、特定のプログラムに関するものです。しかし、今回の主張は違います。誰が書いたものであろうと、どのような言語であっても、まだ発明されていないいかなるハードウェア上であっても、比較に基づくソートアルゴリズムである限り、100個の要素を525回未満の比較でソートすることはできない、と主張しているのです。
この議論では、アルゴリズムの中身を一切検討しません。
ステップ数ではなく、行き先の数を数える
互いに異なるn個の要素からなるリストは、n!通りの順序に並べ替えることができます。そのうちソートされているのは正確に1つだけであり、処理を開始する前には、自分がどれを手にしているのか知る術はありません。
ここで、1回の比較によって何が得られるかを考えてみましょう。aがbより前に来るかどうかを問い、YesかNoの答えを受け取ります。つまり1ビットの情報です。アルゴリズムが次に何を行うにしても、それは以前よりも1つ多くの二進事実を知った状態で行われます。
したがって、c回の比較を行った後にはcビットの情報を受け取ったことになり、cビットの情報で区別できる異なる状況は高々2c通りです。最初に与えられたのがn!通りの並び順のうちどれであったかを確実に特定するには、以下を満たす必要があります。
2c ≥ n!、すなわちc ≥ log₂(n!)です。
証明はこれで全てです。ここにはループも再帰も戦略に関する仮定も含まれていません。だからこそ、まだ誰も思いついていないアルゴリズムにも正確に適用されるのです。
この証明の標準的な名称は「決定木による下限（decision-tree bound）」です。あらゆる比較ソートを1つの木として思い描いてみてください。各内部ノードは比較、各枝は2つの答えのいずれか、そして各葉はあり得る並び順を表します。深さcの木が持つ葉の数は高々2c個であり、木は少なくともn!個の葉を持たなければならないため、その深さは少なくともlog₂(n!)となります。深さとは、最悪の場合の比較回数のことです。
実際の数値はどうなるか
12個の要素は479,001,600通りの並び順に配置できます。その対数は28.84であるため、12個の要素には少なくとも29回の比較が必要です。100個の要素には少なくとも525回が必要です。100万個の要素には少なくとも18,488,885回が必要です。
Big-O Complexity Explorerを開き、N = 100の行を見てみましょう。O(N log N)の列には664と表示されており、これはO(N)の100とO(N²)の10,000の間に位置しています。この664という数値はN × log₂Nであり、ソートにおいて最適と呼ばれる増加率を示しています。
しかし、理論上の下限は525であり、664はそれを26.6%上回っています。
この差はツールの粗雑さによるものではありません。log₂(n!)はn log₂ nと完全に一致するわけではありません。スターリングの近似によればn log₂ n − 1.4427nとなり、N = 100のとき、この補正項目は139回の比較に相当します。したがって、「N log N」は全体の正しい形状を示してはいるものの、入力サイズの定数倍だけ真のコストを過大評価していることになります。Nが大きくなるにつれて残るのはその「形状」であり、実際に数えたときに気づくのがこの139です。
抜け穴ではない出口
カウンティングソート（計数ソート）は、100万個の小さな整数を1800万回よりも遥かに少ない操作回数でソートできますが、上記の説明と何ら矛盾するものではありません。
先ほどの証明は、投げかける問いがすべて「比較」であることを前提としています。カウンティングソートは異なる種類の問いを発します。キーを読み取り、それをアドレスとして利用するのです。これにより一度に1ビットを遥かに超える情報を抽出できます。なぜなら、比較モデルが前提とすることを拒む事実——すなわち、キーが内部を参照可能な小さな整数であるということ——を利用しているからです。
これは役に立つ習慣です。下限とは常にモデル内での下限であり、ある結果が破られたように見えたときは、前提となるモデルが変更されているのです。Sorting Raceは比較に基づくアルゴリズム同士を競わせるツールですが、それらを分かつのは定数倍の因子やメモリの挙動であり、指数ではありません。それらはすべて、同じ525という下限によって制限されています。
以前どこかで出会った概念
この数え上げの手法に見覚えがあるとすれば、それはなぜあらゆるファイルを圧縮できる圧縮プログラムは存在しないのかの背後にある手法と同じです。あちらでは、あり得るファイルとそれより短いファイルとの数え上げを行っていました。こちらでは、あり得る並び順とあり得る回答シーケンスとの数え上げを行っています。どちらの証明も、結果の集合がそれを説明できるものの集合よりも大きいことに注目することで成り立っています。
Entropy Codingは、反対の方向から見た同じ量を表しています。本当に必要なビット数は残された可能性の数によって決まり、これを超える符号化は存在しません。
どちらの結果も、高速なプログラムの書き方を教えてくれるわけではありません。探索をどこでやめるべきかを教えてくれるのです。