ユニークな文字列たちをいくつかのグループになるべく均等に振り分けたい!
2023-09-17-1
[Programming][Perl]
ユニークな文字列がたくさんあって、それぞれをいくつかのバケットになるべく均等に振り分けたい。
ユニークな文字列とは、例えばユニークなユーザ ID とか商品 ID とか。
タスクの要件はこんな感じ。
いろいろと試行錯誤した結果、対象文字列をMD5のハッシュ値に変換して整数にして mod するのが一番手軽かな。
エンディアンの問題とかあるかもだけど、まあ困ったら考えればいいや。
バケット数ごとの振り分け結果です。
約122万のユニーク文字列数を使用。
だいたい均等の分配できてるっぽい。
厳密さは求めないのでこれでOK。
ユニークな文字列とは、例えばユニークなユーザ ID とか商品 ID とか。
タスクの要件はこんな感じ。
- ユニークな文字列たちを N 個のバケットに振り分ける
- なるべくランダムに振り分ける
- それぞれのバケットの文字列の数はなるべく同じに
- シェルのワンライナーで済ませたい
いろいろと試行錯誤した結果、対象文字列をMD5のハッシュ値に変換して整数にして mod するのが一番手軽かな。
- 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
- その最初の4バイトを整数 (unsigned long) にする
$ echo foobar | perl -MDigest::MD5 -nle 'print unpack("L",Digest::MD5::md5($_))' 586569784
- それをバケット数 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進数とみなす方法
- 今回まずそれを試したんだけど偏りが大きかったので断念