シンボルの頻度をソートするためのソートや他の方法を使うべきでしょうか？

Question

シンボルの配列（256アスキーシンボル）とそのfrequnciesの配列（シンボルのいくつかは0回のアパーチャ）を持っています。ソートにカウントソートを使用することと、どのソートがコードラインをより多く使用するかを複雑にすることが賢明です（コードはアセンブリ、tasmで記述されます）。

Answer 1

入力がlong-ish（文字列または256よりもはるかに長いバッファ）の場合、カウントソートは優れているはずです。

---

それは

をソートするための計数ソートを使用するのが賢明望ましい複雑だろうそれは実装に確かにシンプルだし、O（1）複雑性を有します。大きな入力が可能な場合や一般的な場合、ソートのカウントはと非常にです。

小さな入力が一般的であれば、カウントソートではカウントアレイ全体をクリアして再度スキャンする必要がありますが、このコストは小さな入力ではスケールダウンしません。

CPUに応じて（例えば、高速なmemsetを使ってカウント配列をクリアする）、256シンボルのソートは、64の小さな入力には良いでしょう。あなたはTASMについて言及しています。 x86-16。現代のx86は、SSEストアまたはrep stosdのいずれかを使用して、非常に高速なmemsetを持っています。 （256ビットまたは512バイト（16ビットカウンタの場合）は十分に大きいので、rep stosを使用するのはひどい考えではありません;スタートアップのオーバーヘッドはほとんどが償却され、ベクトルループと同じ速度に近くなります）。

64個以下qsortかmergesortのどちらが良いか分かりません。 16以下の要素（およびqsort/merge-sortのベースケース）以下の場合、パフォーマンスのためにInsertionSortが必要になることがあります。

SSSE3（pshufb用）を搭載した最新のx86では、バイト単位のソートネットワークでコンパイラとしてSSE2 pminub/pmaxubを使用できます（これらの命令は16ビットモードで動作します）。 32ビット要素の場合はUsing SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms、さらにFast in-register sort of bytes?を参照してください。

また、部分ソートにSIMDを使用すると、InsertionSortのスワップ回数が少なくなります。たぶん、いくつかの負荷、pminub/pmaxub、およびストア、多かれ少なかれシャッフルせずに。

と何溶液取る複数のコード行

ASMには、ソースコードの行は、最も有用な尺度です。 （すべての行が命令にアセンブルされるわけではなく、ラベルやディレクティブもあります）。

命令カウントは時には関連性がありますが、命令の中には他の命令より遅いものもあります。命令の順序や命令の入力が他の命令の出力に依存するかどうかは重要です。

パフォーマンスは重要ではなくコードサイズの場合は、マシンコードのバイト数を調べる必要があります。 x86命令は可変長です。

コードサイズについてのみで、パフォーマンスはまったく気になる場合は、バブルソートやジャンプダウンソートを検討することができます。 （早期チェックがなければ、常に最大時間ループする）。陽気に遅いJumpDown sort in 19-bytes of x86-32 machine codeを参照してください。わずか数バイトのコードで、xchg -with-mem（暗黙的にlock接頭辞）を使用せずにスワップできます。より「通常の」バブルソートの実装は、like this（8ビット整数の場合はTASM）となります。

しかし、あなたは、コードのよりわずか数バイトのInsertion Sortを実装することができ、それは一般

（泡または選択のような他のO（N^2）のアルゴリズムと比較して）良好に機能します