多线程 - 一组中所有对之间的计算

Question

我有 n 个元素（例如 A、B、C 和 D），需要在所有这些元素之间进行计算。

Calculation 1 = A with B  
Calculation 2 = A with C  
Calculation 3 = A with D  
Calculation 4 = B with C  
Calculation 5 = B with D  
Calculation 6 = C with D

实际上有超过 1000 个元素，我想并行处理这个过程。

请注意，我无法同时从 2 个线程访问元素。例如，这使得无法同时进行 Calculation 1 和 Calculation 2 因为它们都使用元素 A.
编辑：我可以从 2 个线程访问一个元素，但如果我只是拆分计算并依赖线程安全锁，它会使一切变得非常慢。

是否已经有针对此类问题的分布算法？
似乎很多人一定已经遇到了同样的问题，但我在伟大的互联网上找不到任何东西。 ;)

单线程示例代码：

for (int i = 0; i < elementCount; i++)
{
   for (int j = i + 1; j < elementCount; j++)
   {
      Calculate(element[i], element[j]);
   }
}

Answer 1

这很简单，可以证明没有办法分配你的计算从而永远不会发生冲突（也就是说，除非你手动排序计算并放置圆形边界，就像@Mbo 建议的那样），这意味着有在多个线程之间没有分配，这将使您永远不会锁定。

证明：鉴于您要求任何涉及数据对象 A 的计算都应该在给定线程 T 上发生（确保您永远不会锁定 A 的唯一方法）。
那么线程T必须处理至少一对包含输入列表的彼此对象（B，C，D）。
从基本要求来看，T 还要处理与对象 B 相关的所有事情。还有 C. 和 D. 所以一切。
因此，只有T可以工作。
QED。没有永远不会锁定的并行化。

绕过#1：map/reduce

也就是说...这是一个典型的分而治之的案例。你是对的，简单的添加可能需要临界区锁，而执行顺序无关紧要。那是因为你的关键操作（加法）有一个很好的属性，结合性：A+（B+C）=（A+B）+C，在交换之上。

换句话说，此操作是（并行友好的）reduce 操作的候选者。

所以这里的关键可能是：

发出所有有趣对的流
将每一对映射到一个或多个部分结果
按主对象 (A、B、C) 对每个部分结果进行分组
通过组合部分结果减少每组

示例（伪）代码

static class Data { int i = 0; }
static class Pair { Data d1; Data d2; }
static class PartialComputation { Data d; int sum; }

Data[] data = ...
Stream<Pair> allPairs = ... // Something like IntStream(0, data.length-1).flatMap(idx -> IntStream(idx+1 to data.length ).map(idx2 -> new Pair(data[idx], data[idx2])))
allPairs.flatMap(pair -> Stream.of(new ParticalComputation(pair.d1, pair.d1.i + pair.d2.i), new PartialComputation(pair.d2, pair.d2.i+pair.d1.i)) // Map everything, parallely, to partial results keyable by the original data object
allPairs.collect(Collectors.groupByParallel(
    partialComp -> partialComp.d, // Regroup by the original data object
    Collectors.reducing(0, (sum1, sum2) -> sum1.sum + sum2.sum)) // reduce by summing
))

方法 2：相信实现

事实是，java 中的无竞争锁变得更便宜了。最重要的是，纯锁定有时有更好的选择，例如 Java 中的原子类型（例如 AtomicLong，如果你正在求和），它使用 CAS 而不是锁定，它可以更快（google ，我通常会参考 Java Concurrency In Practice 一书来获取硬数字。）

事实是，如果您有 1000 到 10k 个不同的元素（转化为至少数百万对）和 8 个 CPU，那么争用（或 8 个线程中至少有 2 个正在处理的概率）相同的元素）非常低。而且我宁愿直接测量它而不是预先说 "I can not affor the locks"，尤其是如果操作可以使用原子类型来实现的话。

Answer 2

您可以应用 round-robin tournament algorithm 来组织所有可能的对（N*(N-1) 结果）。

所有集合元素（玩家）排成两行，列为对当前回合。第一个元素固定，其他元素循环移位

因此您可以运行最多 N/2 个线程来获取第一对组的结果，然后重新排序索引并继续

维基摘录：

The circle method is the standard algorithm to create a schedule for a round-robin tournament. All competitors are assigned to numbers, and then paired in the first round:
Round 1. (1 plays 14, 2 plays 13, ... )
 1  2  3  4  5  6  7
 14 13 12 11 10 9  8   

then fix one of the contributors in the first or last column of the table (number one in this example) and rotate the others clockwise one position
Round 2. (1 plays 13, 14 plays 12, ... )
 1  14 2  3  4  5  6
 13 12 11 10 9  8  7
Round 3. (1 plays 12, 13 plays 11, ... )
 1  13 14 2  3  4  5
 12 11 10 9  8  7  6   

until you end up almost back at the initial position
Round 13. (1 plays 2, 3 plays 14, ... )
 1  3  4  5  6  7  8
 2 14  13 12 11 10 9

多线程 - 一组中所有对之间的计算

Multithreading - Calculations between all pairs in a set

algorithm

multithreading

set

combinatorics

绕过#1：map/reduce

方法 2：相信实现