在 pyspark 的近似计数不同 https://spark.apache.org/docs/3.1.2/api/python/reference/api/pyspark.sql.functions.approx_count_distinct.html函数有一个精度参数rsd
。它是如何工作的?如果增加或减少,会有什么权衡?我想对于这个应该明白如何approx_count_distinct
已实施。你能帮我理解吗rsd
在逻辑背景下approx_count_distinct
?
rsd
是“相对标准差”的缩写,默认值为0.05。使用此值,您可以控制在不同计数上您愿意接受的错误是什么。正如 @Derek O 在上面的评论中所描述的,approx_count_distinct
函数在准确性之间进行权衡(您可以使用rsd
参数)和计算速度。
为了更多地了解底层算法,我们可以快速浏览一下该算法的实现approx_count_distinct https://github.com/apache/spark/blob/fbbcf9434ac070dd4ced4fb9efe32899c6db12a9/sql/core/src/main/scala/org/apache/spark/sql/functions.scala#L286-L296功能。我们看到它使用了 HyperLogLogPlusPlus 算法(对超级日志日志 https://en.wikipedia.org/wiki/HyperLogLog算法)。
/**
* Aggregate function: returns the approximate number of distinct items in a group.
*
* @param rsd maximum relative standard deviation allowed (default = 0.05)
*
* @group agg_funcs
* @since 2.1.0
*/
def approx_count_distinct(e: Column, rsd: Double): Column = withAggregateFunction {
HyperLogLogPlusPlus(e.expr, rsd, 0, 0)
}
阿帕奇火花的执行 https://github.com/apache/spark/blob/fbbcf9434ac070dd4ced4fb9efe32899c6db12a9/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/HyperLogLogPlusPlus.scala#L28-L42这个的HyperLogLogPlusPlus
算法基于以下论文(Spark v3.3.1,撰写本文时):
-
HyperLogLog:近最优基数估计算法的分析 http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf(此链接已损坏,但为了完整性我将其添加)
- HyperLogLog 实践:最先进的基数估计算法的算法工程 http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/40671.pdf
- HyperLogLog 实践附录:最先进基数估计算法的算法工程 https://docs.google.com/document/d/1gyjfMHy43U9OWBXxfaeG-3MjGzejW1dlpyMwEYAAWEI/view?fullscreen#
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)