アルゴリズム・データ構造図鑑 · 基礎から応用へ

三分割で必要な順位だけを選ぶQuickselect

重複する値の順位と未調査領域を追い、配列の変更、期待線形時間、最悪の場合の費用を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 全てを並べず、順位だけを求める
  2. 同値の領域をまとめて分ける
  3. 交換後の未調査位置に注意する
  4. 期待線形時間と最悪二次時間を分ける
  5. 順位を求めた後に残る配列
  6. 分割の四領域を検査する
  7. 二つの中央順位を求める場合
  8. 同じ値の順位を数える課題
  9. この記事をロゲイアに質問する理解を確かめる

全てを並べず、順位だけを求める

配列9、2、7、2、5から、小さい順で添字2に来る値を求めます。0始まりの順位なので三番目の値で、整列すれば2、2、5、7、9となり答えは5です。Quickselectは全体を整列する代わりに、基準値より小さい領域、等しい領域、大きい領域へ分け、目的の順位を含む側だけへ進みます。答えを返しても、配列全体が整列したとは限りません。

同じ値が複数ある場合も、一つずつ順位を占めます。異なる値の三番目を求める問題なら、先に重複の意味を変える必要があります。偶数個の中央値では、中央二値の平均を求めるのか、小さい方か大きい方を返すのかを決めます。今回の実装は、一つの有効な順位kの値だけを返します。中央値という名称で入出力を曖昧にしないようにしてください。

同値の領域をまとめて分ける

基準値を5にすると、小さい側は2、2、等しい側は5、大きい側は9、7へ分けられます。小さい領域が二要素なので、順位2は等しい領域に入ります。そこにいる値は全て5なので、その時点で答えが確定します。kが0や1なら小さい側へ、3や4なら大きい側へ進みます。全体配列の添字を使い続ける実装では、右側へ進んでもkから勝手に要素数を引かないようにします。

三分割は同値が大量にある場合にも役立ちます。全て7の配列なら、一回の分割で全体が等しい領域となり、どの有効順位でも7を返せます。二分割で同値を片側へ寄せ続ける実装とは、進み方が異なります。分割処理の途中では、小さいと確定した範囲、未調査の範囲、大きいと確定した範囲を区別し、交換後にどの要素をまだ調べていないかを追います。

基準5との関係値0始まりの順位
小さい2,20,1
等しい52
大きい9,7(未整列でよい)3,4

交換後の未調査位置に注意する

コードは[lo,hi)を対象に、lt、i、gtを使います。iの値が基準より小さければltと交換して両方を進めます。大きければgtを一つ減らして交換しますが、iは進めません。右から来た値がまだ未調査だからです。等しければiだけ進めます。i=gtで未調査領域が消え、[lo,lt)が小、[lt,gt)が同値、[gt,hi)が大となります。

基準値は現在の領域から固定seedの乱数で選びます。入力配列はその場で変わるため、元の順序を残す呼出し側はコピーを渡してください。検査では各回listを作り直し、長さ1〜6の0、1、2からなる全配列の全順位をsortedと照合します。空入力や範囲外順位を正常な答えとして返さず、IndexErrorで拒否します。分割の不変条件と入出力の契約を一緒に確認します。

python
import random
from itertools import product
def select(a,k,seed=7):
    if not 0<=k<len(a):raise IndexError(k)
    rng=random.Random(seed);lo=0;hi=len(a)
    while True:
        pivot=a[rng.randrange(lo,hi)];lt=lo;i=lo;gt=hi
        while i<gt:
            if a[i]<pivot:a[lt],a[i]=a[i],a[lt];lt+=1;i+=1
            elif a[i]>pivot:gt-=1;a[i],a[gt]=a[gt],a[i]
            else:i+=1
        if k<lt:hi=lt
        elif k>=gt:lo=gt
        else:return pivot
for n in range(1,7):
    for values in product(range(3),repeat=n):
        for k in range(n):assert select(list(values),k)==sorted(values)[k]
