バイト比較で構造体をソートするための最適なソートアルゴリズム？

Question

私はかなりの量のデータを保持する64個の構造体の配列を持っています（構造体は約128バイトなので、再編成する必要があります）。配列は、各構造体の単一の符号なしバイトに基づいてソートされる必要があります。私のデータの興味深い特性は、ソートされた値の複製が多数存在する可能性が高いことです。つまり、すべての重複を取り除くと、配列は10個のユニークな要素にすぎませんが、これは指定されていません。私はソートされた値になってしまった場合はそう ：一度ソート

、私はそれぞれのユニークなバイトの実行が開始されることサイズと種類を格納し、スタックを作成する必要があり 4,4,4,9,9,9、 9,9,14,14 スタックは次のようになります。 （4,3）、（9,5）、（14,2）

私はこれらの条件で実行できる最適化がいくつかあると考えました。私がheapsortを行うと、ソート中にスタックを作成できますが、これはqsortより速く、後でスタックを構築しますか？私が使用している大きな構造体のため、ソートアルゴリズムが遅くなるでしょうか？私はバイトを比較しているだけなので、私ができる最適化は何ですか？ところで

：言語はC++

おかげです。

Answer 1

あなたの鍵は整数であり、本当にたくさんあるわけではありません。 オッズはBucket Sortであり、バケットサイズは1で、非常に適用可能です。

Answer 2

私はSTLがあなたがうまくいきたいと思うと思います。独自の並べ替えルーチンとコンテナを書き直すと、エラーが発生しやすく、遅くなる可能性があります。ボトルネックだと気になるだけです。

Answer 3

メモリ内の実際の構造体ではなく、構造体へのポインタまたは参照をソートするので、ソートが遅くなることはありません。

Answer 4

一般に、大きなオブジェクトでは、オブジェクトではなくオブジェクトのポインタ/インデックスの配列をソートする方が高速になる場合があります。または、各ノードにオブジェクトのポインタ/インデックスとオブジェクトのソートキーが含まれているノードの配列をソートします（この場合、キーは1バイトです）。これをC++で行うには、適切なコンパレータをstd::sortまたはstd::stable_sortに供給するだけです。次に、正しい順序を知る必要があるのとは対照的に、元のオブジェクトが順番に必要な場合は、最後にオブジェクトを新しい配列にコピーします。

128バイトのコピーは、余分な間接指定を行っても、バイト比較を実行するよりもはるかに遅くなります。最適なパフォーマンスを得るためには、比較するのではなく、見る必要のある動きであり、ポインタを扱うことは、ほとんどの動きを避けるための1つの方法です。

最後にコピーを実行するときに、ランレングスエンコードを作成することができます。

もちろん、あなたのケース（64、 "約128"、および1）の数字を特別に使用するカスタムソートアルゴリズムを使用すると、さらに高速化することができます。しかし、 "最も速い - イントロソート、ヒープソート、またはマージソート"のような簡単な質問さえも、コードを記述して実行することなく答えられるのは一般的に不可能です。