生成两位数字不同的唯一代码
我想要生成唯一的代码号(确切地说是由7位数字组成)。代码号是随机生成的，并保存在MySQL表中。
我还有另一个要求。所有生成的代码至少应该有两位数的差异。这对于防止输入用户代码时的错误非常有用。希望它能够避免在执行某些操作时引用另一个用户代码，因为它更不可能错过两位数并匹配另一个现有的用户代码。
生成算法的工作原理很简单：
table.
- Generate
- 一次从MySQL
- 检索所有以前的代码。
- 用所有以前的代码减去生成的代码。
- 检查减法结果中的非零位数。
- 如果它> 1，接受生成的代码并将其添加到以前的codes.
- Otherwise，跳转到2。
<代码>H 113从2到6重复步骤从2到6的请求代码数。< code >H 214<代码>H 115保存在DB表中。< code >H 216g<217/code>
该算法工作良好，但问题与性能有关。当请求生成大量代码(如: 10,000 )时，需要很长时间才能生成代码。
的问题是：是否有任何方法来提高该算法的性能？
如果这很重要，我将在Ubuntu服务器上使用perl + MySQL。
回答 5
Stack Overflow用户
发布于 2011-03-21 16:19:46
你考虑过Luhn算法的一个变体吗？Luhn用于在许多应用程序(包括信用卡帐号)中生成数字字符串的检查数字。这是ISO-7812-1标准的一部分，用于生成标识符.它将捕获用一个不正确的数字输入的任何数字，这意味着任何两个有效数字至少有两位数不同。
查看Check算法：：LUHN in CPAN中的perl实现。
Stack Overflow用户
发布于 2011-03-21 16:18:46
不要检索现有代码，只需生成一个潜在的新代码，并查看数据库中是否有冲突的代码：
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;
}Stack Overflow用户
发布于 2011-03-21 16:20:28
将数字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或者.那么你就不能使用1111111号。由于每数字还有8个其他选项和7个数字，您只需要检查56个可能的值。检查这些值是否在您的哈希表中。如果尚未使用任何这些值，则可以使用随机节点。如果您使用过它们中的任何一个，那么就不能。
- 从增广树中删除节点。确保您维护了增广的information.
- If --您不能使用该值，返回到步骤1.
- ，如果您可以使用该值，您将有一个新的随机代码。将其添加到哈希表中.
现在，检查一个值是否可用需要O(1)时间而不是O(n)时间。另外，找到另一个可用的随机值来检查需要O(log )时间，而不是.啊..。我不知道怎么分析你的算法。
长话短说，如果您从头开始并使用此算法，您将生成O(n log n)中有效代码的完整列表。因为n是10,000,000，它需要几秒钟或者什么的时间。
每个人我都在做数学计算吗？如果没有确认，或者我需要澄清什么，请告诉我。
https://stackoverflow.com/questions/5380210
复制相似问题
腾讯云开发者
