Namaran

Code daily. Without assist.

2026-09-28

Buckets.hs

import Data.Bits (countTrailingZeros)

registers :: Int -> [Int] -> [Int]
registers m hs =
  [ maximum (0 : [rank (h `div` m) | h <- hs, h `rem` m == i])
  | i <- [0 .. m - 1]
  ]
  where
    rank w = countTrailingZeros w + 1

ハッシュ値の並び hs を m 個のバケットに振り分け、バケットごとに rank の最大値を記録する registers です。ハッシュ値は負になることもあります。print (registers 4 [6, -7, 5]) はいま [0,1,1,0] を出力しますが、本来は [0,2,1,0] です。どこを直せばよいでしょうか?

Answer

h `rem` m == i を h `mod` m == i に変えます。

rem の結果は割られる数と同じ符号になるので、(-7) `rem` 4 は -3 です。i は 0 から 3 までしか動かないので、-7 はどのバケットの内包表記にも拾われず、エラーも出ないまま消えます。mod の結果は割る数と同じ符号になり、(-7) `mod` 4 は 1 です。

rank に渡す商には div を使っているので、組にすべきなのも mod です。div は負の無限大の方向に丸めるので (-7) `div` 4 は -2 になり、-2 * 4 + 1 で元の -7 に戻ります。rem と組になるのは0の方向に丸める quot で、div と rem を混ぜると h の分け方として辻褄が合いません。

直すと -7 はバケット1に入ります。商の -2 は2の補数で表すと末尾に 0 が1個並ぶので rank は 2 です。バケット1にはもう1つ 5 から rank 1 が来ていて、最大値の 2 が残ります。