高效計算數據流中頻繁和高位元素

Question

這裏是該算法的pseduo代碼。

以下是如何我已經實現了這一點。

#include <iostream> 
#include <fstream> 
#include <string> 
#include <map> 

typedef std::map<std::string, int> collection_t; 
typedef collection_t::iterator collection_itr_t; 

collection_t T; 

collection_itr_t get_smallest_key() { 
    collection_itr_t min_key = T.begin(); 
    collection_itr_t key  = ++min_key; 
    while (key != T.end()) { 
     if (key->second < min_key->second) 
      min_key = key; 
     ++key; 
    } 
    return min_key; 
} 
void space_saving_frequent(std::string &i, int k) { 
    if (T.find(i) != T.end()) 
     T[i]++; 
    else if (T.size() < k) { 
     T.insert(std::make_pair(i, 1)); 
    } else { 
     collection_itr_t j = get_smallest_key(); 
     int cnt = j->second + 1; 
     T.erase(j); 
     T.insert(std::make_pair(i, cnt)); 
    } 
} 
int main (int argc, char **argv) { 
    std::ifstream ifs(argv[1]); 
    if (ifs.peek() == EOF) 
     return 1; 
    std::string line; 
    while(std::getline(ifs,line)) { 
     std::string::size_type left = line.rfind('=') + 1; 
     std::string::size_type length = line.length(); 
     std::string i  = line.substr(left, length - left - 1); 
     space_saving_frequent(i, 5); 
    } 
    ifs.close(); 
    return 0; 
} 

原紙鏈接：http://dimacs.rutgers.edu/~graham/pubs/papers/freqcacm.pdf

但代碼不能正常工作，我沒有能夠找出其中我錯了。

Answer 1

如果最少計數的項目是兩個或更多，您可以通過選擇例如索引最低的項目存儲在您的數據結構中或任意一個最低計數等項目中來任意斷開關係。

如果你想比較你的實現和參考，看看Cormode和Hadjieleftheriou的實現，你會發現here。代碼比您的代碼更復雜，因爲您實際上並未實現流彙總數據結構。他們的代碼還包括其他幾種頻繁項目算法的實現，作者比較了這些算法的性能。在大多數情況下，節省空間是最好的算法，關於精度，召回率，更新速度，使用空間等幾項指標。您還將找到一篇討論此實驗性比較的論文。本文的改進版本出現在ACM的Communications中。 Here你可以訪問pdf版本。