生成兩位數字不同的唯一代碼

我想生成唯一的代碼編號（完全由7位數字組成）。代碼編號是隨機生成的，並保存在MySQL表中。生成兩位數字不同的唯一代碼

我有另一個要求。所有生成的代碼至少應有兩位數字。這對於在輸入用戶代碼時防止錯誤很有用。希望它可以防止在執行某些操作時引用另一個用戶代碼，因爲它不太可能錯過兩位數字並與另一個現有用戶代碼相匹配。

的生成算法的工作只是想：

找回以前所有的代碼，如果任何來自MySQL表。
一次生成一個代碼。
用以前的所有代碼減去生成的代碼。
檢查減法結果中的非零位數。
如果它大於1，接受生成的代碼並將其添加到以前的代碼。
否則，跳轉到2.
重複步驟從2到6的請求代碼數。
將生成的代碼保存在數據庫表中。

該算法工作正常，但問題與性能有關。請求生成大量代碼時，完成代碼生成需要很長時間，如：10,000。

問題：有什麼辦法可以提高這個算法的性能嗎？

我在Ubuntu服務器上使用perl + MySQL（如果有的話）。

來源

2011-03-21 Khaled

您是否考慮過Luhn算法的變體？ Luhn用於在許多應用程序中爲數字串生成一個校驗位，包括信用卡帳號。它是生成標識符的ISO-7812-1標準的一部分。它會捕獲任何輸入的數字，並輸入一個不正確的數字，這意味着任何兩個有效數字至少有兩位數不同。

查看算法:: LUHN CPAN中的perl實現。

來源

2011-03-21 16:19:46 ataylor

校驗位是此應用程序的絕佳主意。 – 2011-03-21 17:05:26

這是一個非常好的主意。它還確保沒有兩個代碼只能有一個數字變化，因爲更改任何數字也會改變校驗和。 – 2011-03-22 02:24:48

更正 - 更改數字會_可能會更改校驗和。如果你嘗試過，你可以創建兩個只相差一個字符的代碼。 – 2011-03-22 02:35:58

不要檢索現有的代碼，只是產生一個潛在的新代碼，看看是否有任何衝突的人在數據庫：

SELECT code FROM table WHERE abs(code-?) regexp '^[1-9]?0*$';

（其中佔位符是新生成的代碼）。

啊，我錯過了很多代碼一次生成的部分。這樣做（完全未經測試）：

my @codes = existing_codes(); 

my $frontwards_index = {}; 
my $backwards_index = {}; 
for my $code (@codes) { 
    index_code($code, $frontwards_index); 
    index_code(reverse($code), $backwards_index); 
} 

my @new_codes = map generate_code($frontwards_index, $backwards_index), 1..10000; 

sub index_code { 
    my ($code, $index) = @_; 
    push @{ $index{ substr($code, 0, length($code)/2) } }, $code; 
    return; 
} 

sub check_index { 
    my ($code, $index) = @_; 
    my $found = grep { ($_^$code) =~ y/\0//c <= 1 } @{ $index{ substr($code, 0, length($code)/2 } }; 
    return $found; 
} 

sub generate_code { 
    my ($frontwards_index, $backwards_index) = @_; 

    my $new_code; 
    do { 
     $new_code = sprintf("%07d", rand(10000000)); 
    } while check_index($new_code, $frontwards_index) 
     || check_index(reverse($new_code), $backwards_index); 
    index_code($new_code, $frontwards_index); 
    index_code(reverse($new_code), $backwards_index); 
    return $new_code; 
}

來源

2011-03-21 16:18:46 ysth

正則表達式搜索不能被索引，所以這是隻比現有解決方案更好。 – 2011-03-22 02:25:30

@Nick Johnson：使服務器讀取所有現有數據並使服務器返回所有現有數據有很大的區別。但是我的SQL解決方案實際上並沒有幫助，因爲需要很多新代碼。 – ysth 2011-03-22 02:32:09

有一個恆定的因素差異。這意味着它還不能很好地擴展。 – 2011-03-22 02:35:25

將數字0到9,999,999放在擴展二叉搜索樹中。增強功能用於跟蹤左側和右側的子節點數量。因此，例如，當您的算法開始時，頂級節點應該具有5,000,000的值，並且應該知道其左側有5,000,000個節點，右側有4,999,999個節點。現在創建一個散列表。對於您已經使用的每個值，請從增強二分搜索樹中刪除其節點並將值添加到散列表。確保保持增強。

要獲得單個值，請按照下列步驟操作。

使用頂部節點來確定樹中剩下多少個節點。假設您剩下n個節點。選擇0到n之間的隨機數字。使用增強功能，您可以在log（n）時間內找到樹中的第n個節點。
找到該節點後，計算將使該節點上的值無效的所有值。假設您的節點的值爲1,111,111。如果您已經有2,111,111或3,111,111或...則不能使用1,111,111。由於每個數字和7位數字有其他8個選項，因此您只需檢查56個可能的值。檢查這些值是否在你的散列表中。如果您尚未使用任何這些值，則可以使用隨機節點。如果你使用過其中的任何一個，那麼你就不能。
從擴充樹中刪除您的節點。確保你保持增強的信息。
如果您不能使用該值，請返回步驟1.
如果您可以使用該值，則會有一個新的隨機碼。將它添加到散列表。

現在，檢查一個值是否可用需要O（1）時間而不是O（n）時間。此外，找到另一個可用的隨機值進行檢查需要O（log n）時間而不是......啊......我不知道如何分析你的算法。

長話短說，如果你從頭開始，使用這種算法，你會產生的有效代碼爲O的完整列表（N log n）的。由於n是10,000,000，所以需要幾秒鐘或什麼。

難道我做數學題，就在那裏的人呢？讓我知道，如果沒有檢查出來，或者我需要澄清什麼。

來源

2011-03-21 16:20:28

使用散列。

產生一個成功的代碼（未與任何現有的代碼有衝突），但在哈希表中的代碼，並且也把通過正好一個位相差到散在63個其他代碼後。

要查看是否有隨機生成的代碼將與現有代碼衝突，只是檢查是否在散存在的代碼。

來源

2011-03-21 16:24:53 mob

Howabout：

通過自增前一個生成一個6位代碼。通過遞增前一個模10來生成1位代碼。將兩者連接起來。

的Presto，保證在兩個數字不同。：D

（是的，有些face。，我假設'隨機'或至少是準隨機是必要的，在這種情況下，生成一個6位隨機密鑰，重複，直到它不是重複的獨特之列，重複，直到插不失敗的約束），然後生成一個校驗位，正如有人已經說了。）

來源

2011-03-21 16:26:46 Penfold

生成兩位數字不同的唯一代碼

回答

相關問題