Генерация уникальных кодов, которые отличаются в двух цифрах

Question

Я хочу сгенерировать уникальные кодовые номера (ровно из 7 цифр).Кодовый номер генерируется случайным образом и сохраняется в таблице MySQL.

У меня есть еще одно требование.Все сгенерированные коды должны отличаться как минимум двумя цифрами.Это полезно для предотвращения ошибок при наборе кода пользователя.Надеемся, что это предотвратит обращение к другому пользовательскому коду при выполнении некоторых операций, так как более вероятно, что он пропустит две цифры и совпадет с другим существующим пользовательским кодом.

Алгоритм генерации работает просто так:

1. Получить все предыдущие коды, если они есть, из таблицы MySQL.
2. Создать один код за раз.
3. Вычесть сгенерированный код из всех предыдущих кодов.
4. Проверить количествоненулевые цифры в результате вычитания.
5. Если это> 1, принять сгенерированный код и добавить его к предыдущим кодам.
6. В противном случае перейти к 2.
7. Повторите шаги с 2 по 6 для количества запрошенных кодов.
8. Сохраните сгенерированные коды в таблице БД.

Алгоритм работает нормально, но проблема связана с производительностью.Генерация кодов занимает очень много времени при запросе на генерацию большого количества кодов, таких как: 10 000.

Вопрос: Есть ли способ улучшить производительность этого алгоритма?

Я использую perl + MySQL на сервере Ubuntu, если это имеет значение.

Answer 1

Рассматривали ли вы вариант алгоритма Луна? Luhn используется для генерации контрольной цифры для строк чисел во многих приложениях, включая номера счетов кредитных карт. Это часть стандарта ISO-7812-1 для генерации идентификаторов. Он поймает любое число, введенное с одной неверной цифрой, что означает, что любые два действительных числа отличаются минимум двумя цифрами.

Проверьте алгоритм :: LUHN в CPAN для реализации perl.

Answer 2

Не извлекайте существующие коды, просто сгенерируйте потенциальный новый код и посмотрите, есть ли какие-либо конфликтующие в базе данных:

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

Answer 3

Поместите числа от 0 до 9 999 999 в расширенном бинарном дереве поиска.Дополнением является отслеживание количества подузлов слева и справа.Например, когда ваш алгоритм начинается, верхний узел должен иметь значение 5 000 000, и он должен знать, что он имеет 5 000 000 узлов слева и 4 999 999 узлов справа.Теперь создайте хеш-таблицу.Для каждого значения, которое вы уже использовали, удалите его узел из расширенного дерева двоичного поиска и добавьте значение в хеш-таблицу.Обязательно поддерживайте расширение.

Чтобы получить одно значение, выполните следующие действия.

1. Используйте верхний узел, чтобы определить, сколько узлов осталось в дереве.Допустим, у вас осталось n узлов.Выберите случайное число от 0 до n.Используя дополнение, вы можете найти n-й узел в своем дереве за время log (n).
2. Как только вы нашли этот узел, вычислите все значения, которые сделали бы значение на этом узле недействительным.Допустим, ваш узел имеет значение 1,111,111.Если у вас уже есть 2,111,111 или 3,111,111 или ... тогда вы не можете использовать 1,111,111.Так как есть 8 других опций на цифру и 7 цифр, вам нужно только проверить 56 возможных значений.Проверьте, есть ли какое-либо из этих значений в вашей хеш-таблице.Если вы еще не использовали ни одно из этих значений, вы можете использовать свой случайный узел.Если вы использовали какой-либо из них, вы не можете.
3. Удалить свой узел из дополненного дерева.Убедитесь, что вы поддерживаете расширенную информацию.
4. Если вы не можете использовать это значение, вернитесь к шагу 1.
5. Если вы можете использовать это значение, у вас есть новый случайный код.Добавьте его в хеш-таблицу.

Теперь проверка наличия доступного значения занимает время O (1) вместо времени O (n).Кроме того, поиск другого доступного случайного значения для проверки занимает время O (log n) вместо ... ах ... Я не уверен, как проанализировать ваш алгоритм.

Короче говоря, если вы начинаете сПоцарапав и воспользовавшись этим алгоритмом, вы сгенерируете полный список допустимых кодов в O (n log n).Поскольку n равно 10 000 000, это займет несколько секунд или что-то в этом роде.

Я все тут подсчитал?Дайте мне знать, если это не подтвердится или мне нужно что-то уточнить.

Answer 4

Используйте хеш.

После генерации успешного кода (не конфликтующего с каким-либо существующим кодом), но этот код в хеш-таблице, а также вставки в хеш-код 63 других кодов, которые различаются ровно на одну цифру.

Чтобы узнать, не конфликтует ли случайно сгенерированный код с существующим кодом, просто проверьте, существует ли этот код в хэше.

Answer 5

Howabout:

Генерация 6-значного кода путем автоинкрементации предыдущего.Сгенерируйте 1-значный код, увеличив предыдущий мод 10. Объедините два.

Presto, гарантированно отличаясь двумя цифрами.: D

(Да, немного шутливо. Я предполагаю, что необходим «случайный» или, по крайней мере, квазислучайный. В этом случае генерируйте случайный ключ из 6 цифр, повторяйте, пока он не станет дубликатом (т.е. сделать столбец уникальным, повторять до тех пор, пока вставка не нарушит ограничение), а затем сгенерировать контрольную цифру, как кто-то уже сказал.)