0

私が使用しているデータセットの特徴的な機能のいくつかは、次の傾向を示しています。

  1. 配列の最初の50〜70％はほぼソートされ、最後の30％は完全にスクランブルされています。

    • 挿入ソート部分をシェルソートに置き換えても効果はありますか？

  2. 配列の最初の50〜70％はほぼソートされており、最後の30％には多くのカメが含まれています。

    • カメの発生は非常に重要なので、このコムソートのバリエーションを支持してティムソートを捨てる必要があります- ここで。彼らのベストケースのパフォーマンスはO（n）を示していますが、平均ケースパフォーマンスはO（n log n）のティムソートの方が優れていますが、コムソートはΩ（n log n）ですが、これはコムソートの修正バージョンまたはカメの密度を取ります考慮に入れますか？

  3. 2番目のシナリオと同じですが、パフォーマンスを向上させることができる場合は、部分的にソートされた出力で問題ありません。たとえば、1,000,000個の要素を含む配列は、配列の最初の1％スロットに最小の1％（つまり、10,000個の要素）を持つことができますが、内部で並べ替える必要はありません。

    • これは、クイックソートで特定の再帰深度の後に引き出して、要素を適切な場所のほぼ近くに配置することで実行できますか。

関連する場合は、これが私が変更しようとしているJava用のTimsortコードです--code。

4

1 に答える 1

1

最善の答えは、TimSortをカスタマイズすることでデータセットのパフォーマンスが向上するかどうかを確実に予測することはできないということだと思います。あなたはそれを試して見る必要があるでしょう。

そして、私は私のコメントから私のアドバイスを繰り返すつもりです：最初にそれをプロファイリングしてください！

代表的なデータで実行されているアプリケーションのプロファイルを作成するまで、これが役立つ可能性すらあるかどうかを知ることはできません。たとえば、計算がデータの並べ替えに5％の時間を費やしている場合、並べ替えアルゴリズムを50％高速化すると、アプリケーションは2.5％高速化されます。そして、それは単にあなたの時間を無駄にする価値がありません。

于 2012-10-07T12:02:25.933 に答える