焔式
焔式（ほむらしき）は、マージソートを応用した、差分ソートです。
ソート済み配列に対し、値の変更を行った箇所に焦点を当て、高速にソートします。
以下の特徴があります（変更範囲をDとして）。
- 比較ソート
- 安定ソート
- 外部領域：N
- 平均時間：O((D log D) + N)
- 最悪時間：O((D log D) + N)
- 最良時間：O(D)
- 再帰：無し
リポジトリ
基本となるアルゴリズム
- ソート済み配列に対して、任意の範囲の値を変更します。
- 変更範囲を、比較安定ソートします。
- 「前方範囲、変更範囲、後方範囲」で三区画マージします。
具体的な流れ
ソート済み配列に対して、任意の範囲の値を変更します
0 2 3 4 5 6 7 9|ソート済み配列
↓ ↓ ↓
0 2|8 1 3|6 7 9|
変更範囲を、比較安定ソートします
0 2|8 1 3|6 7 9|
↓ ↓ ↓
0 2|1 3 8|6 7 9|
「前方範囲、変更範囲、後方範囲」で三区画マージします
0 2|1 3 8|6 7 9|
02 前方範囲
138 変更範囲
679 後方範囲
012 前方範囲を消費するまで、変更範囲とマージ（前方Part）
36789 変更範囲の残りと、後方範囲をマージ（後方Part）
01236789 前方Partと後方Partを連結（ソート完了）
ビルド＆テスト
検証を行った環境は以下のとおりです。
- Windows 10 Pro 64bit
- Core i7-8700 3.20GHz
颯式と刹那式が兄弟ディレクトリに存在する状態でビルドできます。
Msvc
Microsoft(R) C/C++ Optimizing Compiler Version 19.16.27027.1 for x64
cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe
clang++
clang version 8.0.0 (tags/RELEASE_800/final)
Target: x86_64-w64-windows-gnu
clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe
g++
gcc version 8.3.0 (Rev2, Built by MSYS2 project)
Target: x86_64-w64-mingw32
g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe
平均ベンチマーク
以下は、ソート済み配列に対し、ランダムな範囲を、ランダムな値に変更した場合です。
単位は秒で、数値が低いほど高速です。
Msvc
| 件数 | std::sort | std::stable_sort | 焔式 |
|---|---|---|---|
| 10,000 | 0.00031643 | 0.00016890 | 0.00014270 |
| 1,000,000 | 0.05004999 | 0.02833382 | 0.02414271 |
| 100,000,000 | 3.43509980 | 3.48550165 | 2.55574413 |
clang++
| 件数 | std::sort | std::stable_sort | 焔式 |
|---|---|---|---|
| 10,000 | 0.00027717 | 0.00020017 | 0.00015642 |
| 1,000,000 | 0.03866672 | 0.02881882 | 0.02255046 |
| 100,000,000 | 3.38201222 | 3.64178056 | 2.60998679 |
g++
| 件数 | std::sort | std::stable_sort | 焔式 |
|---|---|---|---|
| 10,000 | 0.00029155 | 0.00020019 | 0.00014887 |
| 1,000,000 | 0.04052708 | 0.02760306 | 0.02054782 |
| 100,000,000 | 3.58270940 | 3.45231729 | 2.36870185 |
特性ベンチマーク
以下は全て、「100,000,000」件でソートしました。
単位は秒で、数値が低いほど高速です。
最良ケース
ソート済み配列に対し、値を変更せずに、範囲をランダムにした場合です。
| std::sort | std::stable_sort | 焔式 | |
|---|---|---|---|
| Msvc | 0.23993706 | 1.30073792 | 0.01059685 |
| clang++ | 1.04052412 | 1.52173567 | 0.01611595 |
| g++ | 1.34400042 | 1.31273356 | 0.01510180 |
余談
如何だったでしょうか？
ソートは、常に全体で行う必要はないという観点から、差分ソートという考えに至ったアイデアです。
本来であれば、全体ソートである std::sort と std::stable_sort との比較はフェアではないのですが、差分ソートの有用性を判断していただくには必要かと思い、ベンチマークを掲載することにしました。
参考になれば幸いです。
工夫をすれば、より高速にソートできることが示せたと思います。
運用の目安としては、(D ＜ (N/2))の場合は差分ソート、そうでなければ全体ソートが良いかなという所感です。
ソートアルゴリズムには、まだ浪漫が残っています。
以下の記事も併せて読んでいただけると、より楽しめるかも知れません。