前書き

この記事では、quadsortと呼ばれる安定した非再帰的な適応マージソートアルゴリズムについて説明します。

四重交換

Quadsortは、4つの交換に基づいています。従来、ほとんどの並べ替えアルゴリズムは、2つの変数が3番目の一時変数を使用して並べ替えられるバイナリ交換に基づいています。通常は次のようになります。

    if (val[0] > val[1])
    {
        tmp[0] = val[0];
        val[0] = val[1];
        val[1] = tmp[0];
    }

4重交換では、4つの置換変数（スワップ）を使用してソートが行われます。最初のステップでは、4つの変数が部分的に4つのスワップ変数にソートされ、2番目のステップでは、完全に4つの元の変数にソートされます。





このプロセスは上の図に示されています。



ソートの最初のラウンドの後、1つのifチェックにより、4つのスワップ変数が順番にソートされているかどうかが判別されます。その場合、交換はすぐに終了します。次に、スワップ変数が逆の順序でソートされているかどうかを確認します。その場合、ソートはすぐに終了します。両方のテストが失敗した場合、最終的な場所がわかっており、最終的な順序を決定するために2つのテストが残っています。



これにより、順序付けられたシーケンスの1つの冗長な比較が排除されます。同時に、ランダムシーケンスに対して1つの追加の比較が作成されます。ただし、現実の世界では、真にランダムなデータを比較することはめったにありません。したがって、データが乱雑ではなく順序付けられている場合、この確率のシフトは有益です。



無駄なスワップを排除することにより、全体的なパフォーマンスも向上します。Cでは、基本的な4倍スワップは次のようになります。

    if (val[0] > val[1])
    {
        tmp[0] = val[1];
        tmp[1] = val[0];
    }
    else
    {
        tmp[0] = val[0];
        tmp[1] = val[1];
    }

    if (val[2] > val[3])
    {
        tmp[2] = val[3];
        tmp[3] = val[2];
    }
    else
    {
        tmp[2] = val[2];
        tmp[3] = val[3];
    }

    if (tmp[1] <= tmp[2])
    {
        val[0] = tmp[0];
        val[1] = tmp[1];
        val[2] = tmp[2];
        val[3] = tmp[3];
    }
    else if (tmp[0] > tmp[3])
    {
        val[0] = tmp[2];
        val[1] = tmp[3];
        val[2] = tmp[0];
        val[3] = tmp[1];
    }
    else
    {
       if (tmp[0] <= tmp[2])
       {
           val[0] = tmp[0];
           val[1] = tmp[2];
       }
       else
       {
           val[0] = tmp[2];
           val[1] = tmp[0];
       }

       if (tmp[1] <= tmp[3])
       {
           val[2] = tmp[1];
           val[3] = tmp[3];
       }
       else
       {
           val[2] = tmp[3];
           val[3] = tmp[1];
       }
    }

アレイを4つの部分に完全に分割できない場合、1〜3個の要素のテールは、従来のバイナリ交換を使用してソートされます。



上記の4重交換は、quadsortで実装されます。

4重マージ

最初の段階で、4重交換は、上記のように、アレイを4要素ブロックに事前にソートします。



第2段階では、順序付きおよび逆順を検出するために同様のアプローチを使用しますが、4、16、64、またはそれ以上の要素のブロックでは、この段階は従来のマージソートのように処理されます。



これは次のように表すことができます。

main memory: AAAA BBBB CCCC DDDD

swap memory: ABABABAB  CDCDCDCD

main memory: ABCDABCDABCDABCD

最初の行は、4つのスワップを使用して、それぞれ4つのソートされた要素の4つのブロックを作成します。2行目は、クワッドマージを使用して、それぞれスワップメモリ​​内の8つのソートされたアイテムの2つのブロックに結合します。最後の行では、ブロックがマージされてメインメモリに戻され、16個のソートされた要素の1つのブロックが残ります。以下は視覚化です。







これらの操作では、実際にはスワップメモリ​​を2倍にする必要があります。これについては後で詳しく説明します。

スキップ

もう1つの違いは、マージ操作のコストが増加するため、4つのブロックが順方向か逆方向かを確認することが有益であるということです。



4つのブロックが順番に並んでいる場合は、意味がないため、マージ操作はスキップされます。ただし、これには追加のifチェックが必要であり、ランダムにソートされたデータの場合、ブロックサイズが大きくなるにつれて、このifチェックの可能性はますます低くなります。幸いなことに、チェックが各サイクルで4倍になる場合、この頻度は4倍になりますが、潜在的なメリットは各サイクルで4倍になります。



