コムソート（Comb Sort）で出てくる"1.3"について実験

はじめに

有名なソートアルゴリズムの1つにバブルソートの改良版であるコムソートというものがあります。これは大雑把にいうと、最初は離れた場所同士で大小関係の比較と入れ替えを行い、徐々にその幅を狭めていくという方法です。
このコムソートのアルゴリズムはWikipediaによると以下の通りです。

1. 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。
2. i=0 とする。
3. i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。
4. i=i+1 とし、i+h>n となるまで3を繰り返す。
5. hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。
6. h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。

この1.3は間隔hを更新していく速さを決めるものになっていますが、「どうして1.3がここで出てくるんだ？」という疑問が浮かんだため、英語版Wikipediaを見ると、

The shrink factor has a great effect on the efficiency of comb sort. k = 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with 1 gap size.

と書かれています。
どうやらこれは実験的に1.3が良いとされたようですが、実際に試してみないと納得がいかないので実験してみることにしました。
結論から言うと（実験した範囲では）、コムソートで間隔を小さくしていく速さを決めるパラメータ（以下shrink_factor）は1.3あたりが良さそうです。

縦軸：長さ1000のリスト100個をソートするのにかかった合計時間の中央値（Run：5回）
横軸：shrink_factor

実験方法

実験条件

以下の条件でJupyterLabを用いて実験を行いました。

• CPU：i7-9750H
• メモリ：16GB
• OS：Windows 10 Pro
• Pythonバージョン：3.8.6

実験手順

shrink_factorがコムソートの性能に与える影響について調べるために以下の手順で実験を行いました。
なお、ランダムシードを設定することで再現性の取れるように注意しました。

1. 長さ1000のリストを100個用意する。
2. それらのリストにコムソートを適用し、その実行にかかった合計時間を求める。
3. 以上1・2をshrink_factorを1.01～2の範囲で変化させながら実行する。
4. 以上1～3のRunを5回繰り返す。

プログラムと実験結果

コムソートする関数の実装

こちらを参考に実装しました。ソート対象のリストとshrink_factorを指定することでコムソートできます。

import random  # ソートするリストの生成・ランダム化のために利用
import time  # 時間測定用
import pandas as pd  # 測定データ保存用
import seaborn as sns  # データ可視化用


def get_new_gap(old_gap: int, shrink_factor: float) -> int:
    """shrink factorを指定してgapを更新していくための関数。新しいgapを返す。

    Args:
        old_gap (int): 更新元のgap
        shrink_factor (float): gapをどの速さで小さくしていくのかを決めるパラメータ

    Returns:
        int: 更新されたgap
    """
    new_gap = int(old_gap / shrink_factor)
    if new_gap < 1:
        new_gap = 1
    return new_gap

def comb_sort(numbers: list, shrink_factor: float) -> list:
    """コムソートをする関数

    Args:
        numbers (list): ソートしたい数の入ったリスト
        shrink_factor (float): コムソートのgapを更新する速さを決めるパラメータ。1.3が良いらしい。

    Returns:
        list: ソートされたリスト
    """
    length = len(numbers)
    gap = length
    is_swapped = True
    while gap != 1 or is_swapped:  # gapが1かつis_swappedがFalseになるまで実行
        is_swapped = False
        for i in range(0, length - gap):
            if numbers[i] > numbers[i + gap]:
                numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
                is_swapped = True
        gap = get_new_gap(old_gap=gap, shrink_factor=shrink_factor)
    return numbers

コムソートの実行と測定

measurement_reult = pd.DataFrame(columns=['run', 'shrink_factor', 'time [ms]'])
random.seed(0)
shrink_factors = [(101 + 1 * i) / 100 for i in range(100)]  # shrink_factorは1.01～2で0.01刻み
random.shuffle(shrink_factors)  # 実行順序による影響をなくすためにshrink_factorsをシャッフルする。

for run in range(1, 6):  # 何らかの外部要因で変な結果出ると嫌なのでとりあえず5回実行させてみる。
    for shrink_factor in shrink_factors:
        # 各shrink_factorに対して、長さ1000のリスト*100をソートする時間の合計を求める。
        start = time.perf_counter()
        for j in range(100):
            random.seed(j)
            list_to_sort = [random.randint(0, 1000) for k in range(1000)]
            comb_sort(numbers=list_to_sort, shrink_factor=shrink_factor)
        end = time.perf_counter()
        time_from_start_to_end = end - start  # 合計実行時間
        measurement_reult = measurement_reult.append({'run': run,'shrink_factor': shrink_factor, 'time [ms]': time_from_start_to_end},
                                                     ignore_index=True)  # データフレームに測定結果追加

データ加工と可視化

measurement_reult

	run	shrink_factor	time [ms]
0	1.0	1.24	0.280547
1	1.0	1.09	0.421184
2	1.0	1.12	0.353121
3	1.0	1.08	0.455735
4	1.0	1.49	0.634345
...	...	...	...
495	5.0	1.34	0.313309
496	5.0	1.06	0.528426
497	5.0	1.54	0.854932
498	5.0	1.98	3.089549
499	5.0	1.50	0.658193

500 rows × 3 columns

このようなデータが得られたのでseabornで可視化します。

sns.lineplot(x='shrink_factor', y='time [ms]', hue='run', data=measurement_reult)

理想的にはこれら5本の折れ線は重なるはずなのですが、何らかの原因で異常に時間のかかってしまっているところがあるので各Runの中央値を求めてプロットします。

med_measurement_result =  measurement_reult.groupby(['shrink_factor'], as_index=False).median()[['shrink_factor', 'time [ms]']]  # 中央値を出す
med_measurement_result

	shrink_factor	time [ms]
0	1.01	1.747783
1	1.02	1.221213
2	1.03	0.849773
3	1.04	0.713759
4	1.05	0.612795
...	...	...
95	1.96	3.000026
96	1.97	3.111335
97	1.98	3.124569
98	1.99	3.241803
99	2.00	3.888293

100 rows × 2 columns

sns.lineplot(x='shrink_factor', y='time [ms]', data=med_measurement_result)

確かにshrink_factor=1.3のあたりで一番良い結果が出ています。

おわりに

今回はshrink_factorを1.01から2まで0.01刻みで変化させてshrink_factorがコムソートの性能にどのような影響を与えるのかを調べることができました。
実験的に1.3あたりが良さそうというのは納得できたのですが、少し気持ち悪いので理論的な裏付けの載ってるものがあればお教えください。

参考文献

• コムソートについて
  • コムソート（Wikipedia）
  • Comb sort (Wikipedia)
• コムソートの実装について
  • Comb Sort (GeeksforGeeks)
• 実行時間の計測について
  • Python 実行時間計測メモ（Qiita）