apache-spark - Apache Spark RDD sortByKey 算法和时间复杂度

Question

Apache Spark RDD sortByKey 的 Big-O 时间复杂度是多少？

我正在尝试根据特定顺序将行号分配给 RDD。

假设我有一个 {K,V} 对 RDD，我希望使用

myRDD.sortByKey(true).zipWithIndex

这个操作的时间复杂度是多少，以大 O 形式表示？

幕后发生了什么？冒泡排序？我希望不是!我的数据集非常大并且跨分区运行，所以我很好奇 sortByKey 函数是否是最佳的，或者在分区内执行某种中间数据结构，然后跨分区执行其他操作以优化消息传递，或者什么。

Answer 1

快速浏览一下代码就会发现在幕后使用了 RangePartitioner。文档说:

partitions sortable records by range into roughly * equal ranges. The ranges are determined by sampling the content of the RDD passed in

所以本质上你的数据被采样 (O[n])，然后只有唯一的样本键 (m) 被排序 (O[m log(m)]) 并确定键的范围，然后整个数据被打乱(O[n]，但代价高昂)，然后对给定分区上接收到的键范围内的数据进行内部排序 (O[p log[p))。
zipWithIndex可能使用本地大小来分配数字，使用分区号，因此很可能为此效果存储了分区元数据:

Zips this RDD with its element indices. The ordering is first based on the partition index * and then the ordering of items within each partition. So the first item in the first * partition gets index 0, and the last item in the last partition receives the largest index.