Apache Spark RDD sortByKey的Big-O时间复杂度是多少？
我正在尝试根据特定订单将行号分配给RDD .
假设我有一个{K，V}对RDD，我希望按键执行订单
myRDD.sortByKey(true).zipWithIndex
这个操作的时间复杂度是多少？
而且幕后发生了什么？泡泡排序？我希望不是！我的数据集非常大并且跨分区运行，所以我很好奇sortByKey函数是否是最优的，或者在分区中是否有某种中间数据结构，然后是跨分区的其他东西来优化消息传递，或者是什么 .
快速查看代码显示正在使用RangePartitioner . 文档说：
按范围将可排序记录划分为大致*相等的范围 . 范围通过对传入的RDD的内容进行采样来确定
所以本质上你的数据被采样（O [n]），然后只对排序的唯一样本密钥（m）进行排序（O [m log（m）]）并确定密钥范围，然后整个数据被洗牌（O [n]，但代价高昂），然后在给定分区（O [p log [p））上接收的密钥范围内部排序数据 .
zipWithIndex 可能使用本地大小来分配数字，使用分区号，因此很可能为此效果存储分区元数据：
zipWithIndex
使用其元素索引来压缩此RDD . 排序首先基于分区索引*，然后是每个分区内的项目顺序 . 因此第一个*分区中的第一项获得索引0，最后一个分区中的最后一项获得最大索引 .
1 回答
快速查看代码显示正在使用RangePartitioner . 文档说：
所以本质上你的数据被采样（O [n]），然后只对排序的唯一样本密钥（m）进行排序（O [m log（m）]）并确定密钥范围，然后整个数据被洗牌（O [n]，但代价高昂），然后在给定分区（O [p log [p））上接收的密钥范围内部排序数据 .
zipWithIndex可能使用本地大小来分配数字，使用分区号，因此很可能为此效果存储分区元数据：