找到k个机器中存储的k个数组中的最大k数

Question

这是一个面试问题.我有K台机器,每台机器连接到一台中央机器.每台K机器都有一个4字节数字的数组.您可以使用任何数据结构将这些数字加载到这些机器上的内存中,并且它们适合.K机器上的数字并不是唯一的.找到所有K台机器中数字组合中的K个最大数字.我能做到的最快的是什么？

Answer 1

(这是一个有趣的问题,因为它涉及并行性.因为我以前没有遇到过并行算法优化,所以很有趣:你可以通过一些可笑的高复杂度步骤,因为你可以在以后弥补它.无论如何,在答案...)

>" 我能做到的最快的是什么？ "

你能做的最好的是O(K).下面我将说明一个简单的O(K log(K))算法和更复杂的O(K)算法.

第一步:

每台计算机都需要足够的时间来读取每个元素 这意味着除非元素已经在内存中,否则时间上的两个边界之一是O(最大数组大小).例如,如果你的最大数组大小变化为O(K log(K))或O(K ^ 2)或其他东西,那么任何数量的算法技巧都不会让你走得更快.因此,实际的最佳运行时间是O(max(K, largestArraySize))技术上的.

假设阵列的最大长度为N,即<= K. 有了上述警告,我们被允许绑定,N<K因为每台计算机必须至少查看一次其每个元素(每台计算机进行O(N)预处理),每台计算机都可以选择最大的K元素(这被称为查找kth -order-statistics,请参阅这些线性时间算法).此外,我们可以免费使用(因为它也是O(N)).

界限和合理的期望:

让我们首先考虑一些最坏情况,并估算必要的最小工作量.

• 一个最小工作必要的估计值是O(K*N/K)= O(N),因为我们需要至少查看每个元素.但是,如果我们很聪明,我们可以在所有K台计算机上均匀分配工作(因此按K划分).
• 另一个最小工作必要的估计是O(N):如果一个数组大于所有其他计算机上的所有元素,我们返回该集合.
• 我们必须输出所有K元素; 这至少是O(K)打印出来的.如果我们只是知道元素的位置,我们可以避免这种情况,在这种情况下,O(K)界限不一定适用.

可以实现O(N)的界限吗？让我们来看看...

简单方法 - O(NlogN + K)= O(KlogK):

现在让我们想出一个简单的方法,它实现了O(NlogN + K).

考虑如此排列的数据,其中每列是计算机,每行是数组中的数字:

computer: A  B  C  D  E  F  G
      10 (o)      (o)          
       9  o (o)         (o)    
       8  o    (o)             
       7  x     x    (x)        
       6  x     x          (x)  
       5     x     ..........     
       4  x  x     ..          
       3  x  x  x  . .          
       2     x  x  .  .        
       1     x  x  .           
       0     x  x  .           

您还可以将其想象为来自计算几何的扫描线算法,或者是mergesort的"合并"步骤的有效变体.带括号的元素代表我们初始化潜在"候选解决方案"的元素(在某些中央服务器中).该算法将o通过转储(x)两个未选择的os 的答案来收敛于正确的响应.

算法:

• 所有计算机都以"活动"开始.
• 每台计算机对其元素进行排序.(并行O(N logN))
• 重复直到所有计算机都处于非活
  • 每个活动计算机找到次高的元素(自排序后的O(1))并将其提供给中央服务器.
  • 服务器巧妙地将新元素与旧K元素组合,并从组合集中移除相同数量的最低元素.为了有效地执行此步骤,我们有一个固定大小为K的全局优先级队列.我们插入新的可能更好的元素,坏元素不属于集合.每当元素落在集合之外时,我们告诉发送该元素的计算机永远不会发送另一个元素.(理由:这总是会提升候选集的最小元素.)

(旁注:添加回调挂钩以退出优先级队列是O(1)操作.)

我们可以用图形方式看到这将最多执行2K*(findNextHighest_time + queueInsert_time)操作,并且当我们这样做时,元素将自然地脱离优先级队列.findNextHighest_time是O(1),因为我们对数组进行了排序,因此为了最小化2K*queueInsert_time,我们选择一个具有O(1)插入时间的优先级队列(例如基于Fibonacci堆的优先级队列).这给了我们一个O(log(queue_size))提取时间(我们不能有O(1)插入和提取); 但是,我们永远不需要使用提取操作!完成后,我们只将优先级队列转储为无序集合,这需要O(queue_size)= O(K)时间.

因此,我们有O(N log(N)+ K)总运行时间(并行排序,然后是O(K)*O(1)优先级队列插入).在N = K的最坏情况下,这是O(K log(K)).

更好的方法 - O(N + K)= O(K):

然而,我想出了一个更好的方法,达到了O(K).它基于中位数中值选择算法,但是并行化.它是这样的:

如果我们确定在所有计算机中某处至少有K(不是严格地说)更大的数字,我们就可以消除一组数字.

算法:

