linux - gcc std :: listの並べ替えの実装が非常に高速になる理由は何ですか？

Question

リンクリストの実装があり、MergesortアルゴリズムとQuickSortアルゴリズムの両方を試しています。

私が理解していないのは、std::listのソート操作が非常に高速である理由です。Linuxでstd::listを見ると、配列ベースのリストではなく、リンクリストでもあるように見えます。

ここでDaveGambleのバージョンとほぼ同じように試した マージソート：リンクリストのマージソート

また、私はこのコードに基づいて簡単なクイックソートを試してみようと思いました： http ://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

驚いたことに、std :: listとsortを使用して1,000万個の乱数を並べ替えるのは、他のいずれよりも約10倍高速でした。

そして、質問している人のために、はい、私はこのプロジェクトのために私自身のリストクラスを使用する必要があります。

Answer 1

私はlist::sort（ソースコード）の興味深いGLibC実装を調べてきましたが、従来のマージソートアルゴリズムを実装していないようです（少なくともこれまでに見たことのないものです）。

基本的にそれが行うことは次のとおりです。

1. 一連のバケットを作成します（合計64）。
2. 並べ替えるリストの最初の要素を削除し、最初の（i=0th）バケットとマージします。
3. マージする前に、ithバケットが空でない場合は、ithバケットをthバケットとマージしi+1ます。
4. 空のバケットとマージするまで、手順3を繰り返します。
5. 並べ替えるリストが空になるまで、手順2と3を繰り返します。
6. 残りのすべての空でないバケットを、小さいものから大きいものへとマージします。

小さな注意：バケットXをバケットとマージするとY、すべての要素がバケットから削除され、すべてが並べ替えられたままXバケットに追加されます。Yまた、バケット内の要素の数はまたはのいずれかであることに注意して0ください2^i。

では、なぜこれが従来のマージソートよりも速いのでしょうか。確かに言うことはできませんが、ここで頭に浮かぶことがいくつかあります。

• リストをトラバースして中間点を見つけることは決してありません。これにより、アルゴリズムがよりキャッシュフレンドリーになります。
• 以前のバケットは小さく、使用頻度が高いためmerge、キャッシュをゴミ箱に移動する呼び出しの頻度は低くなります。
• コンパイラーは、この実装をより適切に最適化できます。これを確認するには、生成されたアセンブリを比較する必要があります。

このアルゴリズムを実装した人々はそれを徹底的にテストしたと確信しているので、決定的な答えが必要な場合は、おそらくGCCメーリングリストで質問する必要があります。