「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

Pythonで学ぶアルゴリズム(06/18)

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

を参照していく。

4. ソートを改良する

4.2 クイックソート

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

  • まず\mathrm{pivot}と呼ばれる基準となる値を入力した配列に格納された値から適当に選ぶ(ここでは入力配列の最後の数とする。)。
  • 配列全体を走査して\mathrm{pivot}よりも小さければ左、大きければ右へと要素を移動する。\mathrm{pivot}と等しい値は別配列として格納しておく。
  • \mathrm{pivot}の左右にそれぞれ移動した値をそれぞれ新しい配列として再度クイックソートに入力する
  • 最終的にできた配列を連結する
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 クイックソートの計算量

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

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

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の選び方

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


\begin{aligned}
(n-1)+(n-2)+\cdots+1=\displaystyle{\frac{(n-1)(n-2)}{2}}=\mathcal{O}(n^2)
\end{aligned}

という計算量になる。そこで\mathrm{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 クイックソートが与える示唆

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

プライバシーポリシー お問い合わせ