重複したデータの長いシーケンスのローリング・ウィンドウでモードを見つける

Question

一連のデータを（重複して）与え、データ・シーケンスに沿ってフィックス・サイズのウィンドウを移動し、各iteraionのウィンドウでモードを検索します。データが削除され、新しいデータがウィンドウに挿入されます。

私はここでより良い解決策を見つけることができません。

私の考え： ハッシュテーブルを使用してください、キーはデータです、キーのデータは、ウィンドウで発生しているデータの頻度です。

最初の反復では、ウィンドウ内の各データを繰り返し、ハッシュテーブルに格納し、各データの頻度を計算します。その後、ハッシュテーブルをトラバースし、最も頻度の高いデータを返します。 ハッシュテーブル内の最も古いデータを検索し、ハッシュテーブル内にあればその頻度を1減らします。0の場合は新しいデータを使用して古いデータを置き換えます。さもなければ、新しいデータをhahstableに挿入するだけです。テーブルを走査してモードを戻します。

O（n * m）ここで、nはデータのseqサイズ、mはウィンドウサイズです。 欠点は次のとおりです。ハッシュテーブルのサイズが固定されていない、オーバーヘッドのサイズが変更されている可能性があります。各反復、テーブルは横断されなければならない、それはエフェクトではない。

O（n lg m）またはO（n）で行うのは可能でしょうか？

何か助けていただければ幸いです。

おかげ

別の解決策：最初の反復で 、キーに関連付けられた値として、キーとその頻度などのデータとハッシュテーブルを構築します。ハッシュテーブルの基底で、キーとしての周波数と関連データを値として持つマルチマップを構築します。

その後、各繰り返しで、ウィンドウ内で最も古いデータを削除してハッシュテーブルを更新し、マルチマップを最新のハッシュテーブルで更新します。マップキーに複数のデータがある場合は、新しいものを周波数が変更されていないデータのみで置き換えます。しかし、新しい周波数とデータで新しいペアを追加します。

ウィンドウ内で新しいデータを取得し、ハッシュテーブルを更新し、マルチマップをハッシュテーブルで最新のものに更新します。

マルチマップ（バイナリ検索ツリー）の最も右側にあるエントリは、その値が現在のウィンドウの最高頻度であるため、モードです。

n >> m、O（n lg m）の場合、時間O（m + m * lg m + n * lg m） スペース：O（m）

もっと良いアイデアはありますか？

Answer 1

スペースO（M）：

• M値を保持する一つのリングバッファ。
• 1つのBSTがM {値、PQポインタ}のペアを保持しています。
• 1つの優先度キューがM個のカウントを保持します。

時間O（LG M）で更新：

• BST O(lg M)で同じ値を探す
• 、リングバッファO(1)に逸脱する値を検索し、
• は、のカウントを調整しますリンクされたPQノード
  • O(lg M)
• は新しいものO(1)
• 古いリングバッファエントリはリンクのカウントを調整し
• 、BST O(lg M)に新しい値を検索置換し、そのノード上の優先順位を調整してくださいPQノード。
  • あなたはBST構造にnextItemポインタを追加することにより、リングバッファを取り除くことができモードO(1)

  を見つけるために、PQに、そのノード上の優先O(lg M)

のGetFirstを調整し、を実行します。最も古い項目への外部ポインタを保持します。これは、1つのBSTルックアップで速度を上げ、値のサイズがポインタのサイズより大きい場合にはスペース獲得になります。しかし、アルゴリズムはコード化するのがより複雑になります。

Answer 2

前の質問に対する解決策を呼び出す...

データ値のリングバッファを維持します。周波数/データ値の組である型を作る。

これらのペアにデータをキーとしてマップを維持します。そのようなペアも含む、周波数をキーとするマルチマップを作る。

データを進める各ステップで、モードは周波数でキー入力されたマップの最後のエントリです。ネクタイがあるかもしれません - それは読者のための運動です。モードを報告した後、マップを使用して削除する値に属するペアを見つける必要があります。削除される値の頻度を持つすべてのエントリをマルチマップから検索し、正しい値を持つエントリを探します。マップにノードを削除、変更、再挿入し、削除されたデータを処理するマルチマップ。追加されたデータを処理するために同様のプロセスを使用します。予想されるデータに応じて、挿入する値と削除する値が一致するかどうか最初に調べることをお勧めします。