從流中找到運行媒體

問題：由於整數是從數據流中讀取的。查找以有效方式閱讀的元素的中位數。從流中找到運行媒體

我找到了解決辦法here

我的問題是，爲什麼我們需要使用堆，而不是隻是單純的增加數爲載體？

例如，假定我們使用的是向量來存儲輸入數據，然後我們所說的方法來計算中值如下：

if vector size is even 
    return (element at size/2 + element at size/2-1); 
else 
    return (element at size/2);

將在上述溶液中的工作？

來源

2015-10-20 firefly

如果您的向量中的元素不正確，則您的解決方案無法工作。如果你在矢量的末尾添加元素，它們將不會按順序排列。

另一方面，元素是在堆中。

此外，在第一個返回語句中還有一個兩除的差異。

來源

2015-10-20 00:20:16 ChronoTrigger

感謝您的澄清！不知道是否正確，但根據我的理解，假設您有來自數據流的n個整數;因爲需要o（lg（n））將一個元素插入堆中，所以總的時間複雜度將是o（nlg（n））。另一方面，我們可以首先將數據插入一個需要線性時間的向量，然後調用也是o（nlg（n））的排序算法。因此，我並沒有真正看到使用複雜數據結構來解決這個問題的優勢。 – firefly

不同之處在於，如果您每次計算中位數時對矢量進行排序，則您正在執行額外的工作，因爲您沒有利用已排序的元素。考慮這種情況：從流中獲取n個項目，計算中位數，再獲得一個項目，再次計算中位數。在堆中，你有O（nlogn）+ O（logn）+ O（logn）+ O（logn）。用矢量，你有O（n）+ O（nlogn）+ O（1）+ O（nlogn）。所以，記憶問題分開，這取決於你想要計算中位數的頻率。 – ChronoTrigger

有至少兩個原因，你提出解決方案通常不使用：

一般來說，假設如果你正在處理的數據流，該流是巨大的，甚至無限的存儲等等所有的價值都不實際。
正如@ChronoTrigger所說，你必須對你的向量進行排序才能使用它。這個問題通常假設你希望能夠反覆詢問中位數作爲新的數據流。爲了用你的解決方案做到這一點，你必須反覆排序你的向量，這將是緩慢的。

總的來說，在流數據集上保持一個精確的中位數很難高效。有很多算法可以做到這一點，但是它們都會降低內存使用的準確性等。

來源

2015-10-20 00:30:00

謝謝奧利弗！我看到你不斷地對矢量進行排序的重點，但是，對於堆方法，我們還不需要存儲整個數據流嗎？ – firefly

是的，對於堆方法，您仍然需要存儲整個流。請注意，您在SO帖子上的第一個響應是關於與該方法有關的內存問題的討論。 –

向量只在將新元素添加到其正確位置時才起作用（根據排序訂購）。

例如：流：在每一步8 3 4 1 10 12

中值，如果你只是保持在載體的末端添加元素：

step 1: vector: 8 median: 8 
step 2: vector: 8, 3 median: (8+3)/2 
step 3: vector: 8, 3, 4 median: 3 (when actually it should be 4)

希望你的想法

來源

2015-10-20 00:31:14 pgiitu

從流中找到運行媒體

回答

相關問題