図 | 武術の観点から STL ソートアルゴリズムの秘密を探る

[[410325]]

この記事はWeChatの公開アカウント「Backend Research Institute」から転載したもので、著者はDabaiskiです。この記事を転載する場合は、バックエンド研究所の公式アカウントまでご連絡ください。

序文

今日は、STL でのソートアルゴリズムの基礎となる実装とコーディング手法を見てみましょう。

ご存知のとおり、STL はデータ構造とアルゴリズムの一般化をサポートするためにテンプレートに依存しています。一般化は C++ ユーザーにとってすでに驚きですが、STL 開発者の強力なラインナップを見ると、STL がもたらす驚きは一般化にとどまらないことがわかります。強力なパフォーマンスと効率性により、STL はさらに素晴らしいものになっています。

STL の究極のパフォーマンスの背後には、熟練プログラマーの優れたプログラミングスキルと完璧さを追求する職人精神がまさに体現されています。

私の能力の限界により、先人たちの肩を追って STL のソートアルゴリズムの背後に何が隠されているかを調べることしかできません。まるで「Into Science」のワンシーンのようですね。では、ソートアルゴリズムの旅を始めましょう。

内省的哲学

ソートアルゴリズムの実装を理解する前に、イントロスペクティブソートという概念を見てみましょう。正直に言うと、私の中国語レベルは本当に平均的で、ソートアルゴリズムで使用されるこの用語は明確ではないといつも感じているので、勉強しましょう。

イントロスペクティブソートは英語で Introspective Sort と呼ばれます。introspective という言葉は内省的な意味です。まだよくわかりません。検索を続け、この用語の Baidu Encyclopedia の説明を見てみます。

内省は心理学における基本的な研究方法の一つです。内省は自己観察とも呼ばれます。それは内部で発生し、私たち自身も認識している主観的な現象です。それは、自分自身の主観的な経験とその変化の観察であるとも言えます。

内省はまさにその主観性ゆえに、心理学の分野では古代から長年の論争の的となってきました。また、内省は自己反省とも言え、儒教が重視する自己思考でもあります。この観点から、Java イントロスペクションメカニズムや Cocoa イントロスペクションメカニズムなどのコンピュータ分野に応用できます。

わあ、内省は心理学用語だということがわかりました。これで少し理解できました。内省とは、外の世界に希望を託すのではなく、自分自身の経験と能力に基づいて、自己を振り返り、自分で考え、変化を観察し、自分の主観的な経験に基づいて調整することを意味します。

簡単に言えば、イントロスペクションアルゴリズムはデータセットを選り好みせず、ソートが時間内に保証されるように、各データセットに対応する処理方法を提供しようとします。

これを書いていると、「天剣龍驤」で張無忌が光明山で六大宗派と戦う場面が頭に浮かびます。敵がどんなに強くても弱くても、私は自分のやり方で対処します。

彼は強いので強い、そよ風が丘を越えて吹き渡る。

彼が望むままにさせておけば、明るい月が川面を照らします。

彼は残酷で邪悪だが、私には十分なエネルギーがある。

--- 達磨の『九陽経』

哲学、その通りです。分類の視点に切り替えて、内省のプロセスを見てみましょう。

私が理解する内省的ソートアルゴリズムは、外部データの品質や量に依存せず、それぞれの極端なシナリオに対する独自の対応に基づいて対応する判断と決定の調整を行い、さまざまなデータセットに適応して優れたパフォーマンスを発揮するアルゴリズムです。

内省的ソート

諺にあるように、英雄はナイフ、銃、剣、戟、斧、手斧、フック、フォークなど、多くの武器を使用します。これは、無敵の武器はなく、特定のシナリオでのみ明らかな利点があることを示しています。これは、ソフトウェアエンジニアリングに特効薬がないのと同じです。

ソートアルゴリズムに戻ると、バブルソート、選択ソート、挿入ソート、クイックソート、ヒープソート、バケットソートなど、ソートアルゴリズムは多数あります。

古いソートアルゴリズムの多くは O(n^2) ですが、優れたアルゴリズムは O(nlogn) に到達できます。ただし、nlogn であるクイックソートやヒープソートにも、それぞれ長所と短所があります。挿入ソートは、データがほぼ順序付けられている場合に O(n) のパフォーマンスを達成できます。場合によっては、競合比較ではなく、統合と革新を行う必要があります。

