15

入力配列 A があります

 A[0], A[1], ... , A[N-1]

B を返す関数 Max(T,A) が必要です。これは、サイズ T の以前の移動ウィンドウでの A の最大値を表します。

 B[i+T] = Max(A[i], A[i+T])

最大ヒープを使用して現在移動中のウィンドウ A[i] から A[i+T] の最大値を追跡することにより、このアルゴリズムは O(N log(T)) の最悪のケースを生成します。

知りたいのですが、より良いアルゴリズムはありますか? おそらくO（N）アルゴリズム

4

3 に答える 3

32

O(N) は、Deque データ構造を使用して可能です。ペア (Value; Index) を保持します。

at every step:

  if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then 
     Deque.ExtractHead;
  //Head is too old, it is leaving the window

  while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do
     Deque.ExtractTail;
  //remove elements that have no chance to become minimum in the window

  Deque.AddTail(CurrentValue, CurrentIndex); 
  CurrentMin = Deque.Head.Value
  //Head value is minimum in the current window
于 2012-08-30T10:44:28.327 に答える
6

それはRMQ（範囲最小クエリ）と呼ばれます。実際、私はかつてそれについての記事を書きました（C++コードで）。http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/を参照してください。

または、ウィキペディアのRange Minimum Queryを好むかもしれません

準備の後、任意の範囲の最大数を取得できますO(1)

于 2012-08-30T09:51:40.833 に答える
4

画像処理には、数学的形態学と呼ばれるサブフィールドがあります。実装している操作は、拡張と呼ばれるこの分野の中心的な概念です。明らかに、この操作は広範囲に研究されており、非常に効率的に実装する方法を知っています。

この問題に対する最も効率的なアルゴリズムは、1992 年と 1993 年に van Herk と Gil と Werman によって個別に提案されました。このアルゴリズムでは、 のサイズに関係なく、サンプルごとに正確に 3 回の比較が必要ですT。

数年後、Gil と Kimmel はアルゴリズムをさらに改良し、サンプルごとに 2.5 回の比較のみで済むようにしました。ただし、メソッドの複雑さが増したことで、比較が少なくなることは相殺される可能性があります (コードが複雑になると、実行速度が遅くなることがわかりました)。このバリアントを実装したことはありません。

HGW アルゴリズムと呼ばれるには、入力と同じサイズの 2 つの中間バッファーが必要です。途方もなく大きな入力 (数十億のサンプル) の場合、データをチャンクに分割し、チャンクごとに処理できます。

並べ替えでは、データを順方向にたどり、 size のチャンクの累積最大値を計算しますT。同じように後ろ向きに歩きます。これらはそれぞれ、サンプルごとに 1 つの比較を必要とします。最後に、結果は、これら 2 つの一時配列のそれぞれにある 1 つの値の最大値です。データの局所性のために、入力に対して 2 つのパスを同時に実行できます。

一時配列が length である実行中のバージョンを実行することもできると思いますが、2*T実装はより複雑になります。

  • van Herk、「長方形および八角形のカーネルでのローカル最小および最大フィルターの高速アルゴリズム」、Pattern Recognition Letters 13(7):517-521、1992 ( doi )

  • Gil、Werman、「Computing 2-D min、median、および max フィルター」、IEEE Transactions on Pattern Analysis and Machine Intelligence 15(5):504-507、1993 ( doi )

  • ギル、キンメル、「効率的な拡張、侵食、オープニング、およびクロージング アルゴリズム」、パターン分析と機械知能に関する IEEE トランザクション 24(12):1606-1617、2002 ( doi )

(注: Code Review に関するこの関連する質問からクロスポストされています。)

于 2018-04-01T17:29:19.903 に答える