4つのブロックの順序が逆の場合、安定したインプレーススワップが実行されます。



4つのブロックのうち2つだけが順序付けられているか、逆の順序である場合、マージ自体の比較は不要であり、その後省略されます。データをスワップメモリ​​にコピーする必要がありますが、これは計算手順が少なくなります。



これにより、quadsortアルゴリズムは、n比較ではなくn * log n比較を使用して、シーケンスを順方向および逆方向の順序でソートできます。

境界チェック

従来のマージソートのもう1つの問題は、不要な境界チェックにリソースを浪費することです。次のようになります。

    while (a <= a_max && b <= b_max)
        if (a <= b)
            [insert a++]
        else
            [insert b++]

最適化のために、アルゴリズムはシーケンスAの最後の要素をシーケンスBの最後の要素と比較します。シーケンスAの最後の要素がシーケンスBの最後の要素よりも小さい場合、b < b_maxシーケンスAが最初に完全にマージされるため、テストは常にfalseであることがわかります。



同様に、シーケンスAの最後の要素がシーケンスBの最後の要素より大きい場合、テストa < a_maxは常にfalseであることがわかります。次のようになります。

    if (val[a_max] <= val[b_max])
        while (a <= a_max)
        {
            while (a > b)
                [insert b++]
            [insert a++]
        }
    else
        while (b <= b_max)
        {
            while (a <= b)
                [insert a++]
            [insert b++]
        }

フュージョンテール

65要素の配列をソートすると、最後に64要素のソートされた配列と1要素のソートされた配列になります。シーケンス全体が正常である場合、これによって追加のスワップ（交換）操作が発生することはありません。いずれの場合も、このために、プログラムは最適なアレイサイズ（64、256、または1024）を選択する必要があります。



もう1つの問題は、アレイのサイズが最適でないために、不要な交換操作が発生することです。これら2つの問題を回避するために、ブロックサイズがアレイサイズの1/8に達すると、4重マージ手順が中止され、残りのアレイはテールマージを使用してソートされます。テールフュージョンの主な利点は、パフォーマンスに大きな影響を与えることなく、クアッドソートスワップボリュームをn / 2に減らすことができることです。

ビッグオー

データがすでに並べ替えられているか、逆の順序で並べ替えられている場合、quadsortはn回の比較を行います。

キャッシュ

quadsortはn / 2スワップを使用するため、キャッシュの使用はインプレースソートほど理想的ではありません。ただし、ランダムデータを適切に並べ替えると、交換が最適ではなくなります。私のベンチマークに基づくと、クアッドソートは、アレイがL1キャッシュをオーバーフローしない限り、インプレースソートよりも常に高速です。L1キャッシュは、最新のプロセッサでは64KBにもなる可能性があります。

ウルフソート

Wolfsortは、ランダムデータを操作する際のパフォーマンスを向上させるハイブリッドradixsort / quadsortソートアルゴリズムです。これは基本的に、符号なしの32ビットと64ビットの整数でのみ機能する概念の証明です。

視覚化

以下の視覚化は、4つのテストを実行します。最初のテストはランダム分布に基づいており、2番目は昇順分布、3番目は降順分布、4番目はランダムテールのある昇順分布に基づいています。



上半分はスワップを示し、下半分はメインメモリを示しています。色は、スキップ、スワップ、マージ、およびコピー操作によって異なります。

ベンチマーク：quadsort、std :: steady_sort、timsort、pdqsort、wolfsort

次のベンチマークは、WSL gcc構成バージョン7.4.0（Ubuntu 7.4.0-1ubuntu1〜18.04.1）で実行されました。ソースコードはチームによってコンパイルされg++ -O3 quadsort.cppます。各テストは100回実行され、最良の実行のみが報告されます。



横軸は実行時間です。









pdqsortは安定したソートではないため、通常の順序（一般的な順序）のデータでより高速に動作することに注意してください。



次のベンチマークは、WSL gccバージョン7.4.0（Ubuntu 7.4.0-1ubuntu1〜18.04.1）で実行されました。ソースコードはチームによってコンパイルされg++ -O3 quadsort.cppます。各テストは100回実行され、最良の実行のみが報告されます。675から100,000要素の範囲のアレイのパフォーマンスを測定します。



下のグラフのX軸はカーディナリティ、Y軸は実行時間です。

ベンチマーク：quadsortおよびqsort（mergesort）

