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查询解决方案

回答

相关问题