2026-09-28
LinearCount.hs
linearCount :: [Int] -> Maybe Double
HyperLogLog のレジスタの並び regs から異なる値の個数を見積もる linearCount を書いてください。レジスタの総数を m、値が 0 のレジスタの数を v として m * log (m / v) を Just で返し、0 のレジスタが1つもないとき(regs が空のときも)は Nothing を返します。linearCount [0, 0, 0, 0] → Just 0.0、linearCount [1, 0, 2, 0] → Just 2.772588722239781、linearCount [1, 2] → Nothing
Reference
linearCount :: [Int] -> Maybe Double
linearCount regs
| zeros == 0 = Nothing
| otherwise = Just (m * log (m / zeros))
where
m = fromIntegral (length regs)
zeros = fromIntegral (length (filter (== 0) regs))
length が返すのは Int で、Int は Fractional でも Floating でもないので、そのままでは / にも log にも渡せません。数えた結果を fromIntegral で変換すると、m と zeros の型は、Just (m * log (m / zeros)) が Maybe Double であることから Double に決まります。
zeros == 0 は Double どうしの比較ですが、整数を変換した値なので誤差は入りません。この判定がないと、0 のレジスタが1つもないときに m / 0 が Infinity になり、log を通って Just Infinity が返ります。空のリストなら 0 / 0 で NaN です。
掲載したのは参考実装で、唯一の正解ではありません。個数を Int のまま数えて 0 と比べ、式を計算するところで初めて fromIntegral を使う書き方もできます。HyperLogLog は、見積もった個数がレジスタの数に比べて小さいとき、レジスタの最大値から作る推定値ではなくこの式を使います1。
- Flajolet らの論文では、通常の推定値が 5m/2 以下で、しかも値が 0 のレジスタがあるときに、この線形カウントに切り替えます。値の少ないうちは多くのレジスタが 0 のままで、通常の推定値が大きくずれるからです。