イントロスペクティブソートは、1997 年に David Musser によって設計されたソートアルゴリズムです。このソートアルゴリズムはクイックソートから始まり、再帰の深さが一定の深さを超えるとヒープソートに切り替わります (深さはソートされた要素の数の対数です)。David Musser は STL 分野ではよく知られた人物です。

文脈を考慮せずに、盲目的にどちらが良いか悪いかを比較するのは意味がありません。イントロスペクティブソートは、それらすべてを集大成したものです。ソートアルゴリズムが総合的に優れたパフォーマンスを実現できるように、イントロスペクティブソートアルゴリズムは、クイックソート、ヒープソート、挿入ソートを組み合わせ、現在のデータセットの特性に基づいてどのソートアルゴリズムを使用するかを選択し、各アルゴリズムが独自の長所を発揮できるようにします。このアイデアは確かに非常に刺激的です。

デプロイメントの内省的なソート

前述のように、イントロスペクティブソートは主にクイックソート、ヒープソート、挿入ソートを組み合わせたものです。では、これら 3 つのソートはどのように配置されているのでしょうか。

自分と敵を知ることで、あらゆる戦いで勝利が保証されます。まずは、3 つの分類の長所と短所を見てみましょう。

クイックソート

大量のデータの場合、順序付きか繰り返しかに関係なく、最適化されたアルゴリズムはほとんどの場合 O(nlogn) に到達できます。ヒープソートも O(nlogn) ですが、クイックソートの方がいくつかの理由で高速です。再帰が深すぎてセグメンテーションが著しく不均一な場合、O(n^2) の複雑さに退化し、パフォーマンスが低下します。これがクイックソートの欠点です。

ヒープソート

ヒープソートはクイックソートの強力な競合相手です。その最大の特徴は、O(nlogn) に到達でき、その複雑性が非常に安定していることです。クイックソートのように O(n^2) に低下することはありません。ただし、ヒープソートプロセスには多くのヒープ調整が含まれ、要素の比較はジャンプ方式で行われるため、キャッシュの局所性特性が十分に活用されません。その他の理由と同様に、ヒープソートはクイックソートよりも少し遅くなりますが、ビッグ O の複雑性は依然として同じレベルです。

挿入ソート

挿入ソートの特徴の 1 つは、トランプに似ていることです。手札のカードをソートする場合、カードがすでに整列していれば、調整はほとんど必要ありません。したがって、データ量が多くなく、ほぼ整列している場合は、挿入ソートの複雑さは O(n) にまで削減できるため、適用する価値があります。

利点と欠点は大体明らかなので、イントロスペクティブソートが実際にこれら 3 つのソートアルゴリズムをどのようにスケジュールするかを推測できます。

起動フェーズでは、ソートする要素が多数ある場合、最初にクイックソートを使用して大幅なソートを実行し、その複雑さは O(nlogn) で実行できます。
ディープステージでは、クイックソートで再帰を使用すると、スタックフレームの保存や切り替えなどの再帰操作が多くなります。パーティションの切り方が不適切で再帰が深すぎると、スタックオーバーフローによりプログラムが終了する可能性があります。そのため、クイックソート処理がO(n^2)に退化した場合、ヒープソートは劣化がなく、O(nlogn)で安定できるため、この時点で自動的に検出してヒープソートに切り替えます。
最終段階では、クイックソートとヒープソートの後、データパーティション内のソートする要素の数が特定の経験的設定値（再帰の最初の数回の呼び出しが終了しようとしていると考えることができる）よりも少ない場合、データは実際にほぼ順序付けられています。この時点で、挿入ソートを使用して効率を向上させ、複雑さをさらに O(n) に減らすことができます。

これを書き終えて、著者は次のような場面を思いつきました。

2005年春節祝賀会のスケッチ「装飾」で、黄紅と龔翰林が演じた。装飾役の黄紅は、大小2本のハンマーを持っていた。大ハンマーは80ポンド、小ハンマーは40ポンドで、大小のハンマーを切り替えることができた。

実際、ソートアルゴリズムを内省的ソートに切り替えるのと同じです。つまり、テクノロジーは生命から生まれ、生命よりも高いのです。以下は、みんなで一緒に体験できる画像です。