次のベンチマークは、WSL gccバージョン7.4.0（Ubuntu 7.4.0-1ubuntu1〜18.04.1）で実行されました。ソースコードはチームによってコンパイルされg++ -O3 quadsort.cppます。各テストは100回実行され、最良の実行のみが報告されます。

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 ( )
            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 ( )

         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 ()
            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 ()

         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 ( )
            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 ( )

         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 ( )
            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 ( )

         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 ()
            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 ()

         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 ( )
            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 ( )

         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 ( )
            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 ( )

         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 ( )
            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 ( )

         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 ( )
            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 ( )

         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 ()
            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 ()

         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)
            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

MOは、100万アイテムに対して実行された比較の数を示します。



上記のベンチマークは、同じ汎用インターフェイスを介して、インライン化などの既知の不当な利点なしに、quadsortとglibc qsort（）を比較します。

     random order: 635, 202,  47, 229, etc
  ascending order: 1, 2, 3, 4, etc
    uniform order: 1, 1, 1, 1, etc
 descending order: 999, 998, 997, 996, etc
       wave order: 100, 1, 102, 2, 103, 3, etc
  stable/unstable: 100, 1, 102, 1, 103, 1, etc
     random range: time to sort 1000 arrays ranging from size 0 to 999 containing random data

ベンチマーク：quadsortおよびqsort（quicksort）

この特定のテストは、内部でクイックソートを使用するCygwinのqsort（）実装を使用して実行されます。ソースコードはチームによってコンパイルされgcc -O3 quadsort.cます。各テストは100回実行され、最良の実行のみが報告されます。

         quadsort: sorted 1000000 i32s in 0.119437 seconds. MO:   19308657 ( )
            qsort: sorted 1000000 i32s in 0.133077 seconds. MO:   21083741 ( )

         quadsort: sorted 1000000 i32s in 0.002071 seconds. MO:     999999 ()
            qsort: sorted 1000000 i32s in 0.007265 seconds. MO:    3000004 ()

         quadsort: sorted 1000000 i32s in 0.019239 seconds. MO:    4007580 ( )
            qsort: sorted 1000000 i32s in 0.071322 seconds. MO:   20665677 ( )

         quadsort: sorted 1000000 i32s in 0.076605 seconds. MO:   19242642 ( )
            qsort: sorted 1000000 i32s in 0.038389 seconds. MO:    6221917 ( )

         quadsort: sorted 1000000 i32s in 0.002305 seconds. MO:     999999 ()
            qsort: sorted 1000000 i32s in 0.009659 seconds. MO:    4000015 ()

         quadsort: sorted 1000000 i32s in 0.022940 seconds. MO:    9519209 ( )
            qsort: sorted 1000000 i32s in 0.042135 seconds. MO:   13152042 ( )

         quadsort: sorted 1000000 i32s in 0.034456 seconds. MO:    6787656 ( )
            qsort: sorted 1000000 i32s in 0.098691 seconds. MO:   20584424 ( )

         quadsort: sorted 1000000 i32s in 0.066240 seconds. MO:   11383441 ( )
            qsort: sorted 1000000 i32s in 0.118086 seconds. MO:   20572142 ( )

         quadsort: sorted 1000000 i32s in 0.038116 seconds. MO:   15328606 ( )
            qsort: sorted 1000000 i32s in 4.471858 seconds. MO: 1974047339 ( )

         quadsort: sorted 1000000 i32s in 0.060989 seconds. MO:   15328606 ()
            qsort: sorted 1000000 i32s in 0.043175 seconds. MO:   10333679 ()

         quadsort: sorted    1023 i32s in 0.016126 seconds.       (random 1-1023)
            qsort: sorted    1023 i32s in 0.033132 seconds.       (random 1-1023)

このベンチマークでは、クイックソートが従来のマージよりも好まれることが多い理由が明らかになり、昇順、均​​一に分散されたデータ、および降順のデータの比較が少なくなります。ただし、ほとんどのテストでは、quadsortよりもパフォーマンスが劣っていました。Quicksortは、ウェーブオーダーされたデータのソート速度も非常に遅くなります。ランダムデータテストは、小さな配列をソートする場合、quadsortが2倍以上高速であることを示しています。



Quicksortは、汎用および安定したテストで高速ですが、それは不安定なアルゴリズムであるためです。

参照：

• 「ロムトの勝利の帰還」
• 「たくさんの並べ替えの上昇」
• 「カルテシアンツリーで並べ替える」