10

ユーザーがシステムに新しいアイテムを追加するとき、そのアイテムに対して一意の非インクリメント疑似ランダム 7 桁コードを生成したいと考えています。作成されるアイテムの数は数千 (<10,000) にすぎません。

一意である必要があり、2 つのアイテムが同じ情報を持つことはないため、ハッシュを使用できますが、他の人と共有できるコードである必要があります。したがって、7 桁です。

私の最初の考えは、乱数の生成をループし、それがまだ使用されていないことを確認し、使用されている場合はすすぎ、繰り返すことでした。衝突の可能性が低いことを考えると、これは不快な場合でも合理的な解決策だと思います。

この質問への回答は、すべての未使用の数字のリストを生成し、それらをシャッフルすることを提案しています。おそらく、このようなリストをデータベースに保持することもできますが、比較的めったに発生しないものに対して 10,000,000 件のエントリについて話しているのです。

誰かがより良い方法を持っていますか？

4

11 に答える 11

15

7桁の素数Aと大きな素数Bを選び、

int nth_unique_7_digit_code(int n) {
    return (n * B) % A;
}

これによって生成されるすべての一意のコードの数はAになります。

より「安全」になりたい場合は、次のようにしますpow(some_prime_number, n) % A。

static int current_code = B;
int get_next_unique_code() {
   current_code = (B * current_code) % A;
   return current_code;
}
于 2010-02-11T15:15:51.487 に答える
5

増分 ID を使用して、固定キーで XOR することができます。

const int XORCode = 12345;

private int Encode(int id)
{
    return id^XORCode;
}

private int Decode(int code)
{
    return code^XORCode;
}
于 2010-02-11T15:10:51.237 に答える
4

正直なところ、7 桁のコードを 2,000 個だけ生成したい場合、1,000 万個の異なるコードが利用可能である場合、ランダムなコードを生成して衝突をチェックするだけで十分だと思います。

最初のヒットで衝突が発生する可能性は、最悪のシナリオでは約 1,000 分の 1 であり、新しい 7 桁のコードを生成して衝突を再度チェックするための計算作業は、辞書、または同様のソリューション。

ハリーオーバーが提案した 7 桁のコードの代わりに GUID を使用することも確かに機能しますが、もちろん、ユーザーが GUID を覚えるのは少し難しくなります。

于 2010-02-11T15:08:44.327 に答える
2

アイテムが 10.000 未満であるため、すべてのアイテムの一意の番号を保存するには 4 桁しか必要ありません。7 桁なので、3 桁余分に持っています。

4 桁の一意のシーケンス番号と 3 桁の乱数を組み合わせると、一意でランダムになります。生成する新しい ID ごとにシーケンス番号を増やします。

それらを任意の順序で追加するか、混合することができます。

seq = abcd、rnd = ABC

次の ID を作成できます。

  • abcdABC
  • ABCabcd
  • aAbBcCd

混合アルゴリズムを 1 つだけ使用すると、ランダムに見える一意の数値が得られます。

于 2010-02-11T15:48:22.950 に答える
2

より一意になるため、7 桁のコードの代わりに GUID を使用することをお勧めします。.NET がこれを行うため、GUID の生成について心配する必要はありません。

于 2010-02-11T15:05:42.827 に答える
2

「一意の」ID のすべてのソリューションには、どこかにデータベースが必要です。使用されている ID を含むデータベースか、フリー ID を含むデータベースのいずれかです。お気づきのように、フリー ID のデータベースはかなり大きくなるため、ほとんどの場合、「使用済み ID」データベースを使用して衝突をチェックします。

とはいえ、一部のデータベースは、ランダムな順序で範囲内の ID を既に返す「ランダム ID」ジェネレーター/シーケンスを提供しています。

これは、それ自体を繰り返さずに範囲内のすべての数値を作成できる乱数ジェネレーターと、その状態をどこかに保存できる機能を使用して機能します。したがって、ジェネレーターを 1 回実行し、ID を使用して新しい状態を保存します。次の実行では、状態を読み込み、ジェネレーターを最後の状態にリセットして、次のランダム ID を取得します。

于 2010-02-11T15:09:13.463 に答える
2

生成されたもののテーブルがあると思います。その場合、乱数を選択してデータベースと照合することに問題はありませんが、個別には行いません。それらを生成するのは安価ですが、DB クエリを実行するのはそれに比べて高価です。一度に 100 個または 1,000 個を生成し、DB にそれらのどれが存在するかを尋ねます。ほとんどの場合、2 回行う必要はありません。

于 2010-02-11T15:13:25.343 に答える
1

私は LFSR (リニア フィードバック シフト レジスタ) を使用しようとします。コードは非常にシンプルで、ウィキペディアなどどこでも例を見つけることができ、暗号的に安全ではありませんが、非常にランダムに見えます。また、主にシフト操作を使用しているため、実装は非常に高速です。

于 2010-02-11T15:50:53.373 に答える
0

ヒットする確率は非常に低いです。
たとえば、10^4のユーザーと10^7の可能なIDがあります。
使用済みIDを10回続けて選択する確率は10^-30になりました。
このチャンスは、誰の生涯にも一度よりも低いです。

于 2010-02-11T15:19:05.987 に答える
0

ユーザーに独自の 7 桁の番号を選択して、既存の番号の母集団 (使い果たされたときに保存したはずの番号) に対して検証するように依頼することもできますが、多くの 1234567、7654321 をフィルタリングすることになると思います。 、9999999、7777777 タイプの応答であり、フィルタリングを実現するためにいくつかの RegEx が必要になる場合があります。さらに、悪い、反復的なユーザー入力エクスペリエンスが発生しないように、そのようなシーケンスに対してユーザーに警告する必要があります。

于 2010-02-11T16:02:24.793 に答える
0

データベースには数千のアイテムしかないので、あなたのオリジナルのアイデアは正しいように思えます。数万のアイテムの並べ替えられた (インデックス付きの) リスト内の値の存在を確認するには、いくつかのデータ フェッチと比較が必要になるだけです。

リストを事前に生成するのは良い考えではないように思えます。必要以上の数を格納するか、それらの不足に対処する必要があるからです。

于 2010-02-11T15:11:52.633 に答える