Skip to Main Content
高效能PYTHON程式設計
book

高效能PYTHON程式設計

by Micha Gorelick, Ian Ozsvald
August 2015
Intermediate to advanced content levelIntermediate to advanced
384 pages
7h 42m
Chinese
GoTop Information, Inc.
Content preview from 高效能PYTHON程式設計
330
|
第十一章
LogLog 計數器
LogLog 類型的計數器(
http://bit.ly/LL-type_counters
)奠基於雜湊函式的個別位元也能夠
被視為隨機的事實,也就是說,雜湊的第一個位元為
1
的機率是 50%,前兩個位元為
01
的機率是 25%,以及前三個位元為
001
的機率是 12.5%。知道這些機率,並且記錄開頭
處具有最多
0
的雜湊值(亦即,最不可能出現的雜湊值),就能夠估計到目前為止已經
看過多少個項目。
這個方法的良好類比就是擲硬幣。想像一下,我們想要擲硬幣 32 次,並且每次都要
得到人頭,那會有多難!數字 32 源自於我們正在使用 32 位元雜湊函式的事實。如果
我們擲硬幣一次,並且出現數字,我們就儲存數字
0
,因為我們的最佳嘗試連續產生 0
個人頭。因為知道硬幣丟擲背後的機率,而且我們的最長序列的長度為 0,你能夠估
計我們已經實驗過
2^0
=
1
次。如果我們繼續擲硬幣,並且能夠在出現數字之前先得到
10 個人頭,那麼,我們就會儲存數字
10
,根據相同邏輯,你可以估計我們已經實驗過
2^10
=
1024
次。藉由這個系統,我們能夠估計的最高計數會跟我們考慮的最大丟擲次數
有關(就 32 次丟擲而言,這是
2^32
=
4,294,967,296
)。
為了使用 LogLog 類型的計數器編寫這段邏輯,針對我們的輸入的雜湊值取得二進制表
示法,檢視一下,在看到第一個 1 之前會出現多少個 0。該雜湊值可被想成是連續 32
硬幣丟擲,在此,
0
表示人頭,
1
表示數字(亦即,
000010101101 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

流畅的Python

流畅的Python

Luciano Ramalho
手把手教会你linux

手把手教会你linux

桑德.范.乌格特

Publisher Resources

ISBN: 9789863477105