Показать полную графическую версию : Сервис коротких урлов, каков алгоритм?
Есть ведь такие сервисы, самый известный - tinyurl.com. Мне вот интересно, как реализуется алгоритм по нахождению уникального слова. Ведь чем больше слов, тем дольше искать. Если в базе миллион слов, то придётся сравнивать каждое новое слово с уже используемыми. Или может сразу генерируется вся база слов, а потом просто делается связь слова со ссылкой. Правда база изначально будет вмещать несколько миллионов записей. Вот как лучше сделать?
По-моему tinyurl.com никак не подбирает уникальное слово, а просто строит рандомную комбинацию из 6 символов.
1. Создать рандомную комбинацию букв латинского алфавита или использовать специальную хэш-функцию над url'ом.
2. Проверить наличие такой в базе.
3. В случае коллизии или п.1, или изменить один символ на следующий. В случае перехода на п.1 возможен очень долгий цикл, во втором случае - возникновение "кучи" и потери ценности хэш-системы. Но так ли это? Какова вероятность коллизии?
Если брать только латинский алфавит, то 26 в степени 6 = 308 млн. с хвостиком.
Если добавить к латиннице ещё и цифры, то уже 2,1 млрд. комбинаций. Думаю, этот сервис не настолько популярен, чтобы в нём часто возникали коллизии.
Да 1 пункт мало волнует, как именно создать комбинацию из 6 символов.
Вот 2 пункт, проверка, вот в чём загвоздка. Ведь 308 млн. это общее количество уникальных комбинаций, реально коллизи начнутся меньше чем через миллион комбинация. Я проверял :) Правда давно и результаты не помню. Проверял разницу между просто rand и функцией по созданию случайной строки при использовании rand. Создал таблицу с уникальным полем и писал туда слова. Больше миллиона слов не было. И функция выиграла. Насчёт вероятности коллизий - это всё-таки математика, я в ней не силён.
Насчёт популярности, это у нас не популярно, а у них весьма, тот же твиттер преобразовывал все ссылки через tinyurl.com.
Второй пункт зависит исключительно от первого.
Хотел сейчас проверить вероятности коллизий, да после создания 16384 строк всё повисает (даже если маленькими порциями по 10000 записей добавлять). Наверное я что-то делаю не так...
И всё-таки при 36-символьном алфавите (буквы+цифры) вероятность коллизии в пределах первых десяти миллионов записей ничтожно мала. Даже если и будет - сгенерировать просто другую запись. Сколько коллизий подряд выпадет в первой сотне миллионов? Вряд ли даже 10 штук. Другой вопрос - а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк? :)
Ещё можно записывать дату последнего обращения. Если потом попадается такая же случайная комбинация, то проверять - нет обращений 3-6 месяцев - записываем поверх новую ссылку.
а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк? »
возникает задача выбора самого субд по критерию производительности в работе с большими объемами, но в конечном счете все упирается в железо...
Сделал базу и таблицу с 2 полями, первое поле уникальное. Слово состоит из 6 символов. Вставленно 1.999.048 записи.
Видно, что после 1 миллиона записей время увеличивается.
Здесь 2 миллиона циклов.
На вставку 200000 записей уходит по
10% = 24.054500818253
20% = 26.072400093079
30% = 27.169686079025
40% = 27.423403024673
50% = 27.355036973953
60% = 35.397845029831
70% = 47.092970848083
80% = 62.26985001564
90% = 81.317250967026
100% = 96.546401023865
Общее время = 454.699381
memory_get_usage = 82456
memory_get_peak_usage = 107236
То есть получается пропущенно 952 цикла, выходит на 2 миллиона вариантов - 952 коллизии.
Здесь один миллион циклов.
На вставку 100000 записей уходит по
10% = 12.130727052689
20% = 13.389132976532
30% = 12.968748092651
40% = 12.946455955505
50% = 14.068972110748
60% = 13.874950885773
70% = 14.403827905655
80% = 14.447467088699
90% = 14.580943107605
100% = 15.551143884659
Вставленно записей = 999779
Общее время = 138.36254
memory_get_usage = 84204
memory_get_peak_usage = 107616
имхо рандом тут неудачное решение... лучше реализовать последовательное изменение автонабора символов (a, b, ..., aa, ab,..., aaa, aab,...., aaaaaa, aaaaab, aaaaac.... и тд). Последнюю сгенерированную строку хранить в другом месте, чтобы на основании ее сделать следующий набор (последняя строка мб введена юзером - при наличии фичи, как на tinyurl).
Sham, вариант интересный, до такого не додумался :) Насчёт фичи надо будет подумать. Скорее всего она не нужна.
Я думаю, что на том же tinyurl.com специально не стали использовать последовательную выдачу. Почему - другой вопрос.
на том же tinyurl.com специально не стали использовать последовательную выдачу »
Рандомная генерация при большом количестве записей теоретически может привести к неограниченному зацикливанию проверок имеющихся записей (генерация строки -> проверка по базе -> уже есть -> назад).... т.е. имхо генерация дб логическая, а способ - дело хозяйское...
Рандомная генерация при большом количестве записей теоретически может привести к неограниченному зацикливанию проверок имеющихся записей (генерация строки -> проверка по базе -> уже есть -> назад) »
Вот именно. Поэтому я и задумался. А может там нагенерировали всю базу, под 2 миллиарда слов, а потом просто пишут урлы к словам?
Генерация должна быть логической, ну а как это будет?
Рандомное слово - нелогически
Изменение одной буквы - логически, но как то по простому :)
Взять по одной букве со слова в урле - но как это уместить в 6 букв и что-то не могу придумать логику.
Хэш брать от строки, так он как минимум 32 символный.
Больше ничего придумать не могу.
зменение одной буквы - логически, но как то по простому »
а если кодировать числа (будет типа текстовое представление столбца AUTO_INCREMENT)? В Mysql есть ENCRYPT, но надо смотреть.... в конце концов можно брать рандомный срез символов от uniqid или другого хеша, и ограничить кол-во проверок совпадений (допустим 10)... а если будет больше 10, выводить типа "извини, сегодня не твой день" :)
Что-то не могу сообразить как реализовать увеличение буквы на следующую.
Может использование goto поможет, пока тему отодвинул.
BASSON_XVI
23-07-2009, 02:27
Что-то не могу сообразить как реализовать увеличение буквы на следующую. »
Может у глупость говорю :). Может можно букву представить в виде числа (char) затем в зависимости от кодировки прибавить нужное число и опять изменить представление на строку/символ?
проще сделать массив, и рулить индексами....
BASSON_XVI, ну почему глупость, так и есть. Но я не знаю как изменять вторую букву, если с первой дошли до z.
Sham, массив чего?
BASSON_XVI
23-07-2009, 12:13
Ну наверно если на первой дошли до z надо её менять на начальную букву алфавита то есть а и перебирать вторую :) дошли до конца второй поменяли первую букву на b и опять вторую перебирать :).. Правда это как то ппц мудрено слишком :)
BASSON_XVI
23-07-2009, 17:04
FUNCTION getHash($cs)
{
FUNCTION random_generate($cs){
$n="1234567890abcdefghjklmnopqrstuvwxyz";
for($i=0;$i<$cs;$i++){
$rb=rand(0,35);
$rand.=$n[$rb];
}
return $rand;
}
FUNCTION check($randHash,$cs)
{
$sql = "SELECT COUNT(id) FROM links WHERE hash = '$randHash'";
$data = mysql_query($sql);
$res = mysql_result($data,0,0);
if($res>0)
{
$rb = rand(0,$cs);
$rs = random_generate(1);
$randHash[$rb]=$rs;
check($randHash);
}
else
{
RETURN $randHash;
}
}
$randHash = random_generate($cs);
RETURN check($randHash,$cs);
}
Как то так не подойдет? :unsure:
массив чего? »
в смысле $sym = array(1=>'a', 2='b', 3=>'c');
строку (набор предыдущих сгенерированных символов) разбиваем str_split в массив побуквенно, буквы преобразуем в числа по индексам $sym, и делаем инкремент последнего числа в массиве... там нюансы, но чисто арифметические... в конце преобразуем к первоначальному виду и делаем implode...
SELECT COUNT(id) FROM links WHERE hash = '$randHash'" »
COUNT вроде бы работает только с GROUP BY
впервые вижу объявление функций внутри функции...
dmitryst
23-07-2009, 17:50
А если нагенерить эти самые рандомные УРЛ-ы (неважно, как), поместить в таблицу, сопоставить каждому порядковый номер. Зашел клиент - получил по порядковому номеру рандомную строку. Запись можно потом удалить, дабы не использовать повторно. Если одна таблица закончится, к этому времени сгенерируется другая ))). Плюс в простоте выборки, типа "извини, сегодня не твой день" » не будет, т.к. всё уже сгенерировано и проверено.
© OSzone.net 2001-2012
vBulletin v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.