try:select([],0)
except IndexError:pass
else:raise AssertionError('invalid rank accepted')
print('all ternary arrays lengths1..6 and every rank passed')

期待線形時間と最悪二次時間を分ける

一回の分割では、現在の領域の要素をそれぞれ処理します。基準が適度に分かれれば、進む側が小さくなり、n+n/2+n/4のような合計から線形の費用を期待できます。無作為な基準選択の解析では期待O(n)です。一方で基準が端へ偏り続ければn+(n−1)+…となり、最悪O(n²)です。固定seedで速く終わったことは、この最悪の場合が消える証拠ではありません。

今回の反復実装は深い再帰を使わず、分割も配列内で行います。ただし呼出し側で元配列を保つコピーを作れば、追加領域O(n)が別に必要です。ライブラリの選択関数には基準選択や最悪時の切替を工夫したものもありますが、その契約を確認せず、今回の小実装の保証と同一視しないでください。平均、期待、最悪のどの費用を評価しているかを説明します。

順位を求めた後に残る配列

Quickselectの返した値より左が全て完全に整列しているとは限りません。同値領域を挟んで大小の区分が分かっていても、区分の中の順番は未確定です。上位k個を取り出すだけの用途と、それらを順番に表示する用途では、後者に追加の整列が必要な場合があります。返された値だけを使う今回の関数から、配列の他の位置へ契約を勝手に広げないようにします。

順位を何度も求めるなら、毎回新しいコピーへQuickselectを実行する方法と、一度整列して以後は添字で答える方法を比較します。少数の順位か全順位か、元配列を変えられるか、最悪の応答時間が必要かで選択が変わります。データの準備やコピーを測定から外した場合は、その範囲も記録します。選択一回が整列より少ない仕事をすることと、アプリ全体が常に速いことは別の判断です。

分割の四領域を検査する

分割中は[lo,lt)が小さい、[lt,i)が等しい、[i,gt)が未調査、[gt,hi)が大きいという四領域です。大きい値を右へ交換した後、未調査の末尾から新しい値がiへ来るため、iを進めず分類します。一方小さい値をltへ交換した場合、入れ替わる位置が同値領域の境界にあることを使って二つを進めます。

完成後の三領域だけをassertしても、途中の不変条件を考えると誤りを見つけやすくなります。学習用の小入力では、各交換後に領域の大小を検査する版も作れます。ただしその検査時間を含む実行を、通常の選択ループの速度として比べないでください。機能の検証と計測用の実装条件を区別します。

選んだ値より小さい要素がk個ある必要はありません。重複値を許すためです。必要なのは、整列した列の添字kに同じ値が置かれることです。等値区間へ入った時点で止まれる理由も、この順位の契約から説明できます。

二つの中央順位を求める場合

偶数長の中央値を中央二値の平均と定義するなら、長さ6では順位2と3を求めます。同じ値が両方へ来る場合もあり、それぞれを重複込みの順位として扱います。二回選択する単純な方法でも、原配列を保持するか、最初の分割を次へ利用するかで実装が変わります。

値の型が整数でも平均は整数とは限りません。固定幅の言語で二値を足してから割ると、加算の範囲にも注意が必要です。今回の関数は中央値の丸め方まで定めていないため、呼出し側で仕様を加えます。一順位を正しく選べたことと、中央値という製品の出力を正しく作れたことを分けて検査してください。

同じ値の順位を数える課題

課題は4、1、4、2、4、3から0始まりの順位3を求め、基準4での三領域の大きさを示すことです。解答は、小さい領域が1、2、3の三要素、等しい領域が4の三要素、大きい領域は空です。順位3、4、5は全て4になります。順位3は四番目なので、重複を除いた異なる値の順位へ読み替えないでください。

追加課題では順位を2へ変えます。今度は小さい側の三要素へ進み、答えは3です。等しい側の三つを一つだけに数えると順位がずれます。最後に、空配列へ順位0を渡した場合を説明します。有効な順位が一つもないため、答えの代わりに例外を返します。入出力、三分割の区間、重複の扱い、期待と最悪の費用を揃えて説明してください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