快速中值更新算法

假設在某個時間點，您有一個N數字的集合，並且知道中間元素：M。現在，您獲得了一個新值X，因此您可能需要更新M。（或者說，假設你所處理的數字都是唯一的，並且所有的樣本都是串行接收的，所以併發性沒有問題。）快速中值更新算法

計算新的均值非常簡單：take老的意思是，加X，乘以N，除以N + 1。（從檢查N元素的平均值是如何定義的，這一點很明顯，目前我並不太在意數值）

我的問題是：任何人都可以提出一個創意/最優）方法更新中位數的問題？我將在下面提供一個例子（簡單介紹我自己的設計），並進行一些分析：

在本示例中，我將使用std::forward_list，因爲C++ 11是我最近遇到的這種情況。在不失一般性的情況下，我會假設你正在以正確的方式進行：維護到目前爲止遇到的元素（類型T）的有序列表，std::forward_list<T> sorted;出現T x;時，只需使用以下代碼將其摺疊到位：

sorted.merge(std::forward_list<T> {{ x }});

順便說一下，我很好奇，如果任何人有一個更好（更有效/優雅）的方法。 Gripes歡迎。

所以，X現在是sorted一部分，這是我的想法，概括地說：

auto it = sorted.begin(), itend = sorted.end(); 
typename std::forward_list<T>::size_type count = std::distance(it, itend); 
for (const auto &e : sorted) { 
    if (it == itend || ++it == itend) { 
     M = (count % 2) ? e : (e + M)/2; 
     break; 
    } else { ++it; } 
}

這裏發生的是，漂亮的（如果不是有點難以看到）的事情：因爲你移動迭代器轉發兩次（並且安全，我可能會添加，但以兩個比較爲代價），當達到end()時，我們將處於適當的（中值）值。如果存在奇數個元素，則M就是該樣本，如果不是，則只是該元素的平均值和舊（推出）中值。由於奇數和偶數交替出現，舊的或新的M實際上將在集合中。這個推理是合理的，是嗎？

如果你認爲它是垃圾/你的好得多，你不需要評論我的O（3n）方法;我只是把它作爲一個起點。

來源

2013-06-13 Tor E Hagemann

你當然可以做到在O（日誌（n））的時間。將元素添加到平衡二叉樹並選擇第k個最大元素都是O（log（n））時間操作。對於更有趣的事情，也許嘗試2堆，其中一個用於n/2個最大的元素，另一個用於最小的元素。 –

@MarcGlisse：看到我的答案，你不必搜索第k個大元素，因爲你已經知道它或第（k + 1）個或第（k-1）個最大元素:-) –

@SauceMaster看起來你正在跟蹤列表中出現次數最多的元素。這不是中位數。 –

你可以使用一個std::set，插入到集合的事實不會使迭代器無效。

可以容納一個迭代mIt到集合的中間元素，如果N是奇數，並且兩個中間元素的左邊，如果N是偶數。

讓我們考慮一下，你可以有不同的情況下，當你插入元素：

插入時N是奇數：如果插入的元素比*mIt較小，舊位數變成右邊的兩個新的中位數的元素，所以遞減迭代器。如果它更大（或等於multiset），一切都很好。
當N是偶數時插入：如果插入的元素大於（或等於）*mIt，則舊的正確的中位數變爲中位數，因此增加迭代器。如果它更小，那麼左邊的中位數就會變成中位數，一切都很好。

template <class T> 
class MedianHolder { 
    std::set<T> elements; 
    std::set<T>::const_iterator mIt; 

public: 
    T const& getMedian() const { return *mIt; } 

    void insert(T const& t) { 
    if (elements.empty()) { 
     mIt = elements.insert(t).first; 
     return; 
    } 

    bool smaller = std::less<T>(t,getMedian()); 
    bool odd = (elements.size() % 2) == 1; 

    if (!elements.insert(t).second) 
     return; //not inserted 

    if (odd && smaller) --mIt; 
    else if (!odd && !smaller) ++mIt; 
    } 
};

我會離開擦除元素作爲練習你;-)

來源

2013-06-13 13:02:44

您可以分割你的陣列詮釋2種堆樹木，大小相等，至少部分或陣列的I和S是最大的部分，和其前端包括最大和最小的元素。說陣列1, 2, 4, 4, 5, 5, 7, 8, 8, 8組織是這樣的：

1 4 
\/
    4 2 
    \/
    5 <--- I's top 

    5 <--- S's top 
/\ 
    7 8 
/\ 
8 8

請注意，如果元件的數目是偶數，則中值=頂部（S）+頂部（I），如果奇數，則堆之一thould是一個元件比大其他，中位數位居首位。

完成此操作後，更新中值很簡單，如果top（S）變得小於top（I），您應該將您的元素添加到其中一個堆並交換它們的頂端。

來源

2013-06-13 11:53:16 Vovanium

快速中值更新算法

回答

相關問題