問題タブ [timsort]

滑らかな 2D 配列で値を並べ替える最も速い方法は何ですか?

入力はフィルター処理された小さな画像です。

• 約60×80ピクセル
• シングルチャンネル
• 単精度または倍精度浮動小数点数
• 行の主要なストレージ、メモリ内の順次
• 値には符号が混在しています
• 部分的に「滑らか」で、幅が 10 ピクセル程度の領域

出力は、元の配列を並べ替えるインデックスと共に、並べ替えられた値のフラット (約 4800 値) 配列です。

Java 7 のドキュメントが見つかりません。Java 6 についてしか見つけることができません。Java 6 はまだ高速またはマージされています。Arrays.sortJava 7でメソッドのドキュメントを見つける方法を知っている人はいますか?

TimSort は、ソートのために Java 7 でデフォルトで使用されるアルゴリズムです。

このソースを見つけましたが、すべてプライベートであるため、どのメソッドを呼び出すべきかわかりません。誰でも理解できますか？ありがとうございました。

http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java

ティムソート（ウィキペディアによる）のパフォーマンスがはるかに優れているように見えるのに、クイックソートが全体的に最速のソートアルゴリズムであると私がよく耳にするのはなぜですか？グーグルはどんな種類の比較もしなかったようだ。

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

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

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

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

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

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

Common Lisp のアルゴリズム クラスですべての割り当てを行うことに挑戦しました。私は Lisp の学習の初日に入りましたが、障害にぶつかりました。

割り当ては、任意のサブセット長に達したときに挿入に変換するマージ ソートを作成することです (Timsort)。挿入セクションは完全に機能しますが、マージの分割部分は、プログラムを 2 回分割する必要がある場合にのみ機能します。Lisp でリストが機能する方法に関係していることはわかっていますが、問題を特定するには新人すぎます。

無限ループにヒットすると思います...デバッグステートメントで実行すると、セットに要素が多すぎると出力されないため、わかりません。

私はここで、特定の回答を求めたり、誰かに私のコードを書いてもらったりすることを懇願しているわけではありません。たぶん、説明や正しい方向へのポイントが大いに役立つでしょう!

私のコード:

注：これは私が書いたコードで、インターネットから入手したものではありません...おそらくわかりますが、笑

かなり大きなデータセットで並べ替えを行うための「timsort」アルゴリズムを調べていました：http： //timsort4net.codeplex.com/

通常Array.Sort(Keys, Items)、Itemsは、並べ替え中に発生した位置の変更を識別するためのメソッドとして機能する整数配列である場合に使用します。

並べ替えアルゴリズムの実装を大幅に変更せずに、これと同じ結果を達成する方法はありますか？

ティムソートのアルゴリズムを理解しようとしていますが、スタック不変条件を実装する理由を理解するのに問題があります。

1. A> B + C
2. B> C

この文書によると、

後で発生する可能性のあるパターンを悪用するために、マージをできるだけ遅らせたいと思いますが、見つかった実行がまだメモリ階層の上位にあることを悪用するために、できるだけ早くマージを実行したいと思います。

キャッシュ効果を活用するために、できるだけ早くマージを実行したいことは理解していますが、遅延させたい理由がわかりません。それは彼がどのような「パターン」を意味するのでしょうか？

Swenson の Timsort の C 実装を見つけました: https://github.com/swenson/sortは古い SO の質問の 1 つに記載されています。

2 つの問題が発生しました。

1）それを使用するには、ソートしたいタイプに適した SORT_CMP マクロを定義する必要があります。私のタイプは次のように定義されています（ここでは少し簡略化されています）：

私は定義しようとします：

しかし、エラーが発生し続けます：「構造体でも共用体でもない何かでメンバー 'a'を要求しています」おそらくxとyはポインターになると思いましたが：

どちらも機能しません。それを手伝ってくれませんか？私はCの初心者で、おそらく基本的なものが欠けています。

2) Visual Studio でそのコードをコンパイルする方法はありますか? 新しい C 標準 (ブロックの途中の宣言など) のものを使用し、cl.exe はそれを受け入れません。GCC（mingw）を使用してコンパイルしましたが、mingwは残りのコードでVCよりも20％遅い（O2またはO3フラグ対/ Oxのlc.exe）ため、stdlib qsortの代わりにTimsortを使用することで得られる利益それを補うことはありません。同じことが Pelles コンパイラにも当てはまります。私のデータのほとんどには、部分的にソートされたシーケンスが多数あり、ソートには実行時間の約 50% がかかるため、VC で動作させると仮定すると、ここで利益が得られると感じています。

ウィキペディアやその他のリソースでティムソートについてググって読んでいます。しかし、私はティムソートが何をしているのかはっきりとは分かっていません。誰かがアルゴリズムを説明したり、明確な説明を含むドキュメントを提供したりできますか?