イントロスペクションとイントロスペクティブソートについて長々と説明してきました。皆さんはもう理解していると思いますので、実装の詳細を詳しく見ていきましょう。これがこの記事の焦点です。一緒に分析を続けていきましょう！

ソートアルゴリズムの実装の詳細

この記事で紹介したソートアルゴリズムは、SGI STLバージョンに基づいており、主に侯潔先生の著書「STLソースコード分析」に基づいています。そのため、関数のないバージョンが使用されています。専門家の傑作を一緒に鑑賞しましょう！写真は、著者がずっと前に購入したが、常に箱の底に保管していたSTLマジックブックです。

ソート機能の応用シナリオ

SGI STL のソートのパラメータは 2 つのランダムアクセスイテレータ RandomAccessIterator であり、ソートテンプレートもこの種のイテレータに基づいています。したがって、コンテナーがランダムアクセスイテレータでない場合は、一般的なソート関数を使用できない可能性があります。

基礎となる連想コンテナマップとセットはRBツリーに基づいており、すでに独自の順序を持っているため、ソートアルゴリズムを使用する必要はありません。
シーケンスコンテナリストは双方向反復子であり、ランダムアクセス反復子ではありません。Vector と deque は、ソートアルゴリズムに適したランダムアクセス反復子です。
コンテナアダプタのスタック、キュー、および優先度キューは、要素の順序を制限するコンテナであるため、ソートアルゴリズムは適用できません。

要約すると、ソートアルゴリズムは、ベクターコンテナーとデキューコンテナーの両方に適用できることがわかります。

並べ替え概要

先ほどイントロスペクティブソートを紹介しましたので、sort が introsort をどのように使用するかをステップごとに見ていきましょう。前回のエントリコードは次のとおりです。

テンプレート <class RandomAccessIterator>
インライン void sort(RandomAccessIterator first 、 RandomAccessIterator last ) {
    if (最初!=最後) {
        __introsort_loop( first 、 last 、 value_type( first )、 __lg( last - first ) * 2);
        __final_insertion_sort(最初、最後);
    }
 }

コードから、sort はソートするシーケンスの開始と終了として 2 つのランダムアクセスイテレータ (first と last) を使用し、さらに 2 つの関数 __introsort_loop と __final_insertion_sort を呼び出すことがわかります。文字通り、前者はイントロスペクティブソートループであり、後者は挿入ソートです。 __introsort_loop の 3 番目のパラメータは __lg(last - first)*2 であることに注意してください。経験に基づいて、これが再帰の深さの限界であると推測します。コード実装を見てみましょう。

テンプレート <クラスSize >
インラインサイズ__lg(サイズn){
サイズk;
 (k = 0;n > 1;n >>= 1)の場合++k;
 kを返します。
 }

このコードは、n=last-first、つまり 2^k<=n の最大の整数 k 値を意味します。

したがって、全体として、last-first=20、k=4 と仮定すると、最大セグメンテーション深度 depth_max=4*2=8 となり、first と last に基づいて再帰の最大深度を決定できます。

クイックソートとヒープソートの調整 __introsort_loop 関数は、主にクイックソートとヒープソートをカプセル化します。この関数の実装の詳細を見てみましょう。

 //ソート関数のエントリ
テンプレート <クラス RandomAccessIterator、クラス T、クラスSize >
 void __introsort_loop(RandomAccessIterator最初、
                      ランダムアクセスイテレータ最後, T*,
サイズdepth_limit) {
    while (最後-最初> __stl_threshold) {
        深さ制限 == 0 の場合
            partial_sort( first , last , last ); //ヒープソートを使用する
戻る;
        }
 --depth_limit; //分割残高を減らす 
        RandomAccessIterator カット = __unguarded_partition
          (最初、最後、 T(__median(*最初、 *(最初+ (最後-最初)/2 )、
                                   *( last - 1)))); //3点中央値分割プロセス
        __introsort_loop(cut, last , value_type( first ), depth_limit); // サブシーケンスの再帰呼び出し
last = cut; // 左のシーケンスへのイテレータ交換スイッチ
    }
 }
 //3点中央値法に基づく分割アルゴリズム
