0

假设我有一组需要成对处理的数据（对元素的顺序无关紧要，所以这些是组合，而不是排列），我想利用多个线程来这样做。但是，我受到限制，每条数据一次只能由一个线程处理。我正在寻找一种能够提供良好分区策略的算法，通过该策略我可以将数据对分配给线程，同时针对任何大小的数据集一次覆盖可能组合的整个空间。假设每个可能对的处理时间相等。

例如，假设我有 6 条数据：D0、D1、D2、D3、D4 和 D5。

为了优化处理这些，我会做这样的事情：

               Thread 1    Thread 2    Thread 3
Time Slot 1     (D0,D5)     (D1,D4)     (D2,D3)
Time Slot 2     (D0,D4)     (D1,D3)     (D2,D5)
Time Slot 3     (D0,D3)     (D1,D2)     (D4,D5)
Time Slot 4     (D0,D2)     (D1,D5)     (D3,D4)
Time Slot 5     (D0,D1)     (D2,D4)     (D3,D5)

同理，对于8条数据：D0、D1、D2、D3、D4、D5、D6、D7

               Thread 1    Thread 2    Thread 3    Thread 4
Time Slot 1     (D0,D7)     (D1,D6)     (D2,D5)     (D3,D4)
Time Slot 2     (D0,D6)     (D1,D5)     (D2,D4)     (D3,D7)
Time Slot 3     (D0,D5)     (D1,D4)     (D2,D3)     (D6,D7)
Time Slot 4     (D0,D4)     (D1,D3)     (D2,D7)     (D5,D6)
Time Slot 5     (D0,D3)     (D1,D2)     (D4,D6)     (D5,D7)
Time Slot 6     (D0,D2)     (D1,D7)     (D3,D6)     (D4,D5)
Time Slot 7     (D0,D1)     (D2,D6)     (D3,D5)     (D4,D7)

以上是我自己手工计算出来的，但是我必须使用的过程对于每个都略有不同，因此似乎很难转换成代码来为更大的数据集生成这些。有什么想法可以让算法正确有效地生成这些对吗？试图寻找解决方案，但不确定如何更好地表达问题以获得我正在寻找的结果。

4

2 回答 2

0

另一种方法可能是

  • 创建具有所有组合的作业队列
  • 创建一个指示任务状态的状态数组（true 正在运行，false 未运行）
  • 将 tasksToBeProcessed 初始化为队列中的作业数

有一个工作线程，它运行具有以下逻辑 

while(tasksToBeProcessed > 0) {  
    Remove next job from the job queue
    //check the status array
    if (Both the tasks are not running)
        Change the status array and mark tasks as running
    else
        Put the job back in the queue
    continue;

    //process the tasks
    Decrement tasksToBeProcessed by 1
}

在这里，工作线程继续处理作业，直到没有作业要处理。这不需要任何线程旋转。唯一重要的是在访问状态数组和队列时检查线程安全性

于 2013-09-06T10:58:22.493 回答
0

有什么想法可以让算法正确有效地生成这些对吗？

一个简单的解决方案是创建一个与您的每个数据片段相对应的布尔使用中数组。当数据正在处理时，它变为 true，然后当对它们的工作完成时，它返回 false。您还创建了一个待完成队列所有数据片段的组合：[d0, d1], [d0, d2], [d0, d3], ....

有一个调度程序线程，该线程通过待完成队列并找到两个数据片段当前未使用的数据对。它检查两个数据块的使用中数组，将两个数据项的使用中数组设置为真，并将该对放入工作队列中以由线程处理。当它找到其中一个（或两个）都在使用中的一对时，它会将其添加到待完成队列的末尾。在返回结果时，它会将使用中状态设置回 false。重复直到待完成队列为空且所有正在使用为假。

这个单一的调度程序线程在发现冲突时会旋转一点，但与处理相比，旋转的数量应该是 CPU 的相对较小的百分比。

所以它会这样做：

  • 检查 [d0, d1]。都没有使用。d0 现在正在使用中。d1 现在正在使用中。日程。
  • 检查 [d0, d2]。d0 正在使用中。
  • 检查 [d0, d3]。d0 正在使用中。...
  • 检查 [d1, d2]。d1 正在使用中。...
  • 检查 [d2, d3]。都没有使用。d2 现在正在使用中。d3 现在正在使用中。日程。...

最初会有很多旋转，但对布尔数组的检查是一项微不足道的工作。改进它的一件事是不时地打乱待完成的队列。

于 2013-09-05T22:16:21.307 回答