c++ - 并行程序中的多图或排序向量

Question

我有一个必须并行化的程序。它可能包含大量数据。这些数据可以通过一个 id 来标识，并且更多的数据可以具有相同的 id。我的程序的每个线程都会恢复具有特定 id 的所有数据并对其进行处理。

我的问题是对于并行程序，最好的解决方案是使用按数据 id 排序的多图或向量？

谢谢你。

Answer 1

抽象数据类型并实现通用解决方案。然后替换这两种数据类型，看看哪一种表现更好。

Answer 2

这取决于数据的大小。例如，如果您有数据A B C并且D大小为 2、10、20、30，并且使用 4 个线程运行，那么您将遇到负载平衡问题。线程 A 将比其余线程做更少的工作。不幸的是，对数据进行排序对您没有帮助。

将数据存储在堆栈中（例如）并让线程独立于 id 从堆栈中完成工作可能会更好。但是，您必须同步堆栈。

如果您事先知道每个 id 数据包含的大小，则可以将它们分组为由数据 id 组成的块。这些块将具有大致相同的大小。

然后你可以制作一个映射<K,V>，其中V将是块和K将计算这些块的线程的 id。

Answer 3

unordered_map 可能是一个很好的解决方案。由于它是作为散列实现的，相同的 id 最终会出现在相同的桶中。
此外，哈希表在处理大型数据集时也很好，因为它们提供了一种将数据分组到可以单独处理的存储桶中的机制。