Namaran

Code daily. Without assist.

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 が記録されているレジスタほど、多くの異なる値がそこへ来たと推定できます。