Redis學習手冊6—資料結構之HyperLogLog

HyperLogLog簡介

HyperLogLog是一個專門計算集合的基數而建立的機率算法，對于一個給定的集合，HyperLogLog可以計算出這個集合的近似基數：近似基數并非集合的實際基數，它可能會比實際的基數小一點或大一點，但是估算的基數和實際基數之間的誤差會處于一個合理的範圍内，是以那些不需要知道實際基數或者因為條件限制而無法計算出實際基數的程式就可以把這個近似基數當做集合的實際基數使用。

HyperLogLog的優點

HyperLogLog的優點在于它計算近似基數所需的記憶體并不會因為集合的大小而改變，無論集合包含的元素有多少個，HyperLogLog進行計算所需的記憶體總是固定的，并且非常少的。

Redis的HyperLogLog隻需要使用12kb的記憶體空間，就可以對接近： 2 64 2^{64} 264個元素進行基數，而算法的标準誤差僅為0.81%，是以它計算出的近似基數是相當可信的。

HyperLogLog指令速查表

指令	用法及參數	說明
PFADD	PFADD hyperloglog element [element ...]	對一個或多個集合元素進行計數
PFCOUNT	PFCOUNT hyperloglog [hyperloglog ...]	擷取hyperloglog計算的近似基數
PFMERGE	PFMERGE destination hyperloglog [hyperloglog ...]	将給定的多個hyperloglog計算的并集存儲到指定的鍵中

指令詳解

PFADD指令

使用PFADD指令對一個或多個集合元素進行計數：

PFADD hyperloglog element [element ...]
           

根據給定的元素是否已經進行計數，PFADD指令可能傳回0，也可能傳回1：

• 如果給定的元素已經進行過計數，那麼PFADD指令将傳回0，表示HyperLogLog計算出的近似基數沒有發生變化。
• 與此相反，如果給定的元素中出現了至少一個之前沒有進行過計數的元素，導緻HyperLogLog計算出的近似基數發生了變化，那麼PFADD指令将傳回1 。

127.0.0.1:6379> PFADD letters "a" "b" "c"
(integer) 1
127.0.0.1:6379> PFADD letters "a"
(integer) 0
           

複雜度： O ( N ) O(N) O(N)，其中 N N N為使用者給定的元素數量。

版本要求：從Redis 2.8.9版本開始可用。

PFCOUNT指令

使用PFADD指令對元素進行計數之後，可以通過PFCOUNT指令來擷取HyperLogLog為集合計算出的近似基數：

PFCOUNT hyperloglog [hyperloglog ...]
           

127.0.0.1:6379> PFCOUNT letters
(integer) 3
           

傳回并集的近似基數

當使用者向PFCOUNT傳入多個HyperLogLog時，PFCOUNT指令将對所有給定的HyperLogLog執行并集計算，然後傳回并集計算出的近似基數：

127.0.0.1:6379> PFADD letters1 "a" "b" "c"
(integer) 1
127.0.0.1:6379> PFADD letters "c" "d" "e"
(integer) 1
127.0.0.1:6379> PFCOUNT letters1 letters2
(integer) 5
           

複雜度： O ( N ) O(N) O(N)，其中 N N N為給定的HyperLogLog數量。

版本要求：從Redis 2.8.9版本開始可用。

PFMERGE指令

PFMERGE指令可以對多個給定的HyperLogLog執行并集計算，然後把計算得出的并集HyperLogLog儲存到指定的鍵中：

PFMERGE destination hyperloglog [hyperloglog ...]
           

127.0.0.1:6379> PFADD numbers1 128 256 512
(integer) 1
127.0.0.1:6379> PFADD numbers2 128 256 512
(integer) 1
127.0.0.1:6379> PFADD numbers3 128 512 1024
(integer) 1
127.0.0.1:6379> PFMERGE union-numbers number1 number2 number3
(integer) 4
           

PFCOUNT與PFMERGE

PFCOUNT指令在計算多個HyperLogLog的近似基數時會執行以下操作：

• 在内部調用PFMERGE指令，計算所有給定的HyperLogLog的并集，并将這個并集存儲到一個臨時的HyperLogLog中。
• 對臨時的HyperLogLog執行PFCOUNT指令，得到它的近似基數（因為這是針對單個HyperLogLog的PFCOUNT，是以這個操作不會引起循環調用）。
• 删除臨時HyperLogLog
• 向使用者傳回之前得到的近似基數。

複雜度： O ( N ) O(N) O(N)，其中 N N N為使用者給定的HyperLogLog的數量。

版本要求：從Redis 2.8.9版本開始可用。

上一篇：Redis學習手冊5—資料結構之有序集合

下一篇：Redis學習手冊7—資料結構之位圖