2

float 値の配列があり、その値と、さらに重要なことに最大 4 つの値の位置が必要です。

私は元々、現在の位置の値を記録された max-so-far と比較し、max-so-far が変化したときに位置変数を更新することによって、配列をウォークスルーし、通常の方法で max を見つけるシステムを構築しました。これは非常に単純な O(n) アルゴリズムで、うまく機能しました。上位の値だけでなく、上位 3 つまたは 4 つの値を保持する必要があることを後で知りました。同じ手順を拡張し、max-so-far を 4 つの max-so-fars の配列に複雑化したところ、コードが見苦しくなってしまいました。

手続きにわずかな量の計算しか追加されていないため、それでも機能し、十分に高速です。それでも効果的に配列全体を歩き回り、各値を 1 回チェックします。

これは、並べ替えられたリストとそれに付随する元の位置リストの 2 つの配列を返す並べ替え関数を使用して、MATLAB で行います。最初のいくつかの値を見ると、まさに必要なものが得られます。この機能を C# .NET 2.0 プログラムに複製しています。

List オブジェクトで同様のことができることと、List オブジェクトにはソート ルーチンが組み込まれていることは知っていますが、それが元の位置を教えてくれるとは思えません。

それはうまく機能していますが、今では 5 番目の最大値が必要であり、現在 if ステートメントの醜い混乱である max-so-far チェッカーを書き直すと、醜さを悪化させるだけであることがわかります。5 番目のレベルを追加しても問題なく動作し、遅くはありませんが、より良い方法があるかどうか SO コミュニティに尋ねたいと思います。

リスト全体をソートするには、現在の方法よりも多くの計算が必要ですが、リストは 1 千または 2 千の float しかないため、問題になるとは思いません。したがって、元の位置に戻すことができる並べ替えルーチンがあれば、それが理想的です。

背景として、この配列は 1 キロバイトの wave ファイルに対するフーリエ変換の結果であるため、最大値の位置はサンプル データのピーク周波数に対応します。私は上位 4 つに満足していましたが、より正確なサンプル分類を行うには、上位 5 つまたは 6 つを実際に収集する必要があると考えています。

4

4 に答える 4

9

コーディングする必要がある代替アルゴリズムを提案できます:)

サイズ K のヒープを使用します。ここで、K は、保存する上位要素の数を示します。これを元の配列の最初の K 要素に初期化します。すべての N - K 要素について、必要に応じて挿入しながら、配列を調べます。

proc top_k (array<n>, heap<k>)
heap <- array<1..k-1>
for each (array<k..n-1>) 
  if array[i] > heap.min
     heap.erase(heap.min)
     heap.insert(array[i])
  end if
end for
于 2009-03-06T01:30:18.087 に答える
2

リストのアイデアを引き続き使用できます。リストに入れる要素は、インデックスと値の両方を格納する構造にすることができます。ただし、値のみでソートします。たとえば、次のようになります。

class IndexAndValue : IComparable<IndexAndValue>
{
    public int index;
    public double value;

    public int CompareTo(IndexAndValue other)
    {
        return value.CompareTo(other.value);
    }
}

次に、インデックスに関する情報を保持しながら、それらをリストに貼り付けることができます。リストに最大の m 個のアイテムのみを保持する場合、効率は O(mn) になります。

于 2009-03-06T01:33:24.100 に答える
2

現在使用しているアルゴリズムはわかりませんが、簡単なアルゴリズムを提案します。浮動小数点数の配列fと最大capacity 数があることを認めれば、次のことができます。

int capacity = 4; // number of floats you want to retrieve
float [] f; // your float list
float [] max_so_far = new float[capacity]; // max so far

// say that the first 'capacity' elements are the biggest, for now
for (int i = 0; i < capacity; i++)
  max_so_far[i] = i;

// for each number not processed
for (int i = capacity; i < f.length; i++)
{
  // find out the smallest 'max so far' number
  int m = 0;
  for (int j = 0; j < capacity; j++)
    if (f[max_so_far[j]] < f[max_so_far[m]])
      m = j;

  // if our current number is bigger than the smallest stored, replace it
  if (f[i] > f[max_so_far[m]])
    max_so_far[m] = i;
}

アルゴリズムの終わりまでに、最大の要素のインデックスが に格納されmax_so_farます。

capacity値が大きくなると、初期位置を追跡しながらリストをソートする代替手段よりもわずかに遅くなることに注意してください。並べ替えには O(n log n) の比較が必要ですが、このアルゴリズムには O(nの容量) が必要です。

于 2009-03-06T02:04:38.847 に答える
1

別のオプションは、クイック選択を使用することです。クイック選択は、リスト内の k 番目の要素の位置を返します。k 番目の要素の位置と値を取得したら、リストを調べて、値が k 番目の要素より小さい/大きいすべての要素を取得します。

ここでクイック選択の ac# 実装を見つけました:リンク テキスト

長所：

  1. O(n+k) 平均実行時間。

短所：

  1. 見つかった k 個の要素はソートされていません。それらを並べ替えると、実行時間は O(n + logk) になります
  2. 私はこれをチェックしていませんが、非常に小さい k の場合、最良のオプションは、次の最小/最大の要素を見つけるたびに、配列に対して k 回の実行を行うことだと思います。
于 2010-01-07T11:16:26.437 に答える