3

Railsアプリのモデルに対して一意の非順次トークンを生成するアルゴリズムを使用しようとしています。

例えば:

MyModel.create.token #=> '183685'
MyModel.create.token #=> '456873'
MyModel.create.token #=> '813870'

これを処理するために考えられる唯一の方法は、ランダムなものを作成し、衝突をチェックして、再試行することです。これは私にはちょっと臭いコードのように思えます。

class MyModel < ActiveRecord::Base
  before_create :set_token

  def set_token
    existing_model_count = nil

    # Loop while we have a token that already belongs to an existing model.
    while existing_model_count.nil? || existing_model_count > 0
      random_token = TokenGenerator.random_token
      existing_model_count = MyModel.where(token: random_token).count
    end

    # Loop exited, meaning we found an unused token.
    self.token = random_token
  end
end

while不明な回数反復するループを含まない、これを行うためのより良い方法はありますか?


ここでの例は ruby​​ ですが、これは一種の一般的なアルゴリズムの問​​題であり、どの言語にも当てはまる可能性があるため、他の言語での解決策を歓迎します。

4

6 に答える 6

6

「トークン」が何らかの範囲の整数値であり、トークンの数が事前にわかっている場合、単純なボブ フロイドのアルゴリズム (Bentley の「Programming Peals」またはこちらで説明) は、再試行を行わずに一意の乱数を生成します。すでに使用されている数字を「マーク」するために追加のストレージを使用しますが、ランダムに生成された数字が既に使用されている場合は、巧妙に未使用の数字を即座に見つけ出すことができます (つまり、試行錯誤を繰り返す必要はありません)。

ただし、そのアルゴリズムの問​​題の 1 つは、生成される数値が一般的に順序付けられていなくても、順序が完全にランダムではないことです。言い換えれば、アルゴリズムは、範囲から選択した個々の数値の均一な分布を保証しますが、すべての可能な結果シーケンス間での結果シーケンスの均一な分布を保証しません。

それがあなたにとって大したことであるかどうか - あなただけが決めることができます。範囲の長さに比べて生成するトークンの数が少ない場合、このアルゴリズムは非常に満足のいく結果を提供します。トークンの数が範囲の長さに近い場合、このアルゴリズムは「ほぼソートされた」シーケンスを生成します。

于 2013-03-22T21:09:08.487 に答える
2
cipher = OpenSSL::Cipher::AES.new(128, :CBC).encrypt
cipher.update(MyModel.create.object_id.to_s(36))
于 2013-03-22T22:34:11.423 に答える
2

数時間ごとに cronjob を実行して、Redis コレクションに未使用の識別子を再設定します。バックグラウンドで実行できるようにするため、必要なときに Redis コレクションからポップするだけです。

于 2013-03-22T22:22:40.973 に答える