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

Question

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

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

假设我有一个 {K,V} 对 RDD，并且我希望使用 key 执行订单

myRDD.sortByKey(true).zipWithIndex

此操作的时间复杂度是多少（以大 O 形式表示）？

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

Answer 1

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

按范围将可排序记录划分为大致相等的范围。范围是通过对传入的 RDD 的内容进行采样来确定的

因此，本质上，您的数据被采样（O[n]），然后仅对唯一样本键（m）进行排序（O[m log(m)]）并确定键的范围，然后对整个数据进行洗牌（O[n]，但成本较高），然后根据给定分区上接收到的键范围对数据进行内部排序 (O[p log[p)]。

zipWithIndex可能使用本地大小来分配数字，使用分区编号，因此很可能为此效果存储分区元数据：

压缩此 RDD 及其元素索引。排序首先基于分区索引 *，然后基于每个分区内的项目的排序。因此，第一个 * 分区中的第一项获得索引 0，最后一个分区中的最后一项获得最大索引。