テンプレート <クラス RandomAccessIterator、クラス T>
 RandomAccessIterator __unguarded_partition(RandomAccessIterator最初、
                                           RandomAccessIterator最後、
                                           Tピボット）
 （真）の間{
    (* first < pivot) の場合 ++ first ;
 - 最後;  
    while (pivot < * last ) --last;  
    if (!(最初<最後))戻り値 初め;
    iter_swap(最初、最後);
    ++最初;
 }

めまいや混乱を感じないでください。少し分析すれば必ず理解できます。

まず、2 つのランダムアクセスイテレータのパラメータ (first と last) を確認します。3 番目のパラメータは、__lg によって計算されたセグメンテーション深度です。
このとき、while を入力して last-first の間隔サイズを決定します。__stl_threshold は 16 です。Hou Jie は、__stl_threshold のサイズは 5 ~ 20 で、具体的なサイズは自分で設定できると指摘しています。__stl_threshold より大きい場合は実行を継続し、そうでない場合は飛び出します。間隔サイズが __stl_threshold より大きい場合は、3 番目のパラメーター depth_limit が 0 かどうか、つまりセグメンテーションが深すぎるかどうかを判断します。これは、初期最大値を指定してから、各セグメンテーションごとに 1 を減算し、depth_limit=0 になるまで、partial_sort を呼び出すことと同じです。「STL ソースコード分析」の他の章から、partial_sort はヒープソートのカプセル化であることがわかります。ここで、主役の 1 つである heapsort が登場するのは少し興味深いです。
下を見続けると、depth_limit>0 なので、まだ分割の余地があるので、ワクワクしましょう。こうして __unguarded_partition にたどり着きます。この関数は、文字通りクイックソートのパーティション処理であり、カットランダムアクセスイテレータを返します。__unguarded_partition の 3 番目のパラメータ __median は、3 点中央値法を使用して基準値ピボットを取得します。この時点で、クイックソートパーティションの 3 つの要素が集められ、最後に新しいカットポイントの位置が返されます。
読み進めていけば、すぐに終わります。__introsort_loop が現れます。確かに再帰的です。ここでは再帰が 1 つだけであること、および cut と last が渡されることに特に注意してください。これらは右サブシーケンスに相当します。左サブシーケンスはどうでしょうか。読み進めようと急がないでください。last=cut は反転し、cut は左サブシーケンスの右境界になります。このようにして、左サブシーケンスの処理が始まります。

クイックソートの実装の比較

前述のように、sort でのクイックソートの記述は、これまで見てきたものとは多少異なります。「STL ソースコード分析」でクイックソートの左シーケンスの処理を見た後、Hou Jie 先生は次のように書いています。「記述が読みにくく、効率も良くありません。」これを見て、私はさらに混乱しましたが、分析してみましょう。

写真: STLソースコード解析におけるこの記述方法についてのHou Jie先生のコメント

一般的な書き方:

 // クイックソート用の一般的な疑似コード
クイックソート(arr,左,右){
    pivoit = func(arr); //ベンチマーク値を取得するには何らかの方法を使用する
    cut = partition( left , right ,pivot); // 左と右の境界と参照値を組み合わせて分割点の位置を決定します。
    quicksort(arr, left ,cut-1); // 左のシーケンスを再帰的に処理する
    quicksort(arr,cut+1, right ); // 右のシーケンスを再帰的に処理する
}

SGI STL で記述する方法:

 stl_quicksort(最初、最後){
      // 外部制御構造としてのループ
      while(ok){
         cut = stl_partition( first , last ,_median( first , last )); // パーティションを分割
         stl_quicksort(cut, last ); // 右の部分列を処理するための再帰呼び出し
last = cut; // cut をlastに割り当てることは、左の部分列に切り替えてループを継続することと同じです。
   }
 }

インターネット上の大物による記事によると、SGI STL のクイックソートの記述方法では、while ループを使用することで再帰呼び出しが半分に削減されるとのことですが、これは典型的な末尾再帰の最適化のアイデアです。

ここでは比較のためのテストコードをまだ書いていません。まずピットを取り上げて、後で比較テストを書いてからコメントします。ただし、sgi のこの書き方を見ることはできます。

ヒープソートの詳細

//注: これはカスタム比較関数を使用したヒープソートバージョンです
//ヒープとトップの操作
テンプレート <クラス RandomAccessIterator、クラス T、クラス Compare>
 void __partial_sort(RandomAccessIterator first 、 RandomAccessIterator middle 、
                    RandomAccessIterator last 、 T*、 比較 comp) {
    make_heap(最初、真ん中、comp );
 (RandomAccessIterator i = 中間; i <最後; ++i)の場合
        if (comp(*i, * first ))
            __pop_heap( first 、 middle 、 i 、 T(*i )、 comp 、 distance_type( first ));
    sort_heap(最初、 真ん中 、 comp );
 }
 //ヒープソートの入り口
テンプレート <クラス RandomAccessIterator、クラス Compare>
インライン void partial_sort(RandomAccessIterator first ,
                         RandomAccessIterator 中間、
                         RandomAccessIterator last 、比較 comp) {
    __partial_sort( first 、 middle 、 last 、 value_type( first )、 comp );
 }

挿入ソートが作用する

__introsort_loop が __stl_threshold しきい値に達すると、データセットはほぼ順序付けられたとみなすことができます。このとき、挿入ソートによってソート速度をさらに向上させることができ、再帰によるシステム消費も回避できます。__final_insertion_sort の具体的な実装を見てみましょう。

テンプレート <class RandomAccessIterator>
 void __final_insertion_sort(RandomAccessIterator最初、
                            ランダムアクセスイテレータ最後) {
    if (最後-最初> __stl_threshold ) {
        __insertion_sort(最初、最初+ __stl_threshold);
        __unguarded_insertion_sort(最初+ __stl_threshold、最後);
    }
それ以外 
        __insertion_sort(最初、最後);
 }

__final_insertion_sort の実装の詳細を分析してみましょう。

パラメータランダムアクセスイテレータの導入
last-first > __stl_threshold が成立しない場合は、__insertion_sort が呼び出されます。これは、要素数が比較的少ない場合に特別な処理を行わずに直接呼び出すのと同じです。
last-first > __stl_threshold の場合、さらに 2 つの部分に分割され、それぞれ __insertion_sort と __unguarded_insertion_sort が呼び出されます。2 つの部分の分割ポイントは __stl_threshold です。これら 2 つの関数の違いは何ですか?

__insertion_sortの実装

//逆順の調整
テンプレート <クラス RandomAccessIterator、クラス T>
 void __unguarded_linear_insert(RandomAccessIterator last , T 値) {
    RandomAccessIterator次=最後;
 - 次;  
    while (値 < *次) {
        *最後= *次;
最後=次;
 - 次;  
    }
    * last = 値;
 } 
 
テンプレート <クラス RandomAccessIterator、クラス T>
インラインvoid __linear_insert(RandomAccessIterator first 、
                            ランダムアクセスイテレータlast 、 T*) {
    T値 = *最後;
    if (値 < *最初) {
        copy_backward( first , last , last + 1); // 間隔移動
        *最初= 値;
    }
それ以外 
        __unguarded_linear_insert(最後の値 )
 } 
 
 //__挿入ソートエントリ
テンプレート <class RandomAccessIterator>
 void __insertion_sort(RandomAccessIterator first 、 RandomAccessIterator last ) {
    if ( first == last )戻り値;
 (RandomAccessIterator i = first + 1; i != last ; ++i)の場合
        __linear_insert(最初、 i、 value_type(最初) );
 }

挿入された関数には、__unguarded_xxx 形式の関数も表示されます。unguarded という単語は、保護されていない、保護されていないという意味です。Hou Jie 氏は、この形式の関数は、境界チェック条件なしで特定の条件下で正しく実行できる関数であると述べています。

copy_backward も全体的な移動の最適化であり、1 つずつの調整と移動を回避し、効率的な実装のために基礎となる memmove が呼び出されます。

__unguarded_insertion_sort の実装

テンプレート <クラス RandomAccessIterator、クラス T>
 void __unguarded_insertion_sort_aux(RandomAccessIterator最初、
                                    ランダムアクセスイテレータlast 、 T*) {
 (RandomAccessIterator i =最初; i !=最後; ++i)の場合
        __unguarded_linear_insert(i, T(*i));
 } 
 
テンプレート <class RandomAccessIterator>
インライン void __unguarded_insertion_sort(RandomAccessIterator first 、
                                ランダムアクセスイテレータ最後) {
    __unguarded_insertion_sort_aux(最初、最後、 値型(最初));
 }