1

以下の要件を満たす Java アプリケーションの一意の番号を生成する必要があります -

  1. 16進数9桁
  2. 毎日生成される約 600,000 の数字
  3. 番号は、最低 7 日間は一意である必要があります。7 日以上繰り返されても問題ありません。
  4. 負荷のピーク時には、約 15 秒間、毎秒約 800 の一意の番号を生成する必要があります。

失敗した解決策 -

    public static String getUniqueId() {
        String uniqueTime = Long.toHexString(System.nanoTime());
        String uniqueId = uniqueTime.substring(uniqueTime.length() - 9);

        return uniqueId;
    }

nanoTime を使用して 12 桁の 16 進数を生成します。左の 3 文字を切り捨てます。nanoTime は、ピーク負荷の処理に役立ちます。

これは正しくなく、重複が発生する可能性があると思います。

誰でも良いクイックアルゴリズムを提供できますか?

4

7 に答える 7

3

番号を生成するために1つのスレッドのみが使用される場合：

long nextId = counter % MAX_VALUE;
counter++;
return convertToHex(nextId);

複数のスレッドの場合：

long nextId = atomicLongCounter.getAndIncrement() % MAX_VALUE;
return convertToHex(nextId);

注：@Gumboの計算を考えると、最大値に達するには313年かかるため、モジュロを削除することもできます。

于 2012-05-27T15:18:05.147 に答える
2

UUIDを使用するのはどうですか？このような状況では非常に便利です。利用可能なJava実装。

于 2012-05-27T16:22:51.093 に答える
1

簡単な答え: 暗号化。暗号化は可逆であるため、入力が一意である場合、出力が一意であることを保証できます。36 ビットのブロック暗号 (36 ビット = 9 桁の 16 進数) を使用して、数字 0、1、2、3、4、... を暗号化します。

余裕のある時間帯に事前に必要な数だけ事前生成して保存できます。

一般的なブロック暗号のほとんどは 36 ビットではありません (DES は 64 ビットです) が、Hasty Pudding Cypherには 36 ビットのバリアントがあります。それ以外の場合は、RC4 やeSTREAM暗号の 1 つなどの高速ストリーム暗号を使用できます。

ETA: ストリーム サイファーは数値ごとに再キー化する必要があるため、おそらく目的には遅すぎるでしょう。一意性は同じキーを使用している場合にのみ保証されるため、キーの再生成も一意性に影響を与えます。

于 2012-05-27T16:29:12.180 に答える
0

「ランダムに見える」ために数字が必要ない場合は、他の人が提案しているように、カウンターを使用することができます。

複雑なものを探しているのは、数字を「ランダムに」見せたいからだと思います。その場合、次のことができます。

  • SecureRandomのインスタンスを使用して番号を割り当てます
  • 割り当て時にマップされた「現在割り当てられている」数値のマップをメモリに保持します（ConcurrentHashMapに格納されているこのデータを含む600Kの数値は、数十メガバイトのデータのオーダーになると思います。したがって、今日では大したことではありません。標準）
  • 新しい番号を割り当てる必要があるたびに、SecureRandomのインスタンスを介して9つのランダムな16進数を生成します（配列に5つのランダムなバイトを入力するように要求し、4つのビットを破棄すると、9つの16進数に相当するランダムデータが得られます）
  • 新しい番号が割り当てられた番号のマップにすでに含まれているかどうかを確認します。その場合は、ループして新しい番号を生成し、一意の番号を取得します。実際には、これは、言及したボリュームに対して1週間に100回程度しか発生しないため、アカウントを作成する必要はありますが、パフォーマンスへの影響はありません。それのための;
  • 定期的に、割り当てられた番号のマップをスキャンし、7日以上割り当てられた番号を削除して、再利用できるようにします。

実際のアプリケーションの場合、永続性についても考慮する必要があります。番号が割り当てられるたびに、クライアントに返す前にデータベースに永続化する必要があります。これにより、サーバーがクラッシュした場合に状態を回復できます。 。同様に、パージ操作では、メモリ内のマップから削除する前に、データベースから割り当てが削除されます。

于 2012-05-27T16:17:33.600 に答える
0

AtomicLong.incrementAndGet()トリックを行う必要があります。

JVM インスタンス間で永続化する必要がある場合は、範囲を割り当て、その範囲の最大値をデータベースまたは他のトランザクション ストアに保存し、AtomicLong(さらに、その範囲を超えないようにするための適切なロック。

ただし、1回の実行で一意の番号が必要な場合AtomicLong.incrementAndGetは、単純で、-1にラップするまで一意であることが保証されます。これは、1）生涯に発生することはなく、2）簡単に確認できます。

于 2012-05-28T00:28:38.977 に答える
0

-同時数生成の別の可能性

衝突しないことが保証された番号を生成する最大 10 個の個別のスレッド/プロセス/マシンを持つことができます。

シーケンシャルカウンターを使用して整数を生成するだけです

start one of them at 0, use increments of 10
start the next at 1, increments of 10
start the next at 2, increments of 10

上記のいずれかが完全にロードされたとしても、9 桁では不十分になる前に約 1 億のシーケンスがあり、1 日あたり 1 ミルしか生成しないため、9 桁をオーバーフローすることなく 7 日間続けることができます。

ここで良いことは、スレッド/プロセス/マシンが何も共有されていないことです。

ところで-これを基数16で直接行うことができます-10の代わりに16の増分を使用するだけです。または基数5、5の増分など...

于 2012-05-27T15:58:00.913 に答える
0

部分的には娯楽のために、あなたが与えた仕様から別の可能性も提案させてください. また、既知のシードから開始して、1 週間に生成する必要がある数値の量に対して実際には重複を生成しない疑似乱数生成アルゴリズムを見つけることもできます。

たとえば、XORShift generatorに基づく次の例では、重複のない 600000*7 個のランダムな 9 桁の数字が生成されます。

        long seed = 1;
        for (long i = 1; i <= 600000*7; i++) {
            long x = seed++;
            for (int n = 0; n < 3; n++) {
                x ^= (x << 21);
                x ^= (x >>> 35);
                x ^= (x << 4);
            }
          x &= 0xfffffffffL;

          // "x" is now the next unique, random-looking number in the sequence
        }

この方法の利点は、これまでに生成された数値を判別するために、カウンター以外のストレージが必要ないことです。

不利な点は、毎週、まったく同じ順序でやり直すことです。もちろん、割り当てられた番号の量を突然増やす必要がある場合は、別のシーケンスを見つける必要があるかもしれません.

とにかく、役に立つ場合に備えて、ミックスに入れようと思いました.

于 2012-05-27T16:49:05.663 に答える