c++ - 如何有效地查找大型 std::map

Question

我想执行 2 个大键值列表的传递闭包。为此，我有两个“std::map”。 std::map 都将整数映射到整数 vector 。

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)

现在我想使用从“mapIntVecOfInts1”到“mapIntVecOfInts2”的传递映射将“mapIntVecOfInts1”中存在的键映射到“mapIntVecOfInts2”中存在的值。例如。我想对 mapIntVecOfInts1 的键“0”执行以下操作:

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

“mapIntVecOfInts1”和“mapIntVecOfInts2”包含十亿个元素(键)。两个映射中的 vector 本身包含百万个无符号整数。我尝试通过在内存中存储“mapIntVecOfInts1”和“mapIntVecOfInts2”来执行两个映射之间的传递闭包。使用以下代码:

std::vector<unsigned,vector<unsigned> > result;
for(std::map<unsigned,vector<unsigned> >::iterator i1= mapIntVecOfInts1.begin(), l1=mapIntVecOfInts1.end(); i1!=l1;++i1)
{
    vector<unsigned> vec1;
    for(vector<unsigned>::iterator i2=(*i1).second.begin(), l2=(*i1).second.end(); i2!=l2; ++i2)
         vec1.insert(vec1.begin(), mapIntVecOfInts2[*i2].begin(), mapIntVecOfInts2[*i2].end());

     result.push_back(make_pair((*i1).first, vec1));
}

但是，以这种方式执行传递闭包会花费大量时间。有什么方法可以加快速度吗？

Answer 1

可以说您建议的代码做了两件事:

• 将第二个关系映射到第一个条目
• 根据上述映射的结果建立新的关系

生成的映射将具有与第一个关系完全相同的键集，因此您可以(某种程度上)通过先复制整个 mapIntVecOfInts1 来避免整个红黑树构建过程，然后再复制修改拷贝的值，而不是一个一个地添加 vector 。

当然，这不会解决主要瓶颈，即第二个关系 (mapIntVecOfInts2) 的访问速度。您可以尝试使用哈希表 (std::unordered_map) 或什至是 vector (如果您的“十亿键”不是太稀疏)将其减少到分摊 O(1)。

另外正如@SpectralSequence 所说，您的代码没有保留值 vector 中的唯一性，也许您想对此做些事情。