高端装饰公司网站设计,网站开发基本步骤,中国第一作文网,网站规划与建设大作业HyperLogLog#xff08;简称 HLL#xff09;是一种用于近似计数#xff08;特别是基数估计#xff0c;Cardinality Estimation#xff09;的算法#xff0c;它能够在大数据场景中高效地估计集合中不同元素的数量#xff0c;尤其适用于数据流的情况。HyperLogLog 相较于传… HyperLogLog简称 HLL是一种用于近似计数特别是基数估计Cardinality Estimation的算法它能够在大数据场景中高效地估计集合中不同元素的数量尤其适用于数据流的情况。HyperLogLog 相较于传统的计数方法具备非常低的空间复杂度同时又能提供准确的估计结果。它是 LogLog 算法的改进版。
一、背景与需求
在很多数据处理场景中我们需要估算数据流或大规模集合中不同元素的数量。例如
网站访问者的去重统计。网络中独立IP的计数。社交网络中的独立用户数量。 对于这些问题直接计算集合的基数即集合中独立元素的数量是非常消耗内存和计算资源的尤其在数据量巨大的情况下。因此我们需要一种空间复杂度低且计算高效的算法来近似这个基数。
二、基本概念 HyperLogLog 的设计目标是使用较小的内存空间通常是常数空间来对大数据集中的不同元素的基数进行估计。
估计的精度HyperLogLog 的估计值是一个近似值但通常精度非常高。空间复杂度HyperLogLog 使用 O(log(log(n))) 的空间来存储结果其中 n 是数据集中的元素数量。这个空间复杂度比传统的哈希集合需要 O(n) 空间要小得多。
三、工作原理
HyperLogLog 基于以下几个关键的思想 哈希函数HyperLogLog 使用哈希函数将数据项映射到一个范围内。哈希函数的设计要求其具有均匀性即对于不同的输入它能生成均匀分布的输出。 桶BucketsHyperLogLog 使用多个桶来存储中间结果。每个桶保存一个整数值表示该桶所记录的哈希值的前导零的数量。 最大前导零计数对于每个元素通过哈希函数计算其哈希值然后记录该哈希值二进制表示中的前导零的数量。假设哈希值的长度为 L 位那么每个桶存储的是哈希值中的前导零数。 桶的更新规则每次插入一个新元素时计算该元素的哈希值并找到该哈希值二进制表示中的前导零的个数。然后更新对应桶的值即该桶记录的值为该桶当前值和前导零数的最大值。 基数估计最终的基数估计值是通过对所有桶中记录的前导零数的值进行合成计算得到的。
1.1 哈希映射与前导零 首先假设我们对一个元素应用一个哈希函数 H得到的哈希值是一个 m 位的二进制字符串。我们关心的是该哈希值中从左至右的前导零的数量。例如如果哈希值为 0001011001则前导零的数量为 3。
1.2 桶Registers HyperLogLog 使用多个桶每个桶记录一个整数值表示该桶对应哈希值的最大前导零数。假设我们有 b 个桶那么我们将输入的哈希值映射到其中的一个桶。 通过哈希函数我们将输入数据映射到一个桶。然后对于每个数据点计算其哈希值中前导零的数量并更新该桶的值。具体而言如果哈希值的前导零数大于该桶当前记录的前导零数则更新该桶的值。
1.3 基数估算 HyperLogLog 使用一种名为 Harmonic Mean 的方法来估算基数。为了避免估算偏差最终的基数估算结果是通过所有桶的统计信息计算的。
计算所有桶中值的平均数。使用此平均数来推算出总的基数。
具体计算公式如下 其中
E 是基数估算值。m 是桶的数量桶的数量等于 HyperLogLog 中注册器的数量。Z 是桶中记录的前导零数的平均值。 是一个常数具体值与桶的数量 m 有关。
四、空间复杂度与精度 HyperLogLog 的空间复杂度主要由桶的数量 m 决定。每个桶通常存储一个整数值这个整数值代表前导零的最大值因此每个桶所需的存储空间是常数级别的。通常为了保持足够的精度我们会选择 m 为 的形式其中 n 为桶数的对数。
精度HyperLogLog 的误差率标准差与桶的数量 m 相关。桶数越多精度越高但需要更多的内存空间。一般来说HyperLogLog 的误差范围是 ±2%。
五、源代码实现Python 示例
下面是一个简化的 HyperLogLog 的 Python 实现
import hashlib
import mathclass HyperLogLog:def __init__(self, b):self.b b # number of registers (buckets)self.m 1 b # number of registers (m 2^b)self.data [0] * self.m # initialize registers to 0def _hash(self, value):# Use hashlib to compute a hash of the input valuereturn int(hashlib.md5(str(value).encode(utf8)).hexdigest(), 16)def _rho(self, x):# Count the number of leading zeros in the binary representation of xreturn (x ^ (1 x.bit_length() - 1)).bit_length() 1def add(self, value):# Hash the value and compute the register indexhash_value self._hash(value)register_index hash_value (self.m - 1) # Use the lower b bits for the index# Update the corresponding register with the max rho valueself.data[register_index] max(self.data[register_index], self._rho(hash_value))def estimate(self):# Use the registers to estimate the cardinalityZ 1.0 / sum([2.0 ** -reg for reg in self.data])E (self.m ** 2) * Z# Apply bias correction for small cardinalitiesif E 2.5 * self.m:V self.data.count(0)if V 0:E self.m * math.log(self.m / V)# Large cardinalities correctionif E (1 / 30.0) * (1 32):E -(1 32) * math.log(1 - E / (1 32))return E# Example usage:
hll HyperLogLog(15) # Initialize with 2^15 registers
for i in range(10000):hll.add(i)
print(Estimated cardinality:, hll.estimate())代码解释
初始化HyperLogLog 类接受一个参数 b指定桶的数量为 。每个桶存储一个整数值表示前导零的数量。哈希函数_hash 方法使用 MD5 哈希来处理输入值并返回一个整数。更新桶add 方法接受一个元素计算其哈希值并更新相应桶的值。估算基数estimate 方法使用所有桶的值来估算数据集的基数并考虑了小基数和大基数的修正。
六、总结 HyperLogLog 是一个基于哈希的概率算法具有非常高的内存效率尤其适用于需要快速估算基数的大数据场景。它通过哈希映射和前导零统计来估计基数在保证低空间复杂度的同时仍然提供较为准确的结果。尽管它是一个近似算法但在很多实际应用中估算误差足够小能够满足需求。
