3

私が持っているいくつかのアイデアに基づいて、非常に効率的な並べ替えアルゴリズムを開発したいと考えています。問題は、既に存在する大多数の高く評価されている並べ替えアルゴリズムに対して、アルゴリズムの効率をテストしたいということです。

理想的には、私は見つけたいと思います:

  • アルゴリズムの効率を提供するために重要な大量の並べ替えテスト
  • 既存の強力に最適化された並べ替えアルゴリズムの大規模なセット (コード付き - 言語に関係なく)
  • さらに良いことに、ソートアルゴリズム開発者に適切な環境を提供するソフトウェア

ティムソート、クイックソート、デュアルピボットクイックソート、および Java 6 ソートを比較した 2 つのテーブルを含む以前に見つけた投稿を次に示します : http://blog.quibb.org/2009/10/sorting-algorithm-shootout/これらの TXT ファイル (1245.repeat.1000.txt から sequential.10000000.txt まで) には、これらのアルゴリズムのテスト ケースが含まれていますが、元の TXT がどこにも見つかりません。

多くのソートテストケースおよび/または多くの非常に効率的なソートアルゴリズムとのリンクを教えてもらえますか? （これは私が最も興味を持っているテストケースです。ソートアルゴリズムはインターネット上にあります）

事前にどうもありがとうございました！

4

1 に答える 1

1

いくつかのこと：

  • クイックソートは、順方向および逆方向にソートされたリストで機能するため、他のタイプのリストが必要になります。
  • ランダム データでのテストは問題ありませんが、異なるアルゴリズムのパフォーマンスを比較したい場合、毎回新しいランダム データを生成できないか、結果が信頼できないことを意味します。エントリ数に基づく順序でデータを書き込む疑似「ランダム」アルゴリズムを考え出す必要があると思います。そうすれば、サイズ n、10n、および 100n のリストに対して生成されるデータは同様になります。
  • ソートのテストは、主に速度に関するものではなく (アルゴリズムが完成するまで)、エントリに対する比較の比率に関するものです。1 つの並べ替えでリスト内のエントリごとに 15 回の比較が必要で、同じリストに対して別の 12 回の比較が必要な場合、2 回目の並べ替えは 2 倍の時間で実行されたとしても効率的です。より些細なソートの概念では、必要な交換の数も関係します。
  • テストには、RAM で整数のベクトルを使用します。アルゴリズムがうまく機能する場合、整数のベクトルをインデックスのベクトルに変換して、比較するデータを含むバッファーに入れることができます。このようなアルゴリズムは、インデックスが指すデータに基づいてインデックスのベクトルをソートします。
于 2012-02-06T15:45:14.380 に答える