与 C++ 的并行性 unordered_map

Question

我有一个 unordered_map 类型 std::unordered_map<std::string, int64_t> sMap。这包含许多字符串和与每个字符串关联的 'weight'。我想找到权重最大的N个字符串。

如果我想使用单个线程来执行此操作，我想我可以像这样创建一个成对的优先级队列

std::priority_queue<
    std::pair<std::string, int64_t>,
    std::vector<std::pair<std::string, int64_t>>,
    std::function<bool(std::pair<std::string, int64_t>&,
            std::pair<std::string, int64_t>&)>> prQ(comparePair);

然后遍历整个 unordered_map，将元素插入 prQ，同时保持长度 N。

我想使用多线程实现相同的目的。我正在考虑分配每个线程来处理 unordered_map 的几个元素，以创建一个长度为 N 的本地优先级队列，最后可以将其合并到一个全局优先级队列中。

我现在面临的问题是我从 unordered_map::begin() 获得的迭代器不能与 + 运算符一起使用。至少那是我得到的错误： error: no match for ‘operator+’ (operand types are ‘std::unordered_map<std::basic_string<char>, long int>::iterator {aka std::__detail::_Node_iterator<std::pair<const std::b asic_string<char>, long int>, false, true>}’ and ‘int’) 因此，我无法真正指定要由特定线程处理的元素范围。 [] 运算符将按预期采用键而不是偏移量。

基本上，我似乎无法找到一种方法来实现数据并行循环，每个线程只处理几个元素。那么如何使用多线程解决这个问题呢？

编辑：@Brian Vandberg 让我提供一个简化的代码示例，该代码生成了我正在谈论的错误。

std::unordered_map<std::string, int64_t> sMap;
//Initialize sMap values
int start = 0, end = 2;
for(auto i = sMap.begin() + start; sMap.begin() + end; ++i) {
    std::cout<<i->first<<"\t"<<i->second<<"\n";
}

Answer 1

首先，我不确定我是否会使用优先级队列来解决这个问题（单线程，或者作为特定线程执行的部分）。标准库有nth_element，你可以用它在线性时间内找到第n个元素。之后，找出哪些元素更大也是线性时间。

如果速度有问题，您可能会考虑这个，如果大小有问题，您可能会考虑（nth_element 将有效地强制您创建数据副本）。在此解决方案中，您迭代地图（或地图的一部分），并且 push_back 仅将权重转换为 vector，您在其上执行 nth_element。第二阶段，再次遍历地图，选择权重高的。

假设你有循环：

std::size_t j = 0;
for(const auto &e: sMap)
{
    if(++j % k != i)
        continue;
    // Rest of code goes here.
}

然后，如果您将它用于 k 中的第 i 个线程，它将在线程之间划分元素。此外，虽然所有线程都在相同的元素上迭代（如果只是为了跳过其中的大部分），它是并行发生的。

每个线程可以为最大的m个元素生成候选，然后从中选择最大的m个元素km 候选人使用上述方法（使用 nth_element）或任何其他方法。

有趣的是 sMap 的大小会在实践中产生任何加速。

与 C++ 的并行性 unordered_map

Parallelism with C++ unordered_map

c++

multithreading

unordered-map

c++11