实现 Spark 不同

Question

我是Spark和Scala的新手。我正在阅读火花的独特()功能。但是我找不到任何合适的细节。我有几个无法解决的疑问，并把它们写了下来。

>

在 Spark 中实现的 （） 有多独特？

我不太擅长Spark源代码，无法识别整个流程。当我检查执行计划时，我只能看到一个SchffleRDD

什么是不同的时间复杂度？

我还从谷歌搜索中发现，它也以某种方式使用哈希和排序。

所以，我想它是否使用了与借助Hashset从数组中获取唯一元素相同的原理。如果是一个系统，我会猜到时间复杂度是O(nlogn)。

但是它分布在许多分区中，并且是混洗的，那么时间复杂度是多少？

有没有办法避免在特定情况下洗牌？

如果我确保根据我的用例正确分区我的数据，我可以避免洗牌吗？

例如，假设在数据帧中爆炸具有唯一行的 ArrayType 列会创建新行，而其他列是重复的。我将选择其他列.通过这种方式，我确保每个分区的重复项是唯一的。因为我知道每个分区的重复项都是唯一的，所以我可以避免随机播放，只是敏锐地在该分区中删除重复项

我还发现了这个确实火花的独特（）函数只洗牌来自每个分区的不同元组。

谢谢你的帮助。如果我说错了，请纠正我。

Answer 1

Spark中distinct()是如何实现的？

通过应用具有“无”值的虚拟聚合。大约

rdd.map((_, None)).reduceByKey((a, b) => a)

什么是不同的时间复杂度？

鉴于整个过程的复杂性，很难估计。它至少为O(N log N)，因为shuffle需要排序，但是考虑到构建额外的核外数据结构(包括关联数组)所需的多个其他操作，序列化/反序列化数据可能会更高，并且在实践中由IO操作主导，而不是纯粹的算法复杂性。

有没有办法避免在特定情况下洗牌？

是的，如果保证将潜在的重复项放在同一个分区上。

您可以使用< code>mapPartitions对数据进行重复数据删除，尤其是在数据经过排序或者以其他方式保证在隔离的邻域中有重复数据的情况下。如果没有这一点，您可能会受到内存需求的限制，除非您接受概率过滤器(如Bloom filter)的近似结果。

一般来说，虽然这是不可能的，但像这样的操作将是非本地的。