効率的に大規模な参照を検索する方法:: map

Question

2つの大きなキー値リストの推移的クロージャを実行したい。そうするために、私は2つの "std :: map"を持っています。両方のstd :: mapは整数を整数のベクトルに写像します。

std::map<unsigned,vector<unsigned> > mapIntVecOfInts1; 
std::map<unsigned,vector<unsigned> > mapIntVecOfInts2; 

"mapIntVecOfInts1は、" キー（VALUES）の別のセットにキーをマッピング。その中の一例値のいくつかは、以下の形式です：

0 -> (101, 102, 201) 
1 -> (101, 102, 103, 203, 817, 1673) 
2 -> (201, 829, 858, 1673) 

「mapIntVecOfInts2は、」値の別のセットに「mapIntVecOfInts1」に存在する値をマッピングします。例えば

101 -> (4002, 8293, 9000) 
102 -> (4002, 8293, 10928) 
103 -> (8293, 10928, 19283, 39201) 
201 -> (8293) 
203 -> (9393, 9830) 
817 -> (19393, 19830) 
1673-> (5372, 6830) 

は今、私は「mapIntVecOfInts2」に「mapIntVecOfInts1」から推移マッピングを使用して、「mapIntVecOfInts2」に存在する値に「mapIntVecOfInts1」に存在するキーをマップします。例えば。私はmapIntVecOfInts1のキー「0」のために次の操作を実行したい：

0 -> 4002, 9000, 10928, 8293, 19283, 39201 
1 -> 4002, 8293, 9000, 10928, 19283, 39201, 9393, 9830, 19393, 19830, 5372, 6830 

「mapIntVecOfInts1」と「mapIntVecOfInts2は」億の要素（キー）を含有します。 2つのマップ自体のベクトルには、符号なし整数が100万個含まれています。私は "mapIntVecOfInts1"と "mapIntVecOfInts2"をメモリに格納することによって、2つのマップ間でこの推移的閉包を実行しようとしました。次のコードを使用します。

ただし、この方法で推移的閉包を実行するには、時間がかかります。私はこれをスピードアップできる方法がありますか？

Answer 1

少なくとも、内部ループのベクトルの最後に挿入する必要があります。先頭に挿入すると、すでにベクトルにある要素をコピーする必要があるためです。

vec1.insert(vec1.end(), mapIntVecOfInts2[*i2].begin(), mapIntVecOfInts2[*i2].end()); 

また、値が重複しないようにするには、セットの使用を検討してください。

Answer 2

一つは、あなたの提案のコードは2つのことをしていると言うことができます。

• が最初
• のエントリへの第2の関係をマッピングした結果から、新たな関係を構築マッピング

を言いました

結果のマップは、最初のリレーションと全く同じキーセットを持つので、最初にmapIntVecOfInts1全体をコピーしてから、コピーの値を追加するのではなく、 vecひとつずつ変えていく。

もちろん、2番目の関係（mapIntVecOfInts2）のアクセス速度である大きなボトルネックは修正されません。 「十億の鍵」があまり疎でない場合は、ハッシュテーブル（std::unordered_map）で償却されたO（1）に、あるいはベクトルでさえも減らすことができます。

また@SpectralSequenceによると、あなたのコードは値ベクトルの一意性を保持していませんが、おそらくあなたはそれについて何かしたいと思っています。