Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Вебмастеру (http://forum.oszone.net/forumdisplay.php?f=22)
-   -   Сервис коротких урлов, каков алгоритм? (http://forum.oszone.net/showthread.php?t=145119)

Igor_I 14-07-2009 17:16 1167506
Сервис коротких урлов, каков алгоритм?
 
Есть ведь такие сервисы, самый известный - tinyurl.com. Мне вот интересно, как реализуется алгоритм по нахождению уникального слова. Ведь чем больше слов, тем дольше искать. Если в базе миллион слов, то придётся сравнивать каждое новое слово с уже используемыми. Или может сразу генерируется вся база слов, а потом просто делается связь слова со ссылкой. Правда база изначально будет вмещать несколько миллионов записей. Вот как лучше сделать?

Coutty 14-07-2009 17:42 1167534
По-моему tinyurl.com никак не подбирает уникальное слово, а просто строит рандомную комбинацию из 6 символов.
1. Создать рандомную комбинацию букв латинского алфавита или использовать специальную хэш-функцию над url'ом.
2. Проверить наличие такой в базе.
3. В случае коллизии или п.1, или изменить один символ на следующий. В случае перехода на п.1 возможен очень долгий цикл, во втором случае - возникновение "кучи" и потери ценности хэш-системы. Но так ли это? Какова вероятность коллизии?

Если брать только латинский алфавит, то 26 в степени 6 = 308 млн. с хвостиком.
Если добавить к латиннице ещё и цифры, то уже 2,1 млрд. комбинаций. Думаю, этот сервис не настолько популярен, чтобы в нём часто возникали коллизии.

Igor_I 14-07-2009 20:29 1167700
Да 1 пункт мало волнует, как именно создать комбинацию из 6 символов.
Вот 2 пункт, проверка, вот в чём загвоздка. Ведь 308 млн. это общее количество уникальных комбинаций, реально коллизи начнутся меньше чем через миллион комбинация. Я проверял :) Правда давно и результаты не помню. Проверял разницу между просто rand и функцией по созданию случайной строки при использовании rand. Создал таблицу с уникальным полем и писал туда слова. Больше миллиона слов не было. И функция выиграла. Насчёт вероятности коллизий - это всё-таки математика, я в ней не силён.
Насчёт популярности, это у нас не популярно, а у них весьма, тот же твиттер преобразовывал все ссылки через tinyurl.com.

Coutty 14-07-2009 22:13 1167785
Второй пункт зависит исключительно от первого.
Хотел сейчас проверить вероятности коллизий, да после создания 16384 строк всё повисает (даже если маленькими порциями по 10000 записей добавлять). Наверное я что-то делаю не так...

И всё-таки при 36-символьном алфавите (буквы+цифры) вероятность коллизии в пределах первых десяти миллионов записей ничтожно мала. Даже если и будет - сгенерировать просто другую запись. Сколько коллизий подряд выпадет в первой сотне миллионов? Вряд ли даже 10 штук. Другой вопрос - а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк? :)

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

Sham 14-07-2009 22:43 1167795
Цитата:
Цитата Coutty
а справится ли СУБД с обработкой таблицы на 100 (или даже 10) млн. строк? »
возникает задача выбора самого субд по критерию производительности в работе с большими объемами, но в конечном счете все упирается в железо...

Igor_I 15-07-2009 01:41 1167887
Сделал базу и таблицу с 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

Sham 15-07-2009 03:15 1167911
имхо рандом тут неудачное решение... лучше реализовать последовательное изменение автонабора символов (a, b, ..., aa, ab,..., aaa, aab,...., aaaaaa, aaaaab, aaaaac.... и тд). Последнюю сгенерированную строку хранить в другом месте, чтобы на основании ее сделать следующий набор (последняя строка мб введена юзером - при наличии фичи, как на tinyurl).

Igor_I 15-07-2009 20:51 1168712
Sham, вариант интересный, до такого не додумался :) Насчёт фичи надо будет подумать. Скорее всего она не нужна.

Coutty 15-07-2009 21:10 1168723
Я думаю, что на том же tinyurl.com специально не стали использовать последовательную выдачу. Почему - другой вопрос.

Sham 15-07-2009 22:30 1168790
Цитата:
Цитата Coutty
на том же tinyurl.com специально не стали использовать последовательную выдачу »
Рандомная генерация при большом количестве записей теоретически может привести к неограниченному зацикливанию проверок имеющихся записей (генерация строки -> проверка по базе -> уже есть -> назад).... т.е. имхо генерация дб логическая, а способ - дело хозяйское...

Igor_I 15-07-2009 23:44 1168851
Цитата:
Цитата Sham
Рандомная генерация при большом количестве записей теоретически может привести к неограниченному зацикливанию проверок имеющихся записей (генерация строки -> проверка по базе -> уже есть -> назад) »
Вот именно. Поэтому я и задумался. А может там нагенерировали всю базу, под 2 миллиарда слов, а потом просто пишут урлы к словам?
Генерация должна быть логической, ну а как это будет?
Рандомное слово - нелогически
Изменение одной буквы - логически, но как то по простому :)
Взять по одной букве со слова в урле - но как это уместить в 6 букв и что-то не могу придумать логику.
Хэш брать от строки, так он как минимум 32 символный.
Больше ничего придумать не могу.

