了解超置logog以估計(jì)基數(shù)

基數(shù)是數(shù)據(jù)集中不同項(xiàng)目的數(shù)量。無論是計(jì)算網(wǎng)站上的唯一用戶數(shù)量還是估計(jì)不同搜索查詢的數(shù)量，估計(jì)基數(shù)在處理大量數(shù)據(jù)集時都變得具有挑戰(zhàn)性。這就是超置式算法進(jìn)入圖片的地方。在本文中，我們將探討HyperLoglog及其應(yīng)用程序背后的關(guān)鍵概念。

Hyperloglog

HyperLogLog是一種概率算法，旨在估計(jì)具有高精度和低內(nèi)存使用情況的數(shù)據(jù)集的基數(shù)。

計(jì)算不同項(xiàng)目的傳統(tǒng)方法需要存儲到目前為止所看到的所有項(xiàng)目，例如將所有用戶信息存儲在用戶數(shù)據(jù)集中，這可以快速消耗大量內(nèi)存。另一方面，HyperLogLog使用固定數(shù)量的內(nèi)存，幾千字節(jié)，并且仍然提供了對基數(shù)的準(zhǔn)確估計(jì)，使其非常適合大規(guī)模數(shù)據(jù)分析。

用例

在以下情況下，HyperLogLog特別有用：

有限的內(nèi)存

如果使用大量數(shù)據(jù)集(例如數(shù)百萬用戶或網(wǎng)絡(luò)流量數(shù)據(jù)的日志)，則由于內(nèi)存限制，存儲每個唯一項(xiàng)目可能是不可行的。

近似計(jì)數(shù)

在許多情況下，不需要確切的計(jì)數(shù)，并且良好的估計(jì)是足夠的。 HyperlogLog給出了一個估計(jì)值，該估計(jì)值與真實(shí)值足夠接近，而沒有精確計(jì)算的開銷。

流數(shù)據(jù)

當(dāng)使用連續(xù)的數(shù)據(jù)流(例如實(shí)時網(wǎng)站流量或社交媒體供稿)時，超置換件可以更新其估算值，而無需重新訪問過去的數(shù)據(jù)。

一些值得注意的應(yīng)用程序用例包括以下內(nèi)容：

· Web分析：估計(jì)訪問網(wǎng)站的唯一用戶數(shù)量。

· 社交媒體分析：計(jì)算社交媒體流中獨(dú)特的主題標(biāo)簽，提及或其他不同項(xiàng)目。

· 數(shù)據(jù)庫系統(tǒng)：有效地計(jì)數(shù)大型數(shù)據(jù)庫中的不同鍵或值。

· 大數(shù)據(jù)系統(tǒng)：諸如Apache Hadoop和Apache Spark之類的框架使用HyperLoglog來計(jì)算大數(shù)據(jù)管道中的不同項(xiàng)目。

· 網(wǎng)絡(luò)監(jiān)控：估計(jì)網(wǎng)絡(luò)流量分析中不同IP地址或數(shù)據(jù)包的數(shù)量。

現(xiàn)有實(shí)現(xiàn)

HyperLoglog已以各種語言和數(shù)據(jù)處理框架實(shí)現(xiàn)。一些實(shí)現(xiàn)超閘紙的流行工具如下：

· REDIS提供了HyperLogLog的本機(jī)實(shí)現(xiàn)PFADD，以通過PFCOUNT和PFMERGE命令進(jìn)行近似的基數(shù)估算。 REDIS允許用戶在消耗最小內(nèi)存的同時有效地跟蹤數(shù)據(jù)集中的獨(dú)特項(xiàng)目。

· Google BigQuery提供了一個名為的內(nèi)置函數(shù)APPROX_COUNT_DISTINCT，該功能使用超置logog來估計(jì)大數(shù)據(jù)集中不同項(xiàng)目的數(shù)量。 BigQuery通過使用HyperLoglog來提供高效的心臟估算，而無需全部數(shù)據(jù)來優(yōu)化查詢處理。

· Apache DataSketches是用于近似計(jì)算的算法集合，包括HyperLogLog。它是在Java中實(shí)現(xiàn)的，通常用于用于大規(guī)模數(shù)據(jù)處理的分布式計(jì)算環(huán)境中。

· Python軟件包HyperlogLog 是 超置池的實(shí)現(xiàn)，可讓您計(jì)算具有較小內(nèi)存足跡的數(shù)據(jù)集的近似基數(shù)。

