Генерация 100% уникальных кодов

В наш век рекламы и продвижения товаров я думаю каждая рекламная компания хоть раз сталкивалась с задачей генерации уникальных кодов в огромных размерах… ну например 50 миллионов уникальных кодов состоящих из цифр и латинского алфавита без учета регистра. Решений в интернете, так скажем, не много… программы платные, причем сомнительного качества – судя по отзывам или по внешнему виду сайта, и ручаться за 100% уникальность не видя исходников я бы не стал. А проверить уникальность постфактум не представляется возможным. А уж какой может получиться скандал, если во время проведения акции будут дубли… никому это не надо.

Решения которые предлагаются на различных форумах тоже оставляют желать лучшего. Как например совет использовать базу данных для проверки на уникальность с помощью индекса на тестовом поле с флажком – уникальный. Вот попробывали бы они использовать такой метод при генерации 50 милионов записей, я бы посмотрел сколько лет они будут ждать результата. Также присутствовали “обнадеживающие” ответы типа “вот тебе функция генерации GUID, он длинный, так что очень малый шанс что будут дубли” не радуют. Нам не нужно длинный, и не нужен GUID, и уж точно нужен уникальный.

Хотел бы предложить мой вариант генерации кодов, который может гарантировать хорошую скорость генерации (500.000 уникальных кодов за меньше чем 2 секунды), которая не будет зависить от количества уже сгенерированных элементов с одной стороны, а с другой неоспоримую уникальность сгенерированных кодов. Огромную скорость мы получаем из-за отказа от поиска на предмет дублей. Искать дубли среди десятков миллионов кодов не простая штука я вам скажу. Тут без бинарного дерева не обойтись. Казалось бы – вот оно решение – поднимаем в памяти бинарное дерево, и генерируем себе коды – 100% уникальность. Правда есть одна проблема... оперативная память, которая не резиновая. При организации бинарного дерева придется хранить ссылку на вышестоящий символ, плюс к этому добавляет уровень вложенности – в нашем случае это номер символа в строке. А это все избытки, которые на больших объемах данных вырастают в гигабайты.

Ну я думаю хватит информации для затравки, приступим к делу:

Версия на Perl

#!/usr/bin/perl -w
$dict = '1234567890qwertyuipasdfghjklzxcvbnm';
$totalLength = 500000;
$codeLength = 12;
$dictLength = length($dict) - 1;

%codes = ();
while (keys(%codes) < $totalLength){
  $res = '';
  for ($i = 0; $i < $codeLength; $i++){
    $res .= substr($dict,rand($dictLength), 1);
  }
  $codes{$res} = undef;
}

Версия на PHP

$dict = '1234567890qwertyuipasdfghjklzxcvbnm';
$totalLength = 500000;
$codeLength = 12;
$dictLength = strlen($dict) - 1;

$codes   = array();
while (count($codes) <$totalLength){
  $res = '';
  for ($n = 0; $n < $codeLength; $n++){
    $res .= $dict[mt_rand(0, $dictLength)];
  }
  $codes[$res] = null;
}

Ну вот собственно и все, хэш codes наполнен 500000 элементами, код выполняется ~ 1 секунды на core i5.

Ключевые моменты: $dict – это словарь доступных символов, $totalLength – это кол-во генерируемых кодов, $codeLength – это длина кода.
While используется вместо for потому что при генерации могут возникать дубли, а нам же важно не кол-во проходов, а количество конечных элементов.

По желанию можно добавить различные условия и проверки, например вхождение одного символа не более 3-х раз в коде, или запретить подряд идущие символы и тд. При генерации более 20 милионов кодов рекомендую запускать на perl x64 версии, и с 4 гигабайтами на борту, т.к. из-за свопа генерация может растянуться на сутки.