我有一堆数据(一个巨大的 0 到 ULLONG_MAX 之间的整数列表)，我想提取所有唯一值。我的方法是创建一个 unordered_map，使用整数列表值作为键，使用一次性 bool 值作为映射值。我迭代列表并为每个键插入一次性值。最后，我迭代 map 以获取所有唯一键。非常简单。

但是，我的列表非常大(数以亿计)，我想对这个进程进行多线程处理。我知道一种天真的线程方法是行不通的，因为 unordered_map 插入会影响底层数据结构，因此它不是线程安全的。并且在每次插入周围添加锁会很慢，并且可能会抵消任何线程加速。

然而，大概不是每次插入都会改变数据结构(只有那些不能适应现有分配桶的插入？)。有没有办法在插入之前检查特定插入是否需要 unordered_map 重新分配？这样我只能在 map 发生变化时锁定线程，而不是在每次插入时都锁定。然后，在每次插入之前，线程仅检查是否存在锁……而不是进行完全锁定/解锁。这可能吗？

最佳答案

并行化的基本规则是将工作分解，处理各个部分，然后组合各个部分。

散列/项目查找是整个 shebang 中最昂贵的部分，因此这就是我们将重点关注的并行化。

如果您绝对需要将结果作为哈希表，我有一些坏消息要告诉您:您必须自己编写。话虽如此，让我们开始吧。

首先，让我们串行解决问题。这很简单。下面的函数接受一个 vector 和一个回调。我们将获取 vector ，将其转换为 unordered_set，并将 unordered_set 提供给回调。简单的？是的。

现在，因为我们要在线程上执行此操作，所以我们不能马上执行。相反，我们将返回一个不带参数的 lambda。当调用该 lambda 时，它会创建 unordered_set 并将其提供给回调。这样，我们可以将每个 lambda 赋予它自己的线程，每个线程将通过调用 lambda 来运行作业。

template<class Vector, class Callback>
auto lazyGetUnique(Vector& vector, Callback callback) {
    using Iterator = decltype(vector.begin());
    auto begin = vector.begin();
    auto end = vector.end();
    using elem_t = typename std::iterator_traits<Iterator>::value_type;

    //We capture begin, end, and callback
    return [begin, end, callback]() {
        callback(std::unordered_set<elem_t>(begin, end));
    };
}

现在 - 这个回调应该做什么？答案很简单:回调应该将 unordered_set 的内容分配给一个 vector 。为什么？因为我们要合并结果，合并 vector 比合并 unordered_set 快很多。

让我们写一个函数来给我们回调:

template<class Vector>
auto assignTo(Vector& v) {
    return [&](auto&& contents) {
        v.assign(contents.begin(), contents.end());
    };
}

假设我们想要获取 vector 的唯一元素，并将它们分配回该 vector 。现在这很容易做到:

std::vector<int> v = /* stuff */;
auto new_thread = std::thread( lazyGetUnique(v, assignTo(v)) ); 

在这个例子中，当new_thread 完成执行时，v 将只包含独特的元素。

让我们看看完成所有事情的完整函数。

template<class Iterator>
auto getUnique(Iterator begin, Iterator end) {
    using elem_t = typename std::iterator_traits<Iterator>::value_type;

    std::vector<elem_t> blocks[4];

    //Split things up into blocks based on the last 4 bits
    //Of the number. This allows us to guarantee that no two blocks
    //share numbers. 
    for(; begin != end; ++begin) {
        auto val = *begin; 
        blocks[val & 0x3].push_back(val); 
    }

    //Each thread will run their portion of the problem.
    //Once it's found all unique elements, it'll stick the result in the block used as input
    auto thread_0 = std::thread( lazyGetUnique(blocks[0], assignTo(blocks[0])) );
    auto thread_1 = std::thread( lazyGetUnique(blocks[1], assignTo(blocks[1])) );
    auto thread_2 = std::thread( lazyGetUnique(blocks[2], assignTo(blocks[2])) );

    //We are thread_3, so we can just invoke it directly
    lazyGetUnique(blocks[3], assignTo(blocks[3]))(); //Here, we invoke it immediately

    //Join the other threads
    thread_0.join();
    thread_1.join();
    thread_2.join(); 

    std::vector<elem_t> result;
    result.reserve(blocks[0].size() + blocks[1].size() + blocks[2].size() + blocks[3].size());

    for(int i = 0; i < 4; ++i) {
        result.insert(result.end(), blocks[i].begin(), blocks[i].end());
    }

    return result;
}

这个函数将内容分成 4 个 block ，每个 block 都是不相交的。它在 4 个 block 中的每个 block 中找到唯一元素，然后组合结果。输出是一个 vector 。

关于c++ - std::unordered_map:多线程插入？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53799491/