たつをの ChangeLog : 2023-09-17

ユニークな文字列がたくさんあって、それぞれをいくつかのバケットになるべく均等に振り分けたい。

ユニークな文字列とは、例えばユニークなユーザ ID とか商品 ID とか。
タスクの要件はこんな感じ。

• ユニークな文字列たちを N 個のバケットに振り分ける
• なるべくランダムに振り分ける
• それぞれのバケットの文字列の数はなるべく同じに
• シェルのワンライナーで済ませたい

いろいろと試行錯誤した結果、対象文字列をMD5のハッシュ値に変換して整数にして mod するのが一番手軽かな。

1. 16バイトのバイナリが出てくる
   

   $ echo foobar | perl -MDigest::MD5 -nle 'print Digest::MD5::md5($_)' | od -t x1
   0000000    38  58  f6  22  30  ac  3c  91  5f  30  0c  66  43  12  c6  3f
   0000020    0a
   0000021
   

2. その最初の4バイトを整数 (unsigned long) にする
   

   $ echo foobar | perl -MDigest::MD5 -nle 'print unpack("L",Digest::MD5::md5($_))'
   586569784
   

3. それをバケット数 N で割って余り（＝バケット番号）を得る
   

   $ echo foobar | perl -MDigest::MD5 -nle 'print unpack("L",Digest::MD5::md5($_)) % 5'
   4
   

エンディアンの問題とかあるかもだけど、まあ困ったら考えればいいや。

バケット数ごとの振り分け結果です。
約122万のユニーク文字列数を使用。
だいたい均等の分配できてるっぽい。
厳密さは求めないのでこれでOK。

N = 3
408313 0
408764 1
408370 2

N = 4
306157 0
307042 1
305954 2
306294 3

N = 5
244633 0
245089 1
245880 2
244960 3
244885 4

N = 6
204129 0
204480 1
203698 2
204184 3
204284 4
204672 5

N = 10
122542 0
122427 1
122685 2
122694 3
121956 4
122091 5
122662 6
123195 7
122266 8
122929 9

過去記事

• 【Perl】文字列をハッシュ関数でハッシュ値に変換[2013-06-04-1]
  • 文字列を256進数とみなす方法
  • 今回まずそれを試したんだけど偏りが大きかったので断念