使用最大內存效率的增量中值計算

Question

我有一個生成值的過程，我觀察過。當進程終止時，我想計算這些值的中位數。

如果我必須計算平均值，我可以只存儲總和和生成值的數量，從而具有O（1）內存要求。中位數呢？有沒有辦法保存來自存儲所有值的顯而易見的O（n）？

編輯：對2種情況感興趣：1）流長已知，2）不是。

Answer 1

你將需要至少存儲小區（N/2）點，因爲第n/2個點的任何一個都可能是中位數。只存儲點並找到中位數可能是最簡單的。如果保存ceil（n/2）點是有價值的，那麼在第一個n/2點讀入一個排序列表（二叉樹可能是最好的），然後當新點添加時，拋出低點或高點並保持追蹤任何一端拋出的點數。

編輯：

如果流長度未知，那麼很明顯，斯蒂芬在評論中觀察到的，那麼我們就沒有選擇，只能記住一切。如果可能有重複的項目，我們可以使用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,3,5,6,7
捨棄最高和最低，離開3,5,6
獲得最後兩個4,8，我們有3,4,5,6,8
中位數仍然是5，世界是一個很好的地方。

但是，讓我們說，前五個數字，我們得到的是1,2,3,4,5
丟棄頂部和底部留下2,3,4
獲得兩個6,7和我們有2個， 3,4,6,7
捨棄頂部和底部離開3,4,6
獲取最後兩個8,9，我們有3,4,6,8,9
的中位數是6，這是不正確的。

如果我們的數字分佈很好，我們可以不斷修整四肢。如果他們可能被大量或大量小數目捆綁在一起，那麼丟棄是有風險的。