• 每台计算机找到sqrt(N)其集合中的最高元素,并将该集合拆分为元素<和>.这需要并行的O(N)时间.
• 计算机协作,这些统计信息组合成一组新的,并找到K/sqrt(N)的个最高元素是集(让我们把它叫做"superstatistic"),并注意哪些计算机统计的<和> superstatistic.这需要O(K)时间.
• 现在考虑所有元素都低于计算机的统计数据,在统计数据低于超集的计算机上.这些元素可以消除.这是因为在统计数据大于超原型的计算机上,大于计算机统计数据的元素是一组较大的K元素.(见这里的视觉).
• 现在,具有uneliminated元素的计算机将其数据均匀地重新分配给丢失数据的计算机.
• Recurse:你还有K台计算机,但是N的值已经减少了.一旦N小于预定常数,使用我在"简单方法 - O(NlogN + K)"中提到的先前算法; 除了这种情况,它现在是O(K).=)

事实证明,减少总量是O(N)(令人惊讶的不是K阶),除了可能是O(K)的最后一步.因此,该算法的总和为O(N + K)= O(K).

O(K)运行时间的分析与仿真.统计数据允许我们将世界划分为四个无序集合,在此表示为一个分为四个子框的矩形:

         ------N-----

         N^.5            
         ________________                     
|       |     s          |  <- computer
|       | #=K s  REDIST. |  <- computer
|       |     s          |  <- computer
| K/N^.5|-----S----------|  <- computer
|       |     s          |  <- computer
K       |     s          |  <- computer
|       |     s  ELIMIN. |  <- computer
|       |     s          |  <- computer
|       |     s          |  <- computer
|       |_____s__________|  <- computer

LEGEND:
s=statistic, S=superstatistic
#=K -- set of K largest elements    

(我在这里绘制了无序行和s列之间的关系,但它会使事情变得混乱;现在快速查看附录.)

对于此分析,我们将考虑N减少.

在给定的步骤中,我们能够消除标记的元素ELIMIN; 这已从上面的矩形表示中删除了区域,将问题大小从K*N减小到,这非常简单地简化为

现在,具有uneliminated元素的计算机将其数据(REDIST上面的矩形)重新分配给具有已消除元素(ELIMIN)的计算机.这是并行完成的,其中带宽瓶颈对应于短大小的长度REDIST(因为它们的数量超过ELIMIN等待其数据的计算机).因此,数据将花费与REDIST矩形的长度一样长的时间(另一种思考方式:K/?N * (N-?N)区域,除以K/?N每次数据,导致O(N-?N)时间).

因此,在尺寸的每个步骤中N,我们能够以K(2?N-1)执行N + 3K + (N-?N)工作为代价来减小问题的大小.我们现在递归.将告诉我们的表现的复发关系是:

T(N) = 2N+3K-?N + T(2?N-1)

子问题大小的抽取比正常的几何级数快得多(√N而不是N/2,你通常从普通的分而治之中获得).不幸的是,主定理和强大的Akra-Bazzi定理都不起作用,但我们至少可以通过模拟来说服自己它是线性的:

>>> def T(n,k=None):
...      return 1 if n<10 else sqrt(n)*(2*sqrt(n)-1)+3*k+T(2*sqrt(n)-1, k=k)
>>> f = (lambda x: x)
>>> (lambda n: T((10**5)*n,k=(10**5)*n)/f((10**5)*n) - T(n,k=n)/f(n))(10**30)
-3.552713678800501e-15

该函数T(N)在大规模上是线性函数的倍数x,因此是线性的(输入加倍使输出加倍).因此,这种方法几乎可以肯定地实现了O(N)我们猜想的界限.虽然看到附录有趣的可能性.

...

附录

• 一个陷阱是意外排序.如果我们做任何意外地对我们的元素进行分类的事情,我们至少会受到对数(N)的惩罚.因此,最好将数组视为集合,以避免认为它们被排序的陷阱.
• 另外我们可能最初认为,随着3K每一步的工作量不断增加,我们将不得不做3K log(log(N))工作.但-1在问题规模的抽取中扮演着强大的角色.运行时间实际上略高于线性,但绝对比N log(log(log(log(N)))小得多.例如,它可能类似于O(N*InverseAckermann(N)),但在测试时我达到了递归限制.
• O(K)可能只是因为我们必须将它们打印出来; 如果我们只满足于知道数据的位置,我们甚至可以拉出O(N)(例如,如果数组长度为O(log(K)),我们可能能够实现O(log(K) )))......但那是另一个故事.
• 无序集之间的关系如下.会把事情弄得一团糟.

.

          _
         / \
(.....) > s > (.....)
          s
(.....) > s > (.....)
          s
(.....) > s > (.....)
         \_/

          v

          S

          v

         / \
(.....) > s > (.....)
          s
(.....) > s > (.....)
          s
(.....) > s > (.....)
         \_/

Answer 2

• 在每台机器上找到k个最大的数字.为O(n*日志(k))的
• 结合结果(在集中式服务器上,如果k不是很大,否则您可以将它们合并到服务器集群中的树层次结构中).

更新:为清楚起见,合并步骤不是一种排序.您只需从结果中选择前k个数字.有效地有很多方法可以做到这一点.例如,您可以使用堆,推动每个列表的头部.然后你可以从堆中移除头部并从元素所属的列表中推出头部.这样做k次可以得到结果.所有这些都是O(k*log(k)).