multithreading - 计算最小值的最小时间

Question

有人问我这样的问题，假设您有 8 个内核并且每次比较需要 1 分钟，那么计算 32 个整数的未排序数组的最小值所需的最短时间是多少。我的解决方案是 6 分钟，假设每个核心独立运行。将数组分成 8 个部分，每个部分有 4 个整数，8 个核同时计算每个部分的局部最小值，耗时 3 分钟，（每个部分进行 3 次比较）。然后 4 个核心计算这 8 个本地分钟的本地分钟，1 分钟。然后 2 个核心计算 4 个本地分钟，1 分钟，然后 1 个核心计算剩余 2 分钟，1 分钟中的全局最小值。因此，总量为 6 分钟。然而，这似乎不是面试官想要的答案。那么你们怎么看呢？谢谢

Answer 1

如果您假设该程序是 CPU 密集型的，这相当荒谬，但似乎是您进行分析的地方，那么您需要决定如何划分工作以通过多线程获得一些东西。

8 个 4 个整数，每个似乎是任意的。面试官通常喜欢看到一个思考过程。作为数学上的一般性，让我们计算问题子集的总排序。计算总排序有多难，回报是多少？

N 个项目的总排序，当两个项目相等时任意挑选，需要 N*(N-1)/2 比较并消除 (N-1) 个项目。让我们做一张桌子。

• N = 2：1 比较，1 淘汰。
• N = 3：3 次比较，2 次淘汰。
• N = 4：6 次比较，3 次淘汰。

显然，使用对 (N = 2) 是最有效的，但如果资源闲置，则其他操作很有用。

• 第 1-3 分钟：一次使用 N = 2、8 个操作淘汰 24 个候选人。
• 第 4 分钟：现在有 8 位候选人。保持 N = 2 将使 4 个内核空闲。设置 N = 3 每次操作多使用 2 个内核并产生 1 个更多消除。N = 3 的两个操作和 N = 2 的一个操作也是如此，消除了 2+2+1 = 5 个候选者。或者，使用N = 4的6个核心和N = 1的两个核心来消除3 + 1 + 1 = 5。结果是一样的。
• 第 5 分钟：只剩下 3 名候选人，所以最后一轮设置 N = 3。

如果让 CPU 保持忙碌，则混合使用两个更高级别的抽象需要 5 分钟。因为这不是解决问题的最有效方法，所以花费了更多的能量，但它更快。

Answer 2

我将假设比较两个“整数”是一个需要 1 分钟才能完成的黑匣子，但我们可以缓存这些比较，并且只进行一次任何特定的比较。

在您减少到 8 个候选人（3 分钟）之前，您无能为力。但是，如果您能提供帮助，您不想让核心闲置。假设候选人的编号是 1 到 8。那么在第 4 分钟你可以比较：
1v2 3v4 5v6 7v8 AND 1v5 2v6 3v7 4v8
如果幸运的话，这会淘汰 6 名候选人，我们可以使用第 5 分钟来选出获胜者.

如果我们不走运，这会留下 4 个候选者（例如，1、3、6 和 8），与原来的方法相比，这一步并没有给我们带来任何好处。在第 5 分钟，我们需要全力以赴（以击败最初的方法）。但是有 8 个核心，C(4,2)=6 可能的配对。所以我们可以进行所有可能的比较（并让 2 个内核空闲），并在 5 分钟内获得我们的获胜者。

Answer 3

这些都是非常大的整数，太大而无法放入 CPU 缓存中，因此多线程并不能真正帮助您——这个问题是 I/O 绑定的。（我想这取决于 I/O 瓶颈的具体情况，但我们不要挑剔。）

由于您需要进行 N-1 次比较，因此答案是 31。