0

我有 N 个元素需要相互比较才能创建图表。它总共给出(N*N-1)/2 次比较。

我想多线程这些比较我也有几个限制：

  • 每个元素都很大，实际上是一个矩阵，所以在每个线程中复制所有元素会占用太多内存。

  • 每个比较都应该发生，这意味着我不能跳过一个。

  • 每次可以在列表中添加一个新元素时，这非常棘手，因为我需要跟踪已完成的操作，只做新的。

  • 由于比较的数量可能很大，比如 2000 万，我不能排那么大的队列。

  • 最后，可以随时停止该过程，我必须能够恢复我什至在应用程序的其他执行中的位置。

到目前为止，我有一个主线程，其中包含线程池中的所有元素和几个工作线程。工作线程比较一组对或一系列元素。我想到了一个比较生成器，它可以按需提供下一个 X 比较。

我怎么能建造这个生成器？

我应该为工人复制每一对，直接从工人那里使用 ReadWriteLock 从 Master 读取数据吗？

我如何跟踪每个线程的进度？

我怎样才能停止并恢复比较状态？

如果有很多问题，我很抱歉。谢谢 ！

4

1 回答 1

0

假设读取是线程安全的（通常只要没有人在写入），一个简单的解决方案是以某种方式在一组工作线程中细分任务，提前这样做。例如，对于n 个工作人员，您可以将对 ( x , y ) 分配给工作人员x mod n。唯一的通信是让每个工人知道它的序数（0…<em>n-1）。每个线程都应将其答案放入一个私有数组中，其他人完成后可以对其进行整理。

适应不同工人生产力的更复杂的模型是将每个值 0…<em>N-1 推送到队列中。每个工作线程从队列中拉出一个数字x，评估每个 ( x , y ) 对，然后返回另一个x。

如果您想花时间，将对排队以最大程度地减少缓存抖动会更有效。这是一个棘手的问题。本质上，您希望将小元素簇中的元素对排入队列，以便几乎同时评估簇中的每一对元素。尽管这很棘手，但它可能会对算法的效率产生巨大影响。

于 2013-01-22T21:30:11.537 回答