生成獨特的隨機字符串

我正在用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個可能的字符串，但如果數據庫收集更多條目，這將需要一些時間。也許它會成爲一個近乎無限的遞歸，我想阻止它。

是否有方法可以生成唯一的隨機字符串，從而防止遞歸？

在此先感謝

來源

2012-12-03 Demnogonis

我沒有遞歸的答案，但我確實有一個關於無限猴子的提示，最終輸入的URL會讓修女變得微弱：'some.eg/CuNwha' - 你可以拉元音或去十六進制以防止這個。 – Ashley

我們並不需要對你的函數有多少次迭代（或遞歸）進行手動波動。我相信在每次調用時，預期的迭代次數是幾何分佈的（即第一次成功之前的試驗次數由geomtric distribution決定），其平均值爲1/p，其中p是成功找到未使用字符串的概率。我相信p只是1 - n/63^6，其中n是當前存儲的字符串的數量。因此，我認爲在你的函數平均每次調用超過2次（p = .5）之前，你需要在數據庫中存儲300億個字符串（〜63^6/2）。此外，地質分佈的方差爲1-p/p^2，所以即使在300億條目處，一個標準差也只是sqrt（2）。因此，我預計〜99％的循環將花費2 + 2 * sqrt（2）以上的迭代或5次迭代。換句話說，我不會太擔心。

來源

2012-12-03 22:25:49 frankc

好的，所以在接下來的20年裏沒什麼好擔心的：D謝謝 – Demnogonis

擺脫遞歸很容易;將你的遞歸調用變成一個do-while循環。例如，將你的函數分成兩部分; 「主」和助手。「main」只需調用助手並查詢數據庫以確保它是唯一的。假設generate_random_string2是幫手，這裏有一個骨架：

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

至於得到一個有效的字符串之前限制迭代次數，大約只保存最後生成的字符串，總是構建新的字符串作爲一個功能是什麼？

例如，當你開始時，你沒有字符串，所以我們只是說你的字符串是'a'。然後下一次你建立一個字符串時，你得到最後一個建立的字符串（'a'）並對它應用一個轉換，例如遞增最後一個字符。這給了你'b'。等等。最終你得到你最關心的角色（比如'z'），然後在這一點上追加'a'來獲得'za'，然後重複。

現在沒有數據庫，只有一個永久值用於生成下一個值。當然，如果你想要真正隨機的字符串，你必須使算法更復雜，但基本原理是相同的：

您的當前值是最後存儲的值的函數。
當您生成一個新值時，將其存儲。
確保您的一代將產生一個獨特的價值（以前沒有發生過）。

來源

2012-12-03 16:43:19 RonaldBarzell

這只是將無限遞歸更改爲無限循環。 – TLP

好吧，修改答案以考慮可能的無限循環。 – RonaldBarzell

從學術的角度來看，這似乎是一個有趣的計劃。但是，如果你在時鐘上，只需要隨機和獨特的字符串，我會使用Data :: GUID模塊。

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

my $guid = guid_string();

來源

2012-12-03 22:45:17 ddoxey

是的，這是一個完全獨特的字符串的好模塊。但我需要它們只有六個字符，因爲用戶必須在...中輸入它們：'some.url/Qehy3_'會重定向到'stackoverflow.com' – Demnogonis

我還有一個基於使用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();

這給了你哪些是左補齊非零垃圾增量十六進制值。

來源

2012-12-03 23:43:52 ddoxey

生成獨特的隨機字符串

回答

相關問題