top-k查詢解決方案

有沒有人有top-k查詢問題的解決方案。問題是我有無限數量的流，我需要拿出解決方案，這將給我流中的前k項。top-k查詢解決方案

這是面試問題。我正在尋找C++解決方案。

這是我將如何解決這個問題。但在這裏我將需要閱讀整個stream/file

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

typedef std::map<std::string, int> freq_table_t; 
typedef std::multimap<std::size_t, freq_table_t::const_iterator> top_n_t; 
size_t n = 5; 

int main (int argc, char **argv) { 
    std::ifstream ifs(argv[1]); 
    if (ifs.peek() == EOF) 
     return 1; 

    std::string line; 
    freq_table_t freq_table; 

    while(ifs.good()&& std::getline(ifs,line)) { 
     if (freq_table.insert(std::make_pair(line, 1)).second == false) 
      freq_table[line]++; 
    } 
    ifs.close(); 

    top_n_t top5; 
    for (freq_table_t::const_iterator it = freq_table.begin(); it != freq_table.end(); ++it) { 
     if (top5.size() < n || it->second > top5.begin()->first) 
      top5.insert(std::make_pair(it->second, it)); 
     if (top5.size() == n + 1) 
      top5.erase(top5.begin()); 
    } 
    for (top_n_t::reverse_iterator ritr = top5.rbegin(); ritr != top5.rend(); ++ritr) 
     std::cout << ritr->second->first << std::endl; 

    return 0; 
}

來源

2011-12-21 avinash dongre

面試已經結束，我無法回答，也沒有在google上找到答案，所以我正在找人解釋我的解決方案 – 2011-12-21 18:55:03

我不認爲這是一個完全不公平的問題，他顯然不是，現在正在接受採訪。我會把它當作一個家庭作業問題來對待，並且引導OP給出答案，而不是隻給他一個答案。另外，我對此很好奇。 – 2011-12-21 18:55:20

詢問Q's在這裏是不禁止的，請將您的意見添加到關於您對解決方案的看法的問題上，或者至少對您的想法有所瞭解，即使這是最微不足道的想法。投票重新開放。 – 2011-12-21 18:59:38

創建std::set<int> top
對於您從流得到數：
- 將號碼添加到集合
- - 如果top.size() > k，刪除該集合的最小元素。

在每一個點，top最多包含在一套k最大的項目（數目將少於k如果有流中少於k不同的項目了這一點）。在C++中編碼應該是微不足道的。

來源

2011-12-21 18:55:57 dasblinkenlight

您正在給出最大的k值，avinash正在尋找最頻繁的k，基於freq_table等，在海報的代碼中。 – James 2011-12-22 03:31:57

@James我回答了問題後添加了代碼。 OP包含前三行。 – dasblinkenlight 2011-12-22 03:34:16

概括dasblinkenlight的回答：

保持最小優先級隊列。對於流中的每個元素，將元素與隊列中的最小元素進行比較。如果它更大，則將最小元素出列並排入新元素。作爲基本情況，將隊列初始化爲流的第一個k元素。

在流的末尾，您的優先級隊列將包含最大的k元素。

鑑於n元素在流中，此算法將在n log k時間運行。

來源

2011-12-21 19:30:11 tskuzzy

我想OP是要求k - 最頻繁的元素，而不是最大的流 – brainydexter 2011-12-22 12:27:54

top-k查詢解決方案

回答

相關問題