gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 01:34:16 25 4
gpt4 key购买 nike

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 - Apache Spark RDD sortByKey 算法和时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32123887/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com