239

重複の可能性:
C のローリング メディアン アルゴリズム

整数がデータ ストリームから読み取られるとします。これまでに読み取った要素の中央値を効率的な方法で見つけます。

私が読んだ解決策：左側の最大ヒープを使用して、有効な中央値よりも小さい要素を表し、右側の最小ヒープを使用して、有効な中央値よりも大きい要素を表すことができます。

着信要素を処理した後、ヒープ内の要素の数は、最大で 1 要素だけ異なります。両方のヒープに同じ数の要素が含まれている場合、ヒープのルート データの平均が実効中央値になります。ヒープのバランスが取れていない場合、より多くの要素を含むヒープのルートから有効な中央値を選択します。

しかし、最大ヒープと最小ヒープをどのように構築するのでしょうか。つまり、ここで有効な中央値をどのように知るのでしょうか? max-heap に 1 つの要素を挿入し、次に min-heap に次の 1 つの要素を挿入するというように、すべての要素についてそうすると思います。ここで間違っている場合は修正してください。

4

9 に答える 9

396

ストリーミングされたデータから実行中の中央値を見つけるためのさまざまなソリューションがいくつかあります。回答の最後で簡単に説明します。

質問は、特定のソリューション (最大ヒープ/最小ヒープ ソリューション) の詳細に関するものであり、ヒープ ベースのソリューションがどのように機能するかを以下に説明します。

最初の 2 つの要素について、小さい方を左側の maxHeap に追加し、大きい方を右側の minHeap に追加します。その後、ストリームデータを1つずつ処理し、

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

次に、いつでも次のように中央値を計算できます。

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

ここで、回答の冒頭で約束したように、一般的な問題について話します。データのストリームから実行中の中央値を見つけるのは困難な問題であり、メモリの制約がある正確な解を効率的に見つけることは、一般的なケースではおそらく不可能です。一方、データに活用できる特性があれば、効率的な専用ソリューションを開発できます。たとえば、データが整数型であることがわかっている場合、カウントソートを使用できます、これにより、コンスタント メモリ コンスタント タイム アルゴリズムが得られます。ヒープ ベースのソリューションは、他のデータ型 (double) にも使用できるため、より一般的なソリューションです。最後に、正確な中央値が必要なく、近似値で十分な場合は、データの確率密度関数を推定し、それを使用して中央値を推定することができます。

于 2012-05-18T18:15:42.147 に答える
60

入力の分散が統計的に分布している場合 (正規、対数正規など)、リザーバー サンプリングは、任意の長い数値ストリームからパーセンタイル/中央値を推定する合理的な方法です。

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

「reservoir」は、サイズに関係なく、すべての入力の実行中の均一な (公平な) サンプルです。中央値 (または任意のパーセンタイル) を見つけることは、リザーバーを並べ替えて関心のあるポイントをポーリングするという単純な問題です。

リザーバは固定サイズであるため、ソートは事実上 O(1) であると見なすことができ、このメソッドは一定の時間とメモリ消費の両方で実行されます。

于 2012-05-21T23:05:17.770 に答える
52

一度にすべてのアイテムをメモリに保持できない場合、この問題はさらに難しくなります。ヒープ ソリューションでは、一度にすべての要素をメモリに保持する必要があります。これは、この問題のほとんどの実際のアプリケーションでは不可能です。

代わりに、数字が表示されたら、各整数が表示された回数を記録してください。4 バイトの整数を想定すると、それは 2^32 バケット、または最大で 2^33 の整数 (各 int のキーとカウント)、つまり 2^35 バイトまたは 32GB になります。0 のエントリのキーやカウントを保存する必要がないため (つまり、Python の defaultdict のように)、これよりもはるかに少なくなる可能性があります。これには、新しい整数を挿入するのに一定の時間がかかります。

次に、いつでも中央値を見つけるために、カウントを使用して、どの整数が中央の要素であるかを判断します。これには一定の時間がかかります (大きな定数ではありますが、それでも一定です)。

于 2012-05-21T21:19:09.600 に答える
31

私が見つけたストリームのパーセンタイルを計算する最も効率的な方法は、P² アルゴリズムです: Raj Jain、Imrich Chlamtac: The P² Algorithm for Dynamic Calculation of Quantiiles and Histograms Without Storeing Observations. 通信します。ACM 28(10): 1076-1085 (1985)

このアルゴリズムは簡単に実装でき、非常にうまく機能します。ただし、あくまでも目安ですので、その点はご了承ください。要約から：

中央値およびその他の分位数の動的計算のために発見的アルゴリズムが提案されています。観測値が生成されると、推定値が動的に生成されます。観測は保存されません。したがって、このアルゴリズムには、観測の数に関係なく、非常に小さく固定されたストレージ要件があります。これにより、産業用コントローラーやレコーダーで使用できるクォンタイル チップに実装するのに理想的です。このアルゴリズムは、ヒストグラム プロットにさらに拡張されます。アルゴリズムの精度が分析されます。

于 2012-05-21T23:14:09.080 に答える
30

最近見たn 個の要素の中央値を見つけたい場合、この問題には、最近見たn 個の要素だけをメモリに保持する必要がある正確な解があります。高速で、スケーリングも良好です。

インデックス可能なスキップリストは、ソートされた順序を維持しながら、O(ln n) の挿入、削除、および任意の要素のインデックス付き検索をサポートします。n 番目に古いエントリを追跡するFIFO キューと組み合わせると、解決策は簡単です。

class RunningMedian:
    'Fast running median with O(lg n) updates where n is the window size'

    def __init__(self, n, iterable):
        self.it = iter(iterable)
        self.queue = deque(islice(self.it, n))
        self.skiplist = IndexableSkiplist(n)
        for elem in self.queue:
            self.skiplist.insert(elem)

    def __iter__(self):
        queue = self.queue
        skiplist = self.skiplist
        midpoint = len(queue) // 2
        yield skiplist[midpoint]
        for newelem in self.it:
            oldelem = queue.popleft()
            skiplist.remove(oldelem)
            queue.append(newelem)
            skiplist.insert(newelem)
            yield skiplist[midpoint]

完全な作業コードへのリンクを次に示します (わかりやすいクラス バージョンと、インデックス可能なスキップリスト コードがインライン化された最適化されたジェネレーター バージョン)。

于 2012-05-22T05:36:47.400 に答える
19

これを直感的に考えると、完全にバランスの取れた二分探索木がある場合、ルートは中央値の要素になります。これは、同じ数の小さい要素と大きい要素が存在するためです。ここで、ツリーがいっぱいでない場合、最後のレベルから欠落している要素があるため、これはまったく当てはまりません。

したがって、代わりにできることは、中央値と、中央値より小さい要素用と中央値より大きい要素用の 2 つのバランスのとれた二分木を用意することです。2 つのツリーは同じサイズに保つ必要があります。

データ ストリームから新しい整数を取得したら、それを中央値と比較します。中央値よりも大きい場合は、右側のツリーに追加します。2 つのツリー サイズの差が 1 より大きい場合、右側のツリーの最小要素を削除し、それを新しい中央値にして、古い中央値を左側のツリーに配置します。小さい方も同様。

于 2012-05-22T18:59:01.387 に答える
8

効率的とは、文脈に依存する言葉です。この問題の解決策は、挿入の量に対して実行されるクエリの量によって異なります。中央値に関心のある最後に向かって N の数字と K 回を挿入するとします。ヒープベースのアルゴリズムの複雑さは O(N log N + K) になります。

次の代替案を検討してください。数値を配列に入れ、クエリごとに線形選択アルゴリズムを実行します (たとえば、クイックソート ピボットを使用します)。これで、実行時間が O(KN) のアルゴリズムができました。

K が十分に小さい場合 (クエリの頻度が低い場合)、後者のアルゴリズムは実際にはより効率的であり、その逆も同様です。

于 2012-05-21T20:50:04.123 に答える
-2

たった1つのヒープでこれを行うことはできませんか? 更新：いいえ。コメントを参照してください。

不変:2*n入力を読み取った後、最小ヒープはnそれらの最大のものを保持します。

ループ: 2 つの入力を読み取ります。両方をヒープに追加し、ヒープの最小値を削除します。これにより、不変条件が再確立されます。

したがって、2n入力が読み取られると、ヒープの最小値は n 番目に大きくなります。中央値周辺の 2 つの要素を平均化し、奇数回の入力後にクエリを処理するには、少し複雑な処理が必要になります。

于 2012-05-21T21:12:22.647 に答える