我怎样才能使用多线程来计算一个非常大的数据集的交集

Question

我有一个由400万组组成的文件。每组包含 1 到 n 个单词。文件大小为 120 MB。

set1 = {w11, w12,...,w1i}
set2 = {w21, w22,...,w2j}
...
setm = {wm1, wm2,...,wmk}

我想计算所有集合之间的交集。

Set 1 ∩ {set1,...,setm}
Set 2 ∩ {set1,...,setm}
...
Set m ∩ {set1,...,setm}

每个操作大约需要 1.2 秒。我做了以下事情：

将400万套分成6块。每个块包含 666666 集合

然后我执行以下操作。在这里，我将创建 36 个线程，我将计算块之间的交集。它太慢了，我把问题复杂化了。

 vector<thread> threads;
 for(int i = 0; i< chunk.size();i++)
  {
    for(int j = 0; j < chunk.size();j++)
    {
       threads.push_back(thread(&Transform::call_intersection, this, ref(chunk[i]),ref(tmp[j]), chunk(results)));
    }
  }

for(auto &t : threads){ t.join(); }

你有没有想过如何将问题分解成子问题，然后最后将它们连接在一起。 linux 也有什么好的方法吗？

示例

第一列代表集合的ID，其余列代表单词。

m.06fl3b|hadji|barbarella catton|haji catton|haji cat|haji
m.06flgy|estadio neza 86
m.06fm8g|emd gp39dc
m.0md41|pavees|barbarella catton
m.06fmg|round
m.01012g|hadji|fannin county windom town|windom
m.0101b|affray

例子

m.06fl3b 与 m.01012g 和 m.0md41 有交集。输出文件如下：

 m.06fl3b m.01012g m.0md41
 m.06flgy
 m.06fm8g
 m.0md41 m.06fl3b
 m.06fmg
 m.01012g  m.06fl3b
 m.0101b

Answer 1

集合交集关联，因此适合parallel folding (which is one of many use cases of MapReduce)。对于每一对集合 ((1, 2), (3, 4), ...)，您可以计算每一对的交集，并将结果放入一个新的集合集合中，该集合的大小将减半。重复，直到你只剩下一组。交集运算的总数将等于集合数减一。

然而，启动数百万个线程会使您的机器陷入困境，因此您可能希望使用 线程池：您可用的 CPU 个核心数量，并创建一个 任务列表 ，其中每个任务都是要相交的两组。每个线程反复检查任务列表并获取第一个可用任务（确保以线程安全的方式访问任务列表）。

我怎样才能使用多线程来计算一个非常大的数据集的交集

how can I use multithreading to compute the intersection on a very large dataset

multithreading

algorithm

intersection

示例

例子