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

## はじめに
有名なソートアルゴリズムの1つにバブルソートの改良版であるコムソートというものがあります。これは大雑把にいうと、最初は離れた場所同士で大小関係の比較と入れ替えを行い、徐々にその幅を狭めていくという方法です。
このコムソートのアルゴリズムは[Wikipedia](https://ja.wikipedia.org/wiki/コムソート)によると以下の通りです。
>
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](https://en.wikipedia.org/wiki/Comb_sort)を見ると、
>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あたりが良さそうです。
![med.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/213259/10c7db8f-9c46-4f91-7936-c9651d2e1687.png)
縦軸：長さ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回繰り返す。  

## プログラムと実験結果
### コムソートする関数の実装
[こちら](https://www.geeksforgeeks.org/comb-sort/)を参考に実装しました。ソート対象のリストとshrink_factorを指定することでコムソートできます。

```Python
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
```

### コムソートの実行と測定
```Python
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)  # データフレームに測定結果追加
```

### データ加工と可視化
```Python
measurement_reult
```


<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>run</th>
      <th>shrink_factor</th>
      <th>time [ms]</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>1.0</td>
      <td>1.24</td>
      <td>0.280547</td>
    </tr>
    <tr>
      <th>1</th>
      <td>1.0</td>
      <td>1.09</td>
      <td>0.421184</td>
    </tr>
    <tr>
      <th>2</th>
      <td>1.0</td>
      <td>1.12</td>
      <td>0.353121</td>
    </tr>
    <tr>
      <th>3</th>
      <td>1.0</td>
      <td>1.08</td>
      <td>0.455735</td>
    </tr>
    <tr>
      <th>4</th>
      <td>1.0</td>
      <td>1.49</td>
      <td>0.634345</td>
    </tr>
    <tr>
      <th>...</th>
      <td>...</td>
      <td>...</td>
      <td>...</td>
    </tr>
    <tr>
      <th>495</th>
      <td>5.0</td>
      <td>1.34</td>
      <td>0.313309</td>
    </tr>
    <tr>
      <th>496</th>
      <td>5.0</td>
      <td>1.06</td>
      <td>0.528426</td>
    </tr>
    <tr>
      <th>497</th>
      <td>5.0</td>
      <td>1.54</td>
      <td>0.854932</td>
    </tr>
    <tr>
      <th>498</th>
      <td>5.0</td>
      <td>1.98</td>
      <td>3.089549</td>
    </tr>
    <tr>
      <th>499</th>
      <td>5.0</td>
      <td>1.50</td>
      <td>0.658193</td>
    </tr>
  </tbody>
</table>
<p>500 rows × 3 columns</p>
</div>

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

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

![5runs.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/213259/9ebb6837-b426-6201-a3b9-5420df8cfb55.png)
理想的にはこれら5本の折れ線は重なるはずなのですが、何らかの原因で異常に時間のかかってしまっているところがあるので各Runの中央値を求めてプロットします。


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

<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>shrink_factor</th>
      <th>time [ms]</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>1.01</td>
      <td>1.747783</td>
    </tr>
    <tr>
      <th>1</th>
      <td>1.02</td>
      <td>1.221213</td>
    </tr>
    <tr>
      <th>2</th>
      <td>1.03</td>
      <td>0.849773</td>
    </tr>
    <tr>
      <th>3</th>
      <td>1.04</td>
      <td>0.713759</td>
    </tr>
    <tr>
      <th>4</th>
      <td>1.05</td>
      <td>0.612795</td>
    </tr>
    <tr>
      <th>...</th>
      <td>...</td>
      <td>...</td>
    </tr>
    <tr>
      <th>95</th>
      <td>1.96</td>
      <td>3.000026</td>
    </tr>
    <tr>
      <th>96</th>
      <td>1.97</td>
      <td>3.111335</td>
    </tr>
    <tr>
      <th>97</th>
      <td>1.98</td>
      <td>3.124569</td>
    </tr>
    <tr>
      <th>98</th>
      <td>1.99</td>
      <td>3.241803</td>
    </tr>
    <tr>
      <th>99</th>
      <td>2.00</td>
      <td>3.888293</td>
    </tr>
  </tbody>
</table>
<p>100 rows × 2 columns</p>
</div>



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

![med.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/213259/c318fb59-edd6-05e6-5844-9c0ec4b3aa91.png)
確かにshrink_factor=1.3のあたりで一番良い結果が出ています。

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

## 参考文献
- コムソートについて
    - [コムソート（Wikipedia）](https://ja.wikipedia.org/wiki/コムソート)
    - [Comb sort (Wikipedia)](https://en.wikipedia.org/wiki/Comb_sort)
- コムソートの実装について
    - [Comb Sort (GeeksforGeeks)](https://www.geeksforgeeks.org/comb-sort/)
- 実行時間の計測について
    - [Python 実行時間計測メモ（Qiita）](https://qiita.com/BlueSilverCat/items/1eddab6db0b726df21c9)