アイテムの2つのストリームを読み取って重複したアイテムを収集しない方法

Question

2つの大きなリストまたはストリームのデータがあり、両方を読み込み、1つのストリームのみにあるアイテムを収集するとします。

サンプル：

リスト＃1：1、4、5

リスト＃2：1、3、5、6

結果：4、3、6

注1：両方のリストは大きすぎますので、並べ替えたいわけではありません。

注2：各ストリームのアイテムは固有です。 1つのリストに重複している項目を心配する必要はありません。

この操作を実行するにはどのような方法が最速ですか？

ありがとうございます。

Answer 1

ストリームが1つのみで、ストリームがソートされていない場合は不可能です。それ以外の場合は、ハッシュテーブルを使用することができますが、実際にはソートよりも少し速いです。

また、http://en.wikipedia.org/wiki/MapReduceのアプローチをご覧ください。あなたが本当に大きなデータを持っているなら、それは良い解決策です。

Answer 2

各値が何回発生するかをカウントします。一度発生する値のみを出力します。

#include <unordered_map> 
#include <vector> 
#include <iterator> 
#include <iostream> 

template<typename InputIterator, typename OutputIterator> 
void 
uniq (InputIterator b0, InputIterator e0, 
     InputIterator b1, InputIterator e1, 
     OutputIterator u) 
{ 
    std::unordered_map<typename std::iterator_traits<InputIterator>::value_type, int> m; 

    while (b0 != e0) 
     ++m [*b0++]; 

    while (b1 != e1) 
     ++m [*b1++]; 

    for (auto &mi : m) 
    { 
     if (mi.second == 1) 
     *u++ = mi.first; 
    } 
} 

int 
main() 
{ 
    std::vector<int> s0 ({1, 4, 5}); 
    std::vector<int> s1 ({1, 3, 5, 6}); 
    std::vector<int> r; 

    uniq (s0.begin(), s0.end(), s1.begin(), s1.end(), std::back_inserter (r)); 

    for (auto i : r) 
    std::cout << i << " "; 
}