Apache是如何实现其topK() API的？

Question

在Apache中有一个 API，它可以从RDD返回顶部的k元素。我想知道这个操作是如何实现的。它是否先对RDD进行排序，然后返回顶部的k值？还是使用其他更有效的实现？

Answer 1

不，它不能对整个RDD进行排序，那样的操作太昂贵了。

它将使用优先级队列分别为每个分区选择顶部N个元素。然后，将这些队列合并到还原操作中。这意味着整个RDD中只有一小部分在整个网络中被洗牌。

有关更多详细信息，请参阅RDD.scala。

示例

3个输入分区

RDD.top(2)

[3, 5, 7, 10], [8, 6, 4, 12], [9, 1, 2, 11]
      ||            ||              || 
   [10, 7]        [12, 8]         [11, 9]
================== reduce ==================
                 [12, 11]