1

私はストリームを持っています（その長さはわかりませんが、理論的には無限かもしれません）。

ストリームの要素を 1 つずつ読み取ります。

ストリームから要素が読み取られるたびに、kこれまでに読み取った最大の要素を返すことができるようにしたいと考えています。

(私にとって理想的には、Python および/または Lisp/scheme のコードです)。

K は最初に読み取られ、K は NUMBER (3 番目、4 番目) または PROCENT (これまでに読み取られた要素の合計数の K %) になります。K=1/2 の場合、毎回中央値の要素を抽出することを意味します...たとえば、N 番目の要素を読み取った後、N/2 番目に大きい要素を返す必要があります

例 K=1/2:

3 -> 3
3,4 -> 3
3,4,2 -> 3
3,4,2,1 -> 2
etc.

この例は、質問を明確にするのに十分だと思います。K 番目の要素を抽出するのに最小限の時間が必要です。(これは、O(1) でストリームを読み取り、読み取った値を挿入し、K 番目の要素を抽出することを想定しています)。

O（n）よりも優れたソリューションが必要です。

4

4 に答える 4

1

したがって、k 番目の要素が必要であり、k はアルゴリズムを実行する前にわかっているため、最初の観察では、最大で k 個の要素、最小の k 個の要素を格納する必要があります。新しい要素を読み取るときは、データ構造に要素を挿入して、そのプロパティを保持し、答えをすばやく取得する機会が必要です。1) 最大 k 個の要素を持つ max-heap を使用できます。要素の挿入をヒープ (log(k)) に読み込みます。次に、k 個の要素 (正確には k+1) を超える場合は、extract_max O(log(k)) を抽出して再構築する必要があり、答えはヒープ アクセス O(1) の先頭。したがって、k 番目の要素を取得するのに log(k) がかかるたびに、すべての要素の合計 - n * log(k) になります。

2) パーセンテージを使用する場合、処理された要素の数に応じて要素の場所が動的に計算されます。ここでは、注文統計ツリー、http://en.wikipedia.org/wiki/Order_statistic_treeを同じログ (量要素の数) の挿入とログ (要素の量) の検索。

于 2012-07-31T02:14:11.717 に答える
1

k 番目に大きい要素を含むヒープ (またはパーセンテージの場合はすべての要素を含む二分探索木) を使用します。これにより、O(Log(k)) (パーセンテージの場合は O(Log(n))) が得られます。

ケースk番目:

  • 新しい要素がヒープの最小値より小さい場合、k 番目に大きい要素がヒープの最小値になります。
  • それ以外の場合は、ヒープの最小値を新しい要素で置き換えてヒープ化します。k 番目に大きいものがヒープの新しい最小値になります。

ケース パーセンテージ: 二分探索ツリーに新しい要素を挿入します。このようなツリーでは、k 番目の要素を簡単に見つけることができます。

于 2012-07-30T23:20:18.120 に答える
0

これまでに見たk 個の最大の要素の並べ替えられたリストを保持している場合は、常にリスト内の最小のものを返すことができます。リストへの挿入はO(k)で、最小の取得はO(1)です。リストのサイズはnに依存しないため、nに関しては一定です。

編集 2: 以下のコメントで述べたように、リストをスキップするのが最善の策であると思います。私の記憶が正しければ、O(log k)時間の挿入、O(1)時間の最小要素の削除、O(k log k)スペース (連結リストのO(k)に対して) があります。

于 2012-07-30T22:07:45.913 に答える
0

ヒープはまともです。最小の O(1) ルックアップ、O(logn) 削除。

Treap は、この種の問題では平均して非常に高速です (一定で良い)。それらは、O(logn) 時間で最小値または最大値へのアクセス (または削除) を許可します。 http://stromberg.dnsalias.org/~strombrg/treap/ そこには、まさにこの種のもののための「ネスト」モジュール (最高のもの) があります。

赤黒ツリーは非常に高速ではありませんが、パフォーマンス コストが非常にスムーズに分散されるため、treap の場合のように、高速-高速-高速-低速-高速-高速-低速の状態になることはありません。代わりに、適度 - 適度 - 適度 - 適度のようなものです。

ここで「フィンガーツリー」をやってみるのも面白いかもしれません。フィンガー ツリーは、ツリー内の最小値と最大値の O(1) ルックアップを提供すると言われています。削除についてはわかりません。

于 2012-07-30T23:40:55.787 に答える