1

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

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

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

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

4

5 に答える 5

3

データの「実行」を利用しているため、Timsort がこれに勝つと思います。

通常、クイックソートは高速ですが、最悪のシナリオに陥るリスクがあります。たとえば、すでにソートされた入力が与えられた場合、quickshort のいくつかのバージョンは O(n^2) です。誰かがあなたに間違った種類のグラデーションで満たされた画像を与えた場合、これはあまり友好的ではありません......

これは少しクレイジーなアイデアです。Z オーダー パス ( Wikipedia リンク) を試すこともできます。これにより、両方の次元で隣接する類似の色を利用できるようになります。

于 2010-05-12T11:44:07.110 に答える
1

インプレースクイックソートから始めます。浮動小数点の比較は、ほとんどのプロセッサで高速です (確かに、マージソートに必要な割り当てよりもはるかに高速です)。

于 2010-04-01T00:18:33.210 に答える
1

フラット配列で numpy の並べ替えルーチンを使用して、いくつかの画像の簡単で汚いベンチマークを打ち出しました。これは、数百のランダムな画像と数百の人間の顔の画像の平均です。どちらも単精度です。

On random images...
quicksort took 0.000153 seconds per image.
mergesort took 0.000170 seconds per image.
heapsort took 0.000241 seconds per image.
On real images...
quicksort took 0.000136 seconds per image.
mergesort took 0.000143 seconds per image.
heapsort took 0.000230 seconds per image.

すべてのアルゴリズムは、既存の半順序付け、特にクイックソートの恩恵を受けているようです。Numpy にはソートされたリストのマージ機能がないようです。そのため、行を事前にソートすることはできません。

于 2010-04-01T03:23:38.313 に答える
0

timsort がありますが、比較が遅いアプリケーション向けであることがいくつかの場所で見られました。派手な開発者は、それを実装することさえ気にしないことにしたようです:

http://mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html

于 2010-04-01T00:12:16.253 に答える
0

行を個別にマージソートしてから、ソートされた行をマージできます。

これは、少なくとも 2D 配列の特別な構造の一部、つまり単調な実行は通常、配列の端で開始および停止するという事実を活用します。また、別の数レベルの並列処理も公開されています。

于 2010-04-01T00:15:17.573 に答える