2

ユーザー ID に基づいて乱数を均等に分散させようとしています。つまり、ユーザーが乱数を要求するたびに同じままである各ユーザーの乱数が必要です (ただし、ユーザーは番号を保存する必要はありません)。特定のユーザーIDの大きな配列に対して、分布をカウントする私の現在のアルゴリズム（PHP）は次のとおり$arrです。

$range = 100;
$results = array_fill(0, $range, 0);

foreach ($arr as $userID) {
    $hash = sha1($userID,TRUE);
    $data = unpack('L*', $hash);
    $seed = 0;
    foreach ($data as $integer) {
        $seed ^= $integer;
    }
    srand($seed);
    ++$results[rand(0, $range-1)];
}

これにより、ほぼ均等な分布が生成されることが期待されます。しかし、そうではありません！の各値が一意であることを確認しました$arrが、リスト内の 1 つのエントリは常に他のすべてのエントリよりも多くのアクティビティを取得します。ほぼ均等に分布する文字列のハッシュを生成するより良い方法はありますか? どうやらSHAは仕事をしていないようです。MD5と単純なcrc32も試しましたが、すべて同じ結果でした!?

私はクレイジーですか？$arr実際、各エントリが一意であることを確認していない唯一の説明はありますか?

4

4 に答える 4

5

sha1 ハッシュ番号は非常に均一に分散されています。これを実行した後：

<?php

$n = '';
$salt = 'this is the salt';

for ($i=0; $i<100000; $i++) {
    $n .= implode('', unpack('L*', sha1($i . $salt)));
}   

$count = count_chars($n, 1);
$sum = array_sum($count);

foreach ($count as $k => $v) {
    echo chr($k)." => ".($v/$sum)."\n";
} 

?>

この結果が得られます。各数値の確率:

0 => 0.083696057956298
1 => 0.12138983759522
2 => 0.094558704004335
3 => 0.07301783188663
4 => 0.092124978934097
5 => 0.088623772577848
6 => 0.11390989553446
7 => 0.092570936094051
8 => 0.12348330833868
9 => 0.11662467707838

ユーザーのIDに基づいて、sha1を単純な乱数ジェネレーターとして使用できます。

16 進数では、分布はほぼ完全です。

//  $n .= sha1($i . $salt, false);

0 => 0.06245515
1 => 0.06245665
2 => 0.06258855
3 => 0.0624244
4 => 0.06247255
5 => 0.0625422
6 => 0.0625246
7 => 0.0624716
8 => 0.06257355
9 => 0.0625005
a => 0.0625068
b => 0.0625086
c => 0.0624463
d => 0.06250535
e => 0.06250895
f => 0.06251425
于 2012-08-01T23:52:10.433 に答える
1

mt_rand()要求された範囲で非常に均等に分布する必要があります。ユーザーが作成されると、そのユーザーのランダムシードを作成しmt_rand()、常にそのユーザーmt_srand()のシードを使用します。

あなたの例のように、0から99までの均等な分布を得るには、mt_rand(0,$range-1). sha1、md5、またはその他のハッシュ アルゴリズムを使用してトリックを実行しても、単純なランダムよりも均等な分布は得られません。

于 2012-08-01T23:39:01.480 に答える
0

ここでの答えはすべて良いものですが、私にとって正しい答えを提供します。つまり、私は本当に頭がおかしいということです。どうやら、uniqコマンドは実際には期待どおりに機能しないようです (最初にデータをソートする必要があります)。したがって、説明は確かにの値$arrが一意ではなかったということでした。

于 2012-08-02T14:16:04.687 に答える
0

適切な分布が得られていないと結論付けた結果を投稿していただけると助かりますが、次の 3 つのいずれかが発生している可能性があります。

  1. 見ているサンプルが小さすぎるか、データの解釈を誤っています。他の人がコメントしているように、均一な分布が完全に均一な出力を持たないことは完全に合理的です。

  2. mt_randの代わりにを使用すると、より良い結果が得られますrand。

  3. （個人的には、これが最も可能性が高いと思います）シード生成を過度に最適化し、データを失う/ピジョンホール/乱数を生成する能力を損なう. あなたのコードを読んで、私はあなたが次のことをしていると思います：

    1. 未知の値の一様ランダム ハッシュを生成する
    2. ハッシュを long に分割し、それらをビット単位で XOR します。
    3. のシードを設定randし、そのシードから乱数を生成する

    しかし、なぜステップ 2 を行うのでしょうか。そこから得られるメリットは何だと思いますか？その一歩を踏み出してみて、ハッシュから抽出した最初の値をシードとして使用して、それがより良い結果をもたらさないかどうかを確認してください. ランダム性の良い経験則 - アルゴリズムを実装した人々の裏をかこうとしないでください。それはできません:)

于 2012-08-02T00:38:32.427 に答える