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

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

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

“mapIntVecOfInts1”将键映射到另一组键(值)。其中的一些示例值具有以下形式:

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”在两个 map 之间执行此传递闭包。使用以下代码:

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));
}

但是，以这种方式执行传递关闭需要大量时间。有什么办法可以加快速度吗？

最佳答案

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

将第二个关系映射到第一个

的条目

从所述映射

的结果建立新的关系

生成的 map 将具有与第一个关系完全相同的键集，因此您可以(有点)避免整个红黑树的构建过程，只需先复制整个mapIntVecOfInts1，然后修改复制的值，而不是添加 vector 逐个。

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

就像@SpectralSequence所说的那样，您的代码没有保留值 vector 中的唯一性，也许您想对此做些什么。

关于c++ - 如何有效查找大型std::map，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41083585/