· 該函數(shù)approx_count_distinct可在Pyspark的DataFrame API中獲得，并用于計(jì)算數(shù)據(jù)框列中不同值的近似計(jì)數(shù)。它基于HyperLogLog算法，提供了一種高度記憶有效的估計(jì)不同計(jì)數(shù)的方法。

示例用法

from pyspark.sql import SparkSession

from pyspark.sql import functions

spark=SparkSession.builder.appName('Test').getOrCreate()

df = spark.createDataFrame([("user1", 1), ("user2", 2), ("user3", 3)])

distinct_count_estimate = df.agg(functions.approx_count_distinct("_1").alias("distinct_count")).collect()

print(distinct_count_estimate)

邏輯

HyperLoglog背后的基本思想是使用哈希功能將數(shù)據(jù)集中的每個項(xiàng)目映射到一系列值的位置。通過分析這些項(xiàng)目的位置，該算法可以估計(jì)存在多少不同的項(xiàng)目而不明確存儲它們。這是其工作原理的分步分類：

1. 集合中的每個項(xiàng)目都使用哈希函數(shù)進(jìn)行哈希。哈希函數(shù)的輸出是二進(jìn)制字符串。

2. HyperLogLog專注于哈希值的二進(jìn)制表示中的領(lǐng)先零。領(lǐng)先的零，值越稀有。具體來說，跟蹤了哈希中第一個位的位置，這使您可以了解不同項(xiàng)目數(shù)量的大小。

3. HyperLogLog將可能的哈希值的范圍分為多個存儲桶或寄存器。每個寄存器都跟蹤對該寄存器的任何項(xiàng)目觀察到的最多的領(lǐng)先零。

4. 處理所有項(xiàng)目后，HyperLogLog結(jié)合了所有寄存器的信息以計(jì)算基數(shù)的估計(jì)。登記率越多，觀察到的領(lǐng)先零的數(shù)量越高，估計(jì)值就越準(zhǔn)確。

HyperLogLog提供了一個誤差范圍的估計(jì)值。錯誤率取決于算法中使用的寄存器數(shù)量。使用的寄存器越多，誤差余量越小，但內(nèi)存使用量越高?？梢愿鶕?jù)應(yīng)用程序的需求進(jìn)行微調(diào)進(jìn)行微調(diào)。

優(yōu)勢

以下是使用超置槽的一些關(guān)鍵優(yōu)勢。

空間復(fù)雜性

與需要存儲每個唯一項(xiàng)目的傳統(tǒng)方法不同，HyperLoglog使用固定數(shù)量的內(nèi)存，與不同項(xiàng)目的數(shù)量對數(shù)縮放。這使其非常適合大規(guī)模數(shù)據(jù)集。

時間復(fù)雜性

在處理速度方面，HyperLogLog高效。它需要為處理的每個項(xiàng)目持續(xù)時間，使其適用于實(shí)時或流媒體應(yīng)用程序。

可伸縮性

HyperLogLog與大型數(shù)據(jù)集相當(dāng)良好，并且經(jīng)常用于分布式系統(tǒng)或數(shù)據(jù)處理框架中，其中需要大量數(shù)據(jù)。

簡單

該算法相對簡單實(shí)現(xiàn)，并且不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或操作。

其他方法

還有其他幾種用于基數(shù)估計(jì)的方法，例如計(jì)數(shù)米草圖和Bloom過濾器。盡管這些方法中的每一種都具有其優(yōu)勢，但HyperLoglog在準(zhǔn)確性和空間復(fù)雜性之間的平衡方面脫穎而出。

布盧姆過濾器

Bloom過濾器非常適合檢查是否存在物品，但它們沒有提供基數(shù)估計(jì)。另一方面，HyperLogLog可以估計(jì)基數(shù)，而無需存儲所有物品。

計(jì)數(shù)素描

這是用于頻率估計(jì)的概率數(shù)據(jù)結(jié)構(gòu)，但是在基數(shù)估計(jì)中，它需要比超置槽更多的存儲器。

結(jié)論

HyperLogLog是一種非常有效且準(zhǔn)確的算法，用于估計(jì)大數(shù)據(jù)集中的基數(shù)。利用概率技術(shù)和哈希功能將允許使用最少的內(nèi)存使用量處理大數(shù)據(jù)，這使其成為數(shù)據(jù)分析，分布式系統(tǒng)和流數(shù)據(jù)應(yīng)用程序的必不可少的工具。