Sham 16-07-2009 13:46 1169383
Цитата:
Цитата Igor_I
зменение одной буквы - логически, но как то по простому »
а если кодировать числа (будет типа текстовое представление столбца AUTO_INCREMENT)? В Mysql есть ENCRYPT, но надо смотреть.... в конце концов можно брать рандомный срез символов от uniqid или другого хеша, и ограничить кол-во проверок совпадений (допустим 10)... а если будет больше 10, выводить типа "извини, сегодня не твой день" :)

Igor_I 21-07-2009 22:49 1174071
Что-то не могу сообразить как реализовать увеличение буквы на следующую.
Может использование goto поможет, пока тему отодвинул.

BASSON_XVI 23-07-2009 02:27 1175197
Цитата:
Цитата Igor_I
Что-то не могу сообразить как реализовать увеличение буквы на следующую. »
Может у глупость говорю :). Может можно букву представить в виде числа (char) затем в зависимости от кодировки прибавить нужное число и опять изменить представление на строку/символ?

Sham 23-07-2009 03:18 1175209
проще сделать массив, и рулить индексами....

Igor_I 23-07-2009 08:21 1175264
BASSON_XVI, ну почему глупость, так и есть. Но я не знаю как изменять вторую букву, если с первой дошли до z.
Sham, массив чего?

BASSON_XVI 23-07-2009 12:13 1175446
Ну наверно если на первой дошли до z надо её менять на начальную букву алфавита то есть а и перебирать вторую :) дошли до конца второй поменяли первую букву на b и опять вторую перебирать :).. Правда это как то ппц мудрено слишком :)

BASSON_XVI 23-07-2009 17:04 1175729
PHP код:
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:

Sham 23-07-2009 17:18 1175746
Цитата:
Цитата Igor_I
массив чего? »
в смысле
PHP код:
$sym = array(1=>'a', 2='b', 3=>'c'); 
строку (набор предыдущих сгенерированных символов) разбиваем str_split в массив побуквенно, буквы преобразуем в числа по индексам $sym, и делаем инкремент последнего числа в массиве... там нюансы, но чисто арифметические... в конце преобразуем к первоначальному виду и делаем implode...

Цитата:
Цитата BASSON_XVI
SELECT COUNT(id) FROM links WHERE hash = '$randHash'" »
COUNT вроде бы работает только с GROUP BY
впервые вижу объявление функций внутри функции...

dmitryst 23-07-2009 17:50 1175783
А если нагенерить эти самые рандомные УРЛ-ы (неважно, как), поместить в таблицу, сопоставить каждому порядковый номер. Зашел клиент - получил по порядковому номеру рандомную строку. Запись можно потом удалить, дабы не использовать повторно. Если одна таблица закончится, к этому времени сгенерируется другая ))). Плюс в простоте выборки,
Цитата:
Цитата Sham
типа "извини, сегодня не твой день" »
не будет, т.к. всё уже сгенерировано и проверено.

BASSON_XVI 23-07-2009 17:53 1175784
Цитата:
Цитата Sham
COUNT вроде бы работает только с GROUP BY »
У меня COUNT так работает в Кузнецове(правда там много неточностей :)) так и еще где читал.
Цитата:
Цитата Sham
впервые вижу объявление функций внутри функции... »
Ну я рад за вас! :) Знайте тоже прекрасно работает:)

Sham 23-07-2009 18:40 1175836
Цитата:
Цитата Sham
COUNT вроде бы работает только с GROUP BY »
Цитата:
Вызов групповых функций для SQL-команд, не содержащих GROUP BY, эквивалентен выполнению этих функций над всем набором возвращаемых данных.
еще как работает :)
Цитата:
Цитата BASSON_XVI
Знайте тоже прекрасно работает »
главное, чтобы было осмысленно... а смысла я не вижу (

Igor_I 23-07-2009 21:47 1175994
А у меня такая функция для случайной строки.
PHP код:
function func_randomstring($length=8, $lower=1, $upper=1, $number=1)
    {
            $a = '';
            if ($lower==1)  $a .= "abcdefghijklmnopqrstuvwxyz";
            if ($upper==1)  $a .= "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
            if ($number==1) $a .= "1234567890";
            $randstr = null;
            for($i = 0; $i < $length; $i ++)
            {
                    $randstr .= substr($a, rand(0, (strlen($a)-1)), 1);
            }

            return $randstr;
    } 
BASSON_XVI, а где вставка результата в базу? Кстати, наверно стоит сделать индекс по полю hash?
Проверял свою функцию или от балды написал?

BASSON_XVI 23-07-2009 23:34 1176054
Igor_I, да от балды написал.... Просто хотел сказать что можно генерить хеш скажем в 6 символов, проверять его по базе если есть такой то рандомно выберать какую букву поменять и менять её рандомно и заново проверять :). Как то так. :(

Igor_I 24-07-2009 18:44 1176806
Я так и делал. Вставлял 2 миллиона записей, первые 200 тысяч записались за 24 секунды, последние - за 96 секунд. Но я не делал индексов. Может с ними получше будет.


Время: 10:42.

Время: 10:42.
© OSzone.net 2001-