4

私はDancerで非常に小さなURL短縮サービスを書いています。これは、RESTプラグインを使用して、投稿されたURLを、ユーザーが短縮されたURLにアクセスするために使用する6文字の文字列とともにデータベースに保存します。

今、私は自分のランダムな文字列の生成方法について少し確信が持てません。

sub generate_random_string{
    my $length_of_randomstring = shift; # the length of 
                                        # the random string to generate

    my @chars=('a'..'z','A'..'Z','0'..'9','_');
    my $random_string;
    for(1..$length_of_randomstring){
        # rand @chars will generate a random 
        # number between 0 and scalar @chars
        $random_string.=$chars[rand @chars];
    }

    # Start over if the string is already in the Database
    generate_random_string(6) if database->quick_select('urls', { shortcut => $random_string });

    return $random_string;
}

これにより、6文字の文字列が生成され、生成された文字列がすでにDBにある場合は、関数が再帰的に呼び出されます。63 ^ 6の可能な文字列があることは知っていますが、データベースがより多くのエントリを収集する場合、これには時間がかかります。そして多分それはほぼ無限の再帰になるでしょう、それは私が防ぎたいです。

再帰を防ぐ一意のランダムな文字列を生成する方法はありますか？

前もって感謝します

4

4 に答える 4

5

関数の反復（または再帰）がいくつあるかについて、実際に手を振る必要はありません。すべての呼び出しで、予想される反復回数は幾何学的に分布していると思います（つまり、最初の成功までの試行回数は幾何学的分布によって決まります）。これは平均1 / pです。ここで、pは未使用の文字列を正常に見つける確率です。pはちょうど1-n/63 ^ 6だと思います。ここで、nは現在保存されている文字列の数です。したがって、関数が呼び出しごとに平均2回以上繰り返される前に、データベースに300億の文字列（〜63 ^ 6/2）を格納する必要があると思います（p = .5）。

さらに、幾何学的分布の分散は1-p / p ^ 2であるため、300億のエントリであっても、1つの標準偏差はsqrt（2）にすぎません。したがって、ループにかかる時間の約99％は、2 + 2 * sqrt（2）の相互作用または約5回の反復よりも少ないと予想されます。言い換えれば、私はそれについてあまり心配しません。

于 2012-12-03T22:25:49.263 に答える
4

学術的な立場からすると、これは取り組むべき興味深いプログラムのように思えます。しかし、あなたが時間に追われていて、ランダムで別個の文字列が必要な場合は、Data::GUIDモジュールを使用します。

use strict;
use warnings;
use Data::GUID qw( guid_string );

my $guid = guid_string();
于 2012-12-03T22:45:17.420 に答える
2

再帰を取り除くのは簡単です。再帰呼び出しをdo-whileループに変えます。たとえば、関数を2つに分割します。「メイン」とヘルパー。「メイン」のものは、単にヘルパーを呼び出し、データベースにクエリを実行して、データベースが一意であることを確認します。generate_random_string2がヘルパーであると仮定すると、スケルトンは次のようになります。

do {
   $string = generate_random_string2(6);
} while (database->quick_select(...));

有効な文字列を取得する前の反復回数を制限することに関しては、最後に生成された文字列を保存し、その関数として常に新しい文字列を作成するのはどうでしょうか。

たとえば、最初は文字列がないので、文字列が「a」であるとしましょう。次に、次に文字列を作成するときに、最後に作成された文字列（'a'）を取得し、それに変換を適用します。たとえば、最後の文字をインクリメントします。これにより、「b」が得られます。等々。最終的には、気になる最高の文字（たとえば、「z」）に到達し、その時点で「a」を追加して「za」を取得し、繰り返します。

これでデータベースはなくなり、次の値を生成するために使用する永続的な値が1つだけになります。もちろん、真にランダムな文字列が必要な場合は、アルゴリズムをより高度にする必要がありますが、基本的な原則は同じです。

  1. 現在の値は、最後に保存された値の関数です。
  2. 新しい値を生成するときは、それを保存します。
  3. 世代が一意の値（以前は発生しなかった値）を生成することを確認してください。
于 2012-12-03T16:43:19.117 に答える
1

MySQLの使用に基づいたもう1つのアイデアがあります。

create table string (
    string_id int(10) not null auto_increment,
    string varchar(6) not null default '',
    primary key(string_id)
);

insert into string set string='';

update string
    set string = lpad( hex( last_insert_id() ), 6, uuid() )
    where string_id = last_insert_id();

select string from string
    where string_id = last_insert_id();

これにより、ゼロ以外のジャンクが埋め込まれたままの増分16進値が得られます。

于 2012-12-03T23:43:52.647 に答える