多CPU情况下找到最大数的最短时间是多少？

Question

例如，假设有32个数字（未排序，范围未知）和8个CPU，每个CPU每分钟计算一次比较。

如果只有一个CPU，则需要进行31次比较。 但是使用8个CPU，我们可以每分钟比较16个数字。

计算最大数字所需的最短时间（以分钟为单位）是多少？ （我算出来大约需要6分钟，但我认为可能可以在5分钟内完成，不确定算法如何工作。）

- sunapi386

---

我们可以假定存在一个中央程序，在获得先前比较结果之后，即时决定将哪些比较委派给8个CPU吗？还是在聚合和输出答案之前，这8个CPU都必须完全完成其指令集？ - torquestomp

这是一颗速度很慢的CPU :) - 500 - Internal Server Error

@torquestomp CPU必须完成它们的比较。假设这是一个朴素（简单）的系统。 - sunapi386

Answer 1

1) 32 numbers -> compare 8 pairs using 8 CPUs -> 24 numbers
2) 24 numbers -> compare 8 pairs using 8 CPUs -> 16 numbers
3) 16 numbers -> compare 8 pairs using 8 CPUs -> 8 numbers
4) 8 numbers  -> compare 4 pairs using 4 CPUs -> 4 numbers
5) 4 numbers  -> compare all numbers with each other using 6 CPUs (tetrahedron)

- Egor Skriptunoff

---

由于在第4步中有4个浪费的CPU，您可能可以随机选择不同对的其他值进行比较，并且如果这些值在各自的对中被证明是最大值，则可能已经在第5步之前知道结果。 - Bernhard Barker

Answer 2

(编辑) 前4步很容易

1. 比较8对（16个数字）-> 8个胜者1
2. 比较8对（16个数字）-> 8个胜者2
3. 比较8对（8个胜者1与8个胜者2）-> 8个胜者，

4. 比较4对 -> 4个胜者

   假设4个数字为a、b、c、d

5. 比较6对（a、b）、（a、c）、（a、d）、（b、c）、（b、d）、（c、d）-> 最大的数字将获得3次胜利

- sowrov

---

第四步：a=c=e=g=1; b=d=f=h=2。有四个获胜者。 - John Dvorak

我假设所有数字都是唯一的，但这个4位获胜者情况是一个特殊情况，在第5步中我们只会有2个获胜者。 - sowrov

即使有唯一的条目，你也可以得到 10,20,11,21,12,22,13,23 => 四个获胜者 (20,21,22,23)。 - John Dvorak

看起来没问题。这有点让我想起了Egor的回答 ；-) - John Dvorak

当我第一次阅读他的回答时，实际上我并没有理解它，所以开始自己思考:p - sowrov

Answer 3

可以将其类比为NCAA比赛表，让每个核心处理一个游戏/分钟。再加上四个面体逻辑，您就可以节省1分钟。

- MobA11y