Selecting median using Quick Select Algorithm(2)

先日のエントリに引き続き、Quick Selectアルゴリズムについて考えてみたいと思います。

Quick Selectアルゴリズムを考えるに至った動機は、メディアンを選択することでした。今回は以下の9個の要素を持つ配列を使って考えてみましょう。

ここでは、配列のインデックスが0番から始まるものとします。メディアンは整列が済んだ配列の4番目の要素になるはずです。

試しに整列を行った配列にインデックスを付けてみましょう。

このデータのメディアンは50だということが分かります。

さて、Quick SelectはQuicksortの分割部分のアルゴリズムを利用します。まずは、先日のエントリと同じようにQuicksortを用いて整列をしてみます。Quick Selectはその後で考えてみましょう。

まず、ピボットを選択します。ピボットの選択には、アルゴリズム Cで解説されているのと同様、一番右側の要素を選択します。ピボットは赤色で表します。

次に、ピボットより大きい値を薄い灰色で、また、小さい値を濃い灰色で可視します。

Quicksortでは、配列の最も左側から右側に向けピボットの値より大きい値を検索し、ピボットの一つ左側の要素から左側に向けピボットより小さい値を検索するのでした。今回の例では、まず77と10が検索されます。これらの値にマークを付けます。

マークが示す値を比較します。大きな値が小さな値の左側にあるのは分割の終了条件に反するため、値を交換します。

値の入れ替えが終了するまで、これを繰り返します。最後に、より大きい値であることを示すマークが付いた値とピボットの値を入れ替えます。これで、分割は終了です。

さらに、ピボットの左右のデータをそれぞれ再帰的に整列します。

再帰的に整列を行う必要がなくなるまで、分割と再帰を繰り返します。再帰をする必要がなくなれば、Quicksortは終了し、配列も整列されているはずです。

なるほど、確かにデータは整列されており、配列の4番目の要素、すなわちメディアンは50であることが分かりました。

しかし、メディアンを求めるためには、全ての要素を整列する必要があるのでしょうか。データのながれをじっくり眺めてみると、メディアンの値が確定しているのは全ての要素の整列が終了するのに比べ随分と前のようです。

また、左側中段にて行われている10と14の値の比較や交換も、メディアンを選択するのには必要がなさそうです。そのような比較や交換、および再帰を半透明として可視してみましょう。

なるほど、分割が終了した後に、以下の条件で再帰的に整列を行えば、目的の要素を選択する以外の余分な操作を防ぐことが出来そうです。

分割の最後に交換されたピボットの位置が目的の要素の位置である場合は、再帰しない
分割の最後に交換されたピボットの位置が目的の要素の位置より右側である場合は、左側のデータを再帰的に処理する
分割の最後に交換されたピボットの位置が目的の要素の位置より左側である場合は、右側のデータを再帰的に処理する

上述のように、ピボットと目的の要素の位置の関係を元に、部分的にQuicksortを適用するアルゴリズムがQuick Selectです。

さて、実装を見て行きましょう。以下はアルゴリズム Cから抜粋したQuick Selectのコードです。

select(int a[], int l, int r, int k)
{
  int i;
  if (r > l) {
    i = partition(l, r);
    if (i > l+k-1) select(a, l, i-1, k);
    if (i < l+k-1) select(a, i+1, r, k-i);
  }
}

この関数は値を返しません。多分に、以下のような用法を想定して設計されていると思われます。

  k = (N-1)/2;
  select(a, 0, N-1, k);
  median = a[k];

先日のエントリにて抜粋したQuicksortの用法と比較すると、この関数の設計意図がより明確になります。

  k = (N-1)/2;
  quicksort(a, 0, N-1);
  median = a[k];

なるほど、select()関数はk番目に小さい要素を見つけるのに特化したソート関数として設計されているのでした。破壊的であり、副作用として不完全な整列を行ってしまう関数ですので、この仕様のほうが分かりやすいですね。

さて、ここまでに効率のよいメディアン選択法を求め、Quick Selectアルゴリズムを考えて来ました。また、Quick Selectを考えるために、Quicksortを考えて来ました。

さて、このアルゴリズムは組み込みのsort()関数を利用したメディアンの選択に比べ、本当に速いのでしょうか? C言語にて実装した場合はそこそこの性能が出るのではないかと期待出来ますが、LL言語の場合は組み込み関数のsort()に比べ、どの程度の性能を発揮するのでしょうか?

実際にQuick SelectとQuicksortをPythonにポートして、検証してみました。以下がQuick Selectのコードです。

def partition(a, l, r, key):
    v = key(a[r])
    i, j = l - 1, r
    while True:
        i, j = i + 1, j - 1
        while key(a[i]) < v:
            i += 1
        while key(a[j]) > v:
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
    a[i], a[r] = a[r], a[i]
    return i

def quickselect(a, l, r, k, key=None):
    if r > l:
        if key is None:
            key = lambda x: x
        i = partition(a, l, r, key)
        if k < i:
            quickselect(a, l, i-1, k, key)
        else:
            quickselect(a, i+1, r, k, key)

10から100000個の配列を100回ずつ生成し、quickselect()関数と組み込みのsort()関数を用いて時間を計測します。配列は、同一の乱数シードを用いて生成しています。折角なので、非破壊的なsorted()関数と以下のquicksort()関数も計測してみました。

def quicksort(a, l, r, key=None):
    if r > l:
        if key is None:
            key = lambda x: x
        i = partition(a, l, r, key)
        quicksort(a, l, i-1, key)
        quicksort(a, i+1, r, key)

結果は以下の通りです。X軸は対数座標としています。今回作成したpartition()関数は最適化していないことを考慮に入れたとしても、散々な結果です。quickselect()関数を用いた結果は組み込みのsort()関数の1.2倍ほど遅く、quicksort()関数に至っては4倍弱遅い結果となっています。