2026-09-28
Registers.hs
import Data.Array (accumArray, elems)
import Data.Bits (countTrailingZeros, shiftR, (.&.))
rank :: Int -> Int
rank w = countTrailingZeros w + 1
registers :: [Int] -> [Int]
registers hs =
elems (accumArray max 0 (0, 3) [(h .&. 3, rank (h `shiftR` 2)) | h <- hs])
main :: IO ()
main = print (registers [5, 8, 12, 33, 8, 6])
これは何を出力するでしょうか?
Answer
[2,4,1,0] です。
各ハッシュ値 h は2つに分けて使われます。下位2ビット h .&. 3 がレジスタの番号で、残りのビット h `shiftR` 2 からは、最下位から数えて何ビット目に初めて 1 が立つかが rank として求まります。countTrailingZeros が末尾に並ぶ 0 の数を返すので、それに 1 を足した値です。
5(2進で 101)はレジスタ1に rank 1、8(1000)は残りが 10 なのでレジスタ0に rank 2、12(1100)は残りが 11 なのでレジスタ0に rank 1 を渡します。33(100001)は残りが 1000 でレジスタ1に rank 4、2度目の8はレジスタ0に同じ rank 2、6(110)はレジスタ2に rank 1 です。
accumArray max 0 (0, 3) は、4つのレジスタをどれも 0 から始め、同じ番号に来た値を max で1つにまとめます。レジスタ0は 2 と 1 と 2 の最大で 2、レジスタ1は 1 と 4 で 4、レジスタ2は 1 です。レジスタ3に振り分けられた値は1つもないので、初期値の 0 のまま残ります。
max でまとめるので、同じ値が何度来ても、どの順に来てもレジスタは変わりません。HyperLogLog が重複を数えずに異なる値の個数を見積もれるのはこのためです。rank が k になる確率はおよそ 2-k なので、大きな rank が記録されているレジスタほど、多くの異なる値がそこへ来たと推定できます。