生成唯一的随机字符串。

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

该函数生成一个6个字符的字符串，如果生成的字符串已经存在于数据库中，则递归调用该函数。我知道总共有63^6种可能的字符串，但是如果数据库中的条目增多，这将需要一些时间。而且，这可能会变成几乎无限递归，我想要避免这种情况。

有没有办法生成唯一的随机字符串，并避免递归？

提前感谢您的帮助。

- Demnogonis

---

我对递归问题没有答案，但是我有一个关于无限猴子最终会打出让修女晕倒的URL的提示：some.eg/CuNwha -- 你可以去掉元音或者使用十六进制来避免这种情况。 - Ashley

Answer 1

我们不需要太过于推测函数会有多少次迭代（或递归）。我认为在每次调用时，预期的迭代次数符合几何分布（即在第一次成功之前进行的试验次数由几何分布决定），其平均值为1/p，其中p是成功找到未使用字符串的概率。我相信p只是1-n/63^6，其中n是当前存储的字符串数量。因此，在您的数据库中存储了300亿个字符串（~63^6/2）之前，您的函数平均每次调用递归超过2次（p = .5）。

此外，几何分布的方差为1-p/p^2，因此即使在300亿条目的情况下，一个标准偏差也只是sqrt(2)。因此，我预计99％的时间循环将少于2 + 2 * sqrt(2)次迭代或约5次。换句话说，我只是不会过于担心它。

- frankc

---

好的，所以在接下来的20年里没有什么可担心的:D谢谢。 - Demnogonis

Answer 2

从学术角度来看，这似乎是一个有趣的项目。但如果你正在工作并需要随机且不同的字符串，我建议使用Data::GUID模块。

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

my $guid = guid_string();

- ddoxey

---

是的，这是一个适用于完全唯一字符串的好模块。但我需要它们只有六个字符，因为用户必须输入它们...就像这样：some.url/Qehy3_将重定向到stackoverflow.com。 - Demnogonis

Answer 3

消除递归很容易；将递归调用转换为do-while循环即可。例如，将函数分成两个部分；“主”函数和一个辅助函数。 "主" 函数只是调用辅助函数并查询数据库以确保其唯一性。假设 generate_random_string2 是辅助函数，则此处是一个框架：

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

关于限制获得有效字符串之前的迭代次数，你可以保存上一个生成的字符串，并始终根据它来构建新的字符串。例如，当你开始时，还没有字符串，所以让我们假设你的字符串是'a'。然后下一次构建字符串时，你获取上一个构建的字符串（'a'），并对其进行转换，例如递增最后一个字符。这将给你'b'，如此往复。最终，你会得到你所关心的最高字符（比如'z'），此时你会添加一个'a'得到'za'，然后重复以上步骤。

现在没有数据库，只有一个持久值，你用它来生成下一个值。当然，如果你想要真正随机的字符串，你需要使算法更加复杂，但基本原则是相同的：

1.你当前的值是上一个存储值的函数。

2.当你生成一个新值时，你存储它。

3.确保你的生成将产生一个唯一的值（即从未出现过的值）。

- RonaldBarzell

---

这只是将无限递归改为了一个无限循环。 - TLP

好的，修改答案以考虑可能的无限循环。 - RonaldBarzell

Answer 4

我有一个基于使用MySQL的想法。

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();

这会给你一个增量十六进制值，左侧填充非零垃圾。

- ddoxey