乱数を生成し、特定の user_id のデータベース内のテーブルに発行しようとしています。問題は、同じ番号を 2 回使用できないことです。これを行う方法は無数にありますが、アルゴリズムに非常に熱心な人が、次の基準が満たされているという点で、洗練されたソリューションで問題を解決する賢い方法を持っていることを願っています。
1) データベースへのクエリが最小限に抑えられます。2) メモリ内のデータ構造のクロールが最小限に抑えられます。
基本的に、アイデアは次のことを行うことです
1) 0 から 9999999 までの乱数を作成します
2) その数が存在するかどうかを確認するためにデータベースをチェックします
または
2) すべての数についてデータベースにクエリを実行します
3) 返された結果がデータベースから取得したものと一致するかどうかを確認します
4) 一致する場合は、繰り返しますステップ1、そうでない場合、問題は解決されています。
ありがとう。
いいえ、あなたのアルゴリズムはスケーラブルではありません。私が以前に行ったことは、数値をシリアルに発行し (毎回 +1)、それらを XOR 演算に渡してビットをごちゃまぜにすることで、乱数のように見えます。もちろん、それらは実際にはランダムではありませんが、ユーザーの目にはそう見えます。
[編集]追加情報
このアルゴリズムのロジックは次のようになります。既知のシーケンスを使用して一意の番号を生成し、それらを決定論的に操作するため、シリアルに見えなくなります。一般的な解決策は、何らかの形式の暗号化を使用することです。これは、私の場合は XOR フリップフロップでした。これは、可能な限り高速であり、数値が衝突しないという保証を満たしているためです。
ただし、速度よりもランダムに見える数字を優先する場合は、他の形式の暗号化を使用できます (一度に多くの ID を生成する必要はありません)。さて、暗号アルゴリズムを選ぶ上で重要なポイントは「数字が衝突しないという保証」です。暗号化アルゴリズムがこの保証を満たすことができるかどうかを証明する方法は、元の数値と暗号化の結果のビット数が同じかどうか、およびアルゴリズムが可逆 (バイジェクション) であるかどうかを確認することです。
[解決策を拡張してくれたAdam LissとCesarBに感謝]
GUID を使用しないのはなぜですか。ほとんどの言語には、これを行うための組み込みの方法が必要です。一意であることが保証されています (非常に合理的な範囲で)。
オーバーザトップのソリューションが必要ですか?
ランダム性は暗号化の品質を意図したものではなく、user_id によってユーザーの寿命を推測するのを思いとどまらせるのに十分だと思います。
開発中に、1,000 万個すべての数字のリストを文字列形式で生成します。
必要に応じて、途中に定数文字列を追加するなど、簡単な変換を実行します。(これは、結果が予測可能すぎる場合に備えてです。)
gperfなどの完全ハッシュ関数を生成するツールにそれらを渡します。
結果のコードを使用して、実行時にユーザーの ID を、他のハッシュ値と競合しないことが保証されている一意のハッシュ値にすばやくエンコードできます。
mysql SELECT CAST（RAND（）* 1000000 AS INT）のステートメントを試してください
仮定:
乱数を 64 ビット整数として、上位 32 ビットに (行挿入時の) タイムスタンプを、下位 32 ビットに user_id を格納するなど、単純なことを行うことができます。同じユーザーの新しい行を追加する頻度に応じて、タイムスタンプに適切な解決策を使用すれば、同じユーザーの複数の行に対しても一意になります。ランダム列の一意の制約と組み合わせて、ロジックでそのようなエラーをキャッチしてから、再試行してください。
私はOddthinkingのアイデアが好きですが、世界で最も強力なハッシュ関数を選択する代わりに、次のようにすることができます。
MD5は高速であり、文字列が配列に属しているかどうかをチェックすると、SELECTを回避できます。
私は実際にこれについて以前に記事を書きました。ロバート・グールドの答えと同じアプローチを取りますが、xor フォールディングを使用してブロック暗号を適切な長さに短縮する方法と、2 の累乗ではない範囲で順列を生成する方法をさらに示します。ユニークプロパティ。
これについてはいくつかの方法があります。1 つの方法は、0000000 から 9999999 までの数字で配列を作成し、この配列でこれらの数字をランダムに選択し、選択した数字の値を最大値 Max と交換してから max を減らすことです。 1 この配列の別のランダムなメンバーを新しい最大値まで選択します
Max を 1 減らすたびに
例（基本）：（右側には、実際のプログラムで削除する必要があるコメントがあります）Rndfuncは、使用している乱数ジェネレーター関数への呼び出しです
dim array(0 to 9999999) as integer
for x% = 1 to 9999999
array(x%)=x%
next x%
maxPlus = 10000000
max =9999999
pickedrandom =int(Rndfunc*maxPlus) picks a random indext of the array based on
how many numbers are left
maxplus = maxplus-1
swap array(pickedrandom) , array(max) swap this array value to the current end of the
array
max = max -1 decrement the pointer of the max array value so it
points to the next lowest place..
次に、選択したい数値ごとにこれを続けますが、非常に大きな配列を使用するオプションが必要になります
もう1つの方法は次のとおりです。数値を生成し、動的に拡張できる配列に格納してから、新しい数値を選択し、この場合、配列の最初の要素から最後の要素までの中間にある値と比較します一致する場合は最初に選択された数字になります別の乱数を選択し、サイズに従って配列を並べ替えます。一致しない場合は、天候に応じて、比較した数値よりも大きくまたは小さくなります。リストが一致せず、比較対象よりも大きいまたは小さい場合は、距離の半分のリスト。
ギャップサイズが1に達するまで半分にするたびに、一度チェックして一致がないので停止します。次に、番号がリストに追加され、リストが昇順で再シャッフルされます。乱数の選択が完了しました...これが役立つことを願っています..
本当にやりたくないことがわかると思います。データベース内の数値が増加すると、「この数値が取得されていないことを確認する」ループに多くの時間を費やす可能性があります。
個人的には、代替手段としてハッシュを使用できましたが、より良い解決策を見つけるには、なぜこのようにしたいのかを知る必要があります.
私の経験は、単純に PHP で RNG を使用することでした。特定のサイズの数値を使用していることがわかりました（intを使用しているため、最大4Gです）。いくつかのテストを実行したところ、平均して 500,000 回の反復で 120 個の重複が得られたことがわかりました。ループを何度も実行した後、3 通を取得することはありませんでした。私の「解決策」は、挿入して失敗したかどうかを確認し、新しいIDを生成してやり直すことでした。
私のアドバイスは、同じことをして、あなたの衝突率を見て、それがあなたのケースに受け入れられるかどうかを確認することです.
これは最適ではないので、誰か提案があれば私も探しています:)
編集: 私は 5 桁の ID ([a-zA-z0-9]{5,5}) に制限されていました。ID が長いほど (組み合わせが多くなり、衝突が少なくなります)。たとえば、メールの md5 が競合することはほとんどありません。
問題は、乱数を生成している場合、無限に重複を生成する可能性が非常に高いことです。
でも：
<?php
//Lets assume we already have a connection to the db
$sql = "SELECT randField FROM tableName";
$result = mysql_query($sql);
$array = array();
while($row = mysql_fetch_assoc($result))
{
$array[] = $row['randField'];
}
while(True)
{
$rand = rand(0, 999999);
if(!in_array($rand))
{
//This number is not in the db so use it!
break;
}
}
?>
これもあなたが望むことを行いますが、これは長い間スケーリングされないため、悪い考えです。最終的に配列が大きくなり、データベースにまだないランダムを生成するのに非常に長い時間がかかります.
非反復期間が長い疑似乱数ジェネレーターを設計するのは簡単です。たとえば、これは、あなたが望むのと同じものに使用されています。
ところで、ユーザーIDを順番に発行しないのはなぜですか?
0 から 9 999 999 までの「乱数」を本当に取得したい場合は、「乱数化」を 1 回行ってから、結果をディスクに保存します。
望む結果を得るのは難しくありませんが、「乱数を取得する」というよりも、「数字で長いリストを作成する」ようなものだと思います。
$array = range(0, 9999999);
$numbers = shuffle($array);
$numbers の現在の位置へのポインターも必要です (データベースに保存します)。0 から始めて、新しい番号が必要になるたびに増分します。(または、ポインターを使用したくない場合は、array_shift() または array_pop() を使用できます。)
適切な PRNG (疑似乱数ジェネレーター) アルゴリズムには、同じ状態になることのないサイクル タイムがあります。PRNG から取得した数値で PRNG の状態全体を公開すると、ジェネレーターの期間中に一意であることが保証された数値が得られます。
これを行う単純な PRNG は、次の式を反復する' Linear Congruential ' PRNG と呼ばれます。
X(i) = AX(i-1)|M
係数の適切なペアを使用すると、32 ビット アキュムレータを使用した単純な PRNG から 2^30 (約 10 億) の期間を取得できます。計算の中間の 'AX' 部分を保持するには、64 ビット長の long 一時変数が必要になることに注意してください。すべてではないにしても、ほとんどの C コンパイラがこのデータ型をサポートします。ほとんどの SQL 方言では、数値データ型でも実行できるはずです。
A と M の適切な値を使用すると、優れた統計的および幾何学的特性を持つ乱数ジェネレーターを取得できます。これについては、Fishman と Moore によって書かれた有名な論文があります。
M = 2^31 - 1 の場合、以下の A の値を使用して、かなり長い期間 (2^30 IIRC) の PRNG を取得できます。
A の適切な値:
742,938,285
950,706,376
1,226,874,159
62,089,911
1,343,714,438
このタイプのジェネレータは (定義により) 暗号的に安全ではないことに注意してください。それから生成された最後の数を知っていれば、次に何をするかを予測できます。残念ながら、暗号化されたセキュリティと保証された非反復性を同時に得ることはできないと思います。PRNG が暗号的に安全であるためには (例: Blum Blum Shub )、生成された数値で十分な状態を公開して、シーケンス内の次の数値を予測できるようにすることはできません。したがって、内部状態は生成された数よりも広く、(セキュリティを確保するために) 期間は生成可能な値の数よりも長くなります。これは、公開された数が期間内で一意ではないことを意味します。
同様の理由で、メルセンヌ・ツイスターのような長周期発電機にも同じことが言えます。
PHP には、このための関数uniqidが既にあります。他の場所からデータにアクセスする必要がある場合に最適な標準の uuid を生成します。車輪を再発明しないでください。
乱数が繰り返されないようにしたい場合は、繰り返しのない乱数ジェネレーターが必要です (ここで説明されているように)。
基本的な考え方は、次の式seed * seed & pは、任意の入力に対して繰り返しのない乱数x such that 2x < pをp - x * x % p生成し、他のすべての乱数と同様に繰り返しのない乱数を生成するというものですが、p = 3 mod 4. したがって、基本的に必要なのは、できるだけ近い単一のプリム番号9999999だけです。このようにして、労力を単一の読み取りフィールドに減らすことができますが、生成される ID が大きすぎるか、生成される ID が少なすぎるという欠点があります。
このアルゴリズムはうまく並べ替えられないため、シードと生成された値の間の 1 対 1 の関係を破壊することなく正確な値を変更するために、XOR または加算、またはその他のアプローチと組み合わせることをお勧めします。