algorithm - 最大メモリ効率での増分中央値計算

Question

私には価値を生み出すプロセスがあり、それを観察しています。プロセスが終了したら、それらの値の中央値を計算したいと思います。

平均を計算する必要がある場合、生成された値の合計と数を格納するだけで、O(1) のメモリが必要になります。中央値はどうですか？すべての値を格納することで明らかな O(n) を節約する方法はありますか?

編集: 2 つのケースに関心があります: 1) ストリームの長さがわかっている、2) わかっていない。

Answer 1

最初の n/2 ポイントのいずれかが中央値になる可能性があるため、少なくとも ceil(n/2) ポイントを保存する必要があります。ポイントを保存して中央値を見つけるのがおそらく最も簡単です。ceil(n/2) ポイントを保存することに価値がある場合は、最初の n/2 ポイントをソート済みリストに読み込み (おそらくバイナリ ツリーが最適です)、新しいポイントが追加されると、低いポイントまたは高いポイントを破棄して保持します。投げ出された両端のポイント数を追跡​​します。

編集：

ストリームの長さが不明な場合、明らかに、Stephen がコメントで観察したように、すべてを覚えておくしかありません。アイテムが重複している可能性が高い場合は、値とカウントを保存する Dolphins のアイデアを使用して、メモリを少し節約できる可能性があります。

Answer 2

あなたはできる

• 許容できる場合は、統計を使用します。たとえば、サンプリングを使用できます。
• 番号ストリームに関する知識を使用する
  • カウントソートのようなアプローチを使用する：k個別の値はO(k)メモリを保存することを意味します）
  • または、既知の外れ値を捨てて、(高い、低い) カウンターを保持します。
  • 重複がないことがわかっている場合は、ビットマップを使用できます...しかし、それはO(n).

Answer 3

離散値と多くの繰り返しがある場合は、値とカウントを保存できます。これにより、スペースが少し節約されます。

おそらく、計算の段階で、中央値がその上限または下限の範囲にないことが確実である限り、上位 'n' および下位 'n' の値を破棄できます。
たとえば、100,000 の値を期待しているとしましょう。保存された数が (たとえば) 12,000 になるたびに、最高の 1000 と最低の 1000 を破棄して、ストレージを 10,000 に戻すことができます。

値の分布がかなり一貫している場合、これはうまく機能します。ただし、最後に非常に高い値または非常に低い値を多数受け取る可能性がある場合は、計算が歪む可能性があります。基本的に、（最終的な）中央値よりも小さい「高い」値、または（最終的な）中央値以上の「低い」値を破棄すると、計算はオフになります。

例の更新
ビット
データセットが数字 1、2、3、4、5、6、7、8、9 であるとしましょう。
調べると、中央値は 5 です。

最初に得た 5 つの数字が 1、3、5、7、9 だとしましょう。
スペースを節約するために、最高値と最低値を破棄して 3,5,7 を残し
ます 2,6 をさらに 2 つ取得すると、ストレージは 2,3,5,6,7になります
最高値と​​最低値を破棄して、3,5,6 を残して
Get最後の 2 つは 4,8 で、3,4,5,6,8
です。中央値はまだ 5 で、世界は良い場所です。

ただし、取得した最初の 5 つの数字が 1,2,3,4,5 であるとしましょう
上と下を破棄して 2,3,4 を残し
ます さらに 2 つの 6,7 を取得すると、2,3,4,6,7 になります
破棄上と下は 3,4,6 のまま
最後の 2 つの 8,9 を取得すると、中央値が 6 の 3,4,6,8,9 が
得られますが、これは正しくありません。

数値が適切に分散されていれば、四肢のトリミングを続けることができます。それらがたくさんの大きな数またはたくさんの小さな数で束ねられている可能性がある場合、破棄は危険です.