Apache Spark RDD sortByKey 算法和时间复杂度
Apache Spark RDD sortByKey algorithm and time complexity
Apache Spark RDD sortByKey 的 Big-O 时间复杂度是多少？
我正在尝试根据特定顺序将行号分配给 RDD。
假设我有一个 {K,V} 对 RDD，我希望使用
按键执行订单
myRDD.sortByKey(true).zipWithIndex
这个操作的时间复杂度是多少，大 O 形式？
幕后发生了什么？冒泡排序？我希望不是！我的数据集非常大并且跨分区运行，所以我很好奇 sortByKey 函数是否是最佳的，或者在分区内执行某种中间数据结构然后跨分区执行其他操作以优化消息传递，或者什么。
快速浏览一下代码就会发现在幕后使用了 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.
Apache Spark RDD sortByKey 的 Big-O 时间复杂度是多少？
我正在尝试根据特定顺序将行号分配给 RDD。
假设我有一个 {K,V} 对 RDD，我希望使用
按键执行订单myRDD.sortByKey(true).zipWithIndex
这个操作的时间复杂度是多少，大 O 形式？
幕后发生了什么？冒泡排序？我希望不是！我的数据集非常大并且跨分区运行，所以我很好奇 sortByKey 函数是否是最佳的，或者在分区内执行某种中间数据结构然后跨分区执行其他操作以优化消息传递，或者什么。
快速浏览一下代码就会发现在幕后使用了 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.