计算最小值的MInimal时间

Question

我被问到这样的问题,计算32个整数的未排序数组的最小值所需的最短时间是多少,因为你有8个核心,每个比较需要1分钟.假设每个核心独立运行,我的解决方案是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的2个核心来消除3 + 1 + 1 = 5.结果是相同的.
• 分钟5:仅剩下3名候选人,因此在最后一轮设置N = 3.

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