生成唯一的随机字符串

Question

我正在和Dancer一起写一个非常小的URL缩短器.它使用REST插件将发布的URL存储在数据库中,该数据库具有六个字符的字符串,用户可以使用该字符串来访问短路的URL.

现在我对我的随机字符串生成方法有点不确定.

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;
}

这会生成一个六字符串,如果生成的字符串已经在数据库中,则会递归调用该函数.我知道有63 ^ 6个可能的字符串,但如果数据库收集更多条目,这将需要一些时间.也许它会变成一个几乎无限的递归,我想阻止它.

有没有办法生成独特的随机字符串,以防止递归？

提前致谢

Answer 1

我们真的不需要手动波动你的函数有多少次迭代(或递归).我相信,在每次调用时,迭代的预期数量geomtrically分配(即第一次成功之前的试验次数由管辖geomtric分布),其中有1意味着/ p,其中p是成功地找到未使用的字符串的概率.我相信p只是1 - n/63 ^ 6,其中n是当前存储的字符串的数量.因此,我认为你需要在数据库中存储300亿个字符串(~63 ^ 6/2),然后你的函数平均每次调用的次数超过2次(p = .5).

此外,geomtric分布的方差为1-P/P ^ 2,所以即使在30个十亿条目,一个标准偏差只是SQRT(2).因此,我预计〜99%的时间循环将花费2 + 2*sqrt(2)交互或~5次迭代.换句话说,我不会太担心它.