Pythonで学ぶアルゴリズム（06/18）

　アルゴリズムを学ぶのにPythonの学習も兼ねて

Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)

を参照していく。

前回

power-of-awareness.com

4.　ソートを改良する

4.2　クイックソート

　マージソートの計算量はであり、理論上、これ以上の改善は望めない。他方でクイックソートも計算量がである。
　クイックソートは配列を小さく分割し全体をまとめることでソートを実行する方法である。

• まずと呼ばれる基準となる値を入力した配列に格納された値から適当に選ぶ（ここでは入力配列の最後の数とする。）。
• 配列全体を走査してよりも小さければ左、大きければ右へと要素を移動する。と等しい値は別配列として格納しておく。
• の左右にそれぞれ移動した値をそれぞれ新しい配列として再度クイックソートに入力する
• 最終的にできた配列を連結する

import random

######################
### クイックソート ###
######################
def quick_sort(array):
    # 空の配列はそのまま返す
    if array == []:
        return array
    
    # 最後の配列をpivotとして採用する
    p = array[-1]
    left = []
    right = []
    pivots = []
    
    # pivotとの比較で要素を分割する
    for v in array:
        if v < p:
            left.append(v)
        elif v == p:
            pivots.append(v)
        else:
            right.append(v)
    #左と右は再度関数を適用しつつ最終的に各arrayを結合する
    return quick_sort(left) + pivots + quick_sort(right)
    
# テストデータを生成
my_array = [random.randint(0,100) for i in range(15)]

print(my_array) # 見てみる
print(quick_sort(my_array))
print(sorted(my_array)) # 組み込み関数でもやってみる

4.2.1　クイックソートの計算量

　クイックソートの計算量は前述したとおりである。
　クイックソートとマージソートを比較すると、前者の方が平均的には速そうである。ただし問題がある。

########################################################
### マージソートとクイックソートの計算時間を計測する ###
########################################################

import random
import time

########################################
### パフォーマンス時間を計測する関数 ###
########################################
def perf_check(method, data, num = 3):
    s = time.time() # スタート時点
    for i in range(num):
        for v in data: method(v)
    e = time.time() # 終了時点
    return e - s

####################
### マージソート ###
####################
def merge_arrays(left, right = []):
    res = []
    i, j = 0, 0
    n, m = len(left), len(right)
    
    while i < n and j < m:
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    return res + left[i:] + right[j:]

def merge_sort(array):
    if len(array) <=1:
        return array
    mid_idx = len(array) // 2
    left = array[:mid_idx]
    right = array[mid_idx:]
    
    return merge_arrays(merge_sort(left),merge_sort(right))

######################
### クイックソート ###
######################
def quick_sort(array):
    # 空の配列はそのまま返す
    if array == []:
        return array
    
    # 最後の配列をpivotとして採用する
    p = array[-1]
    left = []
    right = []
    pivots = []
    
    # pivotとの比較で要素を分割する
    for v in array:
        if v < p:
            left.append(v)
        elif v == p:
            pivots.append(v)
        else:
            right.append(v)
    #左と右は再度関数を適用しつつ最終的に各arrayを結合する
    return quick_sort(left) + pivots + quick_sort(right)

# サンプルデータを100作成する
sample_data = []

for i in range(100):
    sample_data.append([random.randint(0, 5000) for i in range(2000)]) # 長さ2000で各要素が0から5,000の整数から無作為に得られたもの

# パフォーマンス時間を実測する
print(perf_check(merge_sort, sample_data))
print(perf_check(quick_sort, sample_data)) # quick sortの方が高速な様子

# しかし、既にソートされたデータは上手くいかない
sorted_data = []
for i in range(100):
    sorted_data.append(sorted([random.randint(0, 5000) for i in range(2000)]))

print("ソート済みのデータを再度ソートさせると…")
print(perf_check(merge_sort, sorted_data))
print(perf_check(quick_sort, sorted_data)) # quick sortの方が圧倒的に遅い

4.2.2　pivotの選び方

　予めソートしたデータでは、クイックソートのパフォーマンスが大きく劣化した。これはを配列の末尾にしたことで分割が上手くいかなかったことが原因になっている。実際、完全にソートされたデータを入力すると、以外の全要素を格納した配列とに分割され、前者がさらにクイックソートされ…という流れで、最終的に

という計算量になる。そこでの取り方を改良してみる。

import random

def quick_sort(array):
    if not array:
        return array
    p = random.choice(array)
    left = []
    right = []
    pivots = []
    
    # pivotとの比較で要素を分割する
    for v in array:
        if v < p:
            left.append(v)
        elif v == p:
            pivots.append(v)
        else:
            right.append(v)
    #左と右は再度関数を適用しつつ最終的に各arrayを結合する
    return quick_sort(left) + pivots + quick_sort(right)

perf_check(quick_sort, sorted_data)

4.2.3　クイックソートが与える示唆

　クイックソートはランダムな要素を含めることでパフォーマンスを改善できた。このようにアルゴリズムの実行にランダムな要素を含むものを乱択アルゴリズムという。
　この結果を踏まえると、常に決まった選択肢ではなくその都度別の選択肢を選べるような計算方法では、計算が早く終わる可能性がある。

次回

power-of-awareness.com