2012年9月13日木曜日

Pythonでクイックソート実装

Scipyを学習するためのノートPython Scientific lecture notesというものが公開されています。英語版pdfはこちらの右上にあるDownloadsのところにあるpdfへのリンクを、日本語版pdfはこちらの上部にある印刷用のダウンロード書かれた横のpdfへのリンクをクリックすると読むことができます。ただし、(記事執筆時点では)日本語版は最新版ではないようです。

本日は英語版のノート24ページにある、Wikipediaのクイックソートの説明文(擬似コード)を実際のプログラムに変換せよという問題を解いてみました。以下、私の解答です。

# -*- encoding: utf-8 -*-

def quick_sort(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot = array.pop(len(array)/2)
    less = []
    greater = []
    for x in array:
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

ピボットの選び方は簡単のため、リストの中央の位置にある値にしていますが、それ以外にも方法があります。例えば、中央の位置と両端の3つの値に対する中央値をピボットにするという方法があります。これは、クイックソートの性能はピボットの選び方に依存するためです。

極端ではありますが、毎回ピボット以下の値になるグループのデータ数が0、ピボットより値が大きいグループのデータが残り全部となった場合に効率が悪くなります。この場合、ソートのオーダはデータ数をnとしたときO(n^2)になります(1個ずつソート済になるため、バブルソートなどのソートと同じ程度の計算量になる)。クイックソートのオーダは平均してO(n*log(n))となるので、nが大きいとき非効率になってしまいます。

データを大きいもの、小さいもので半分ずつに分けられるようなピボットを選ぶのが理想的なのですが、データを大量に利用してピボット選択の計算をすること自体にも時間がかかってしまいます。このようなときは、ソートしたいデータの性質に依存したピボット選択を考えましょう。例えば、ほぼ昇順であるが、数パーセントのノイズが入ってくるデータの場合は、数パーセントのノイズには目をつぶって、中央の位置にある値(=ほぼ中央値と期待される)をピボットにするという方針を選ぶことが考えられます。

2012年9月14日追記

データの破壊はないほうがよいということなので、popメソッドを利用しない方針で書き直してみました。

# -*- encoding: utf-8 -*-

def quick_sort2(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot_pos = len(array)/2
    pivot = array[pivot_pos]
    less = []
    greater = []
    for idx, x in enumerate(array):
        if idx == pivot_pos: continue
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

7 件のコメント:

  1. popを引数に直接使うのは危険なので避けた方がよさそう。


    x = [3, 1, 4, 1, 5, 9]
    print quick_sort(x)
    print x

    実行結果

    [1, 1, 3, 4, 5, 9]
    [3, 1, 4, 5, 9] # 1が抜けてる!

    こうするとquick_sort実行後にxの中身が書き換えられていることがわかる。

    返信削除
  2. 「select and remove a pivot value pivot from array」
    と問題文に書いているので、removeをpopと解釈して実装した結果がこれだよ!
    というわけです。データの破壊を避けるのであれば、上の追記のように
    書くのが手軽な修正でしょうか。

    返信削除
  3. 一方ロシアは一旦引数のコピーを作ってからpopした

    返信削除
  4. 一番手軽な修正はそっちだよね。
    コピー作るとメモリ余分に喰いそうだから止めたけど。

    返信削除
  5. できた。Python2系では動作確認してないけど、ちょっといじるだけでいけるはず。

    def qsort(xs):
    if len(xs) < 2:
    return xs
    [p, xs] = [xs[0], xs[1:]]
    return qsort([x for x in xs if x < p]) + \
    [p] + \
    qsort([x for x in xs if x >= p])

    print(qsort([3, 1, 4, 1, 5, 9, 2, 6]))

    返信削除
  6. > コピー作るとメモリ余分に喰いそうだから止めたけど。
    ところがどっこい、Pythonのlistはlinked listなので、二番目以降を作り出してるようで実は二番目への参照を保持してるだけなので、実はメモリ消費量はリストの長さnに対してO(n)ではなくO(1)で済むと思う。

    返信削除
  7. qsort関数はPython2.7.3ではインデント直すだけで動作しましたよ。

    最初にしようとしていた修正は上のコードに対し、
    def quick_sort(ary):
    array = ary[:]
    (以下同じ)
    とすることでしたが、このコピーは参照ではないですよねと
    いうことが言いたかったのです。
    コメントにqsort関数の中に出てくるxs[1:]は参照でしょうけれど。

    a = range(5)
    b = a[:]
    b[2] = 100
    print a, b # bの変更はaに反映されない

    返信削除

フォロワー

ページビューの合計