トップ-Kクエリソリューション

Question

誰もトップ-kクエリ問題の解決法を持っていますか？ 問題は私が無限の数のストリームを持っていることで、私はストリームのトップkアイテムを与える解決策を考え出す必要があります。

これはインタビューの質問です。私はC++のソリューションを探しています。

これはどのように問題を解決するのですか。しかし、ここで私はあなたがストリームから取得した各番号についてはstd::set<int> top

作成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; 
} 

Answer 1

• 全体を読む必要があります： - セット
• に番号を追加
• を - - top.size() > kの場合は、セットの最小要素を削除します。各時点で

、topはセット内k最大アイテムまで含有する（ストリームにおける未満k異なるアイテムここまでがあった場合に数未満kとなります）。 これをC++でコーディングするのは簡単ではありません。

Answer 2

一般化dasblinkenlightの答え：

最小優先度キューを維持します。ストリームの各要素について、要素をキューの最小要素と比較します。それが大きい場合は、最小の要素をデキューして新しい要素をエンキューします。基本ケースとして、ストリームの最初のk要素にキューを初期化します。

ストリームの最後には、優先度キューに最大のk要素が含まれます。

ストリーム内の要素がnであれば、このアルゴリズムはn log k時間で実行されます。