Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Модератор: Модераторы разделов

borov
Сообщения: 17
ОС: Ubuntu 7.10

Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение borov »

У меня есть список урлов в базе, каждый раз прочитывая лог файл необходимо смотреть нет ли среди урлов одного из тех что находится в базе.

Получаю список урлов из базы, загоняю в массив где ключ - урл, значение - его id.
Есть два типа проверки, точное совпадение или поиск с помощью регулярного выражения, то есть любой урл типа *.google.com должен быть найден.

Когда список урлов в базе был небольшим, все работало быстро, но после того как число улов превысило 7000, начались тормоза, на проверку 15 доменных имен уходит 3 секунды. Это очень медленно. Т.к. в логе, в одной строчке два разных урла, и оба их надо сравнивать со списком из базы, строчек очень много итд...

Вот функция

Код: Выделить всё


<?php
   function domain_from_urls($domain, $urls, $check_type = "extended") {
         if ($check_type == "exact") {
              if (in_array($domain, array_keys($urls))) {
                   return $urls[$domain];
              }
         }

        if ($check_type == "extended") {
            foreach($urls as $key => $value) {
                $regex = "/^[a-zA-Z0-9\-\.]+\.($key)$/";
                preg_match($regex, $domain, $matches);
                if ($key == $domain) {
                    return $urls[$key];
                }
                if (count($matches)) {
                    if ($key == $matches[1]) {
                        return $urls[$key];
                    }
                }
            }
        }

         return false;
    }


посоветуйте как можно улучить, мне все равно на каком языке, perl,python, может даже осилю c или java :)
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5456
ОС: Gentoo

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение /dev/random »

Хм... Может, держать второй массив, в котором будут храниться не сами URL'ы, а извлеченные из них доменные имена? И сравнивать безо всяких регулярных выражений, тем способом, который использован в ($check_type == "exact"), только не со списком целых URL'ов, а со списком извлеченных из них доменных имен?
Спасибо сказали:
Аватара пользователя
Folderx
Сообщения: 296
ОС: fedora, mandriva

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение Folderx »

(borov) писал(а):Т.к. в логе, в одной строчке два разных урла, и оба их надо сравнивать со списком из базы, строчек очень много итд...


*.google.com надо искать там где все .com

Отсортируй базу получишь первый адрес .com, с него начинаешь поиск по шаблону до первого адреса .ru
Спасибо сказали:
Serik
Сообщения: 149
ОС: SuSE Linux

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение Serik »

Обработанные значения опять идут в БД ? Если да, то имеет смысл делать это в ХП. Загрузить все данные во временную таблицу, построить нужные индексы и т.д. Или построчно передавать ХП, которая будет их добавлять в таблицу. Современные СУБД (я имею в виду PostgreSQL :) хорошо работают со строками и с большими массивами строк.

Если данные нужны в программе, имеет смысл перейти на С++/STL. У меня в std::map более 20k записей, ключ по строке, 99% строк длиннее 64 символов. Полный обход по ключу, т.е. из сырых данных вытаскивается строка и ищется в std::map, всех 20k записей идет ~3 сек на мощном железе. Но ищется точное соответствие, регулярные выражения я не использую.

Так же имеет смысл, как уже было сказано выше, до поиска разделить url на части: протокол, хост (может даже домены), путь к файлу, параметры.
Спасибо сказали:
borov
Сообщения: 17
ОС: Ubuntu 7.10

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение borov »

/dev/random писал(а):
05.12.2007 21:24
Хм... Может, держать второй массив, в котором будут храниться не сами URL'ы, а извлеченные из них доменные имена? И сравнивать безо всяких регулярных выражений, тем способом, который использован в ($check_type == "exact"), только не со списком целых URL'ов, а со списком извлеченных из них доменных имен?

Извините что всех запутал.
Действительно в базе только доменные имена.

Для примера экспортировал в CSV:

"id","name"
1,"00nff.info"
2,"01q-09.info"
3,"02d07ftfie2.info"
4,"086orfqz.info"
5,"0dgpm63e.info"
6,"0fazrvp0x7x.info"
7,"0g3nf.info"
8,"0oh0fzbshy.info"
9,"0t9nry5b5cjw.info"
10,"0wdg2ytaz94y.info"


База MySQL, в самом начале прохождения скрипта, все эти домены грузятся в массив и держатся в памяти. Дальше начинается чтение лог файлов, в логе есть url и referer. От них отрезается http:// и все что после / таким образом остается одно доменное имя. Собственно ради чего тут используются регулярные выражения, так по той причине что домен может быть google.com, www.google.com, video.google.com. Точное совпадение будет использоваться в дальнейшем и таких доменов будет очень мало, то есть как правило будут использоваться только домены которые могут быть какого угодно уровня.


Folderx писал(а):
06.12.2007 02:03
(borov) писал(а):Т.к. в логе, в одной строчке два разных урла, и оба их надо сравнивать со списком из базы, строчек очень много итд...


*.google.com надо искать там где все .com

Отсортируй базу получишь первый адрес .com, с него начинаешь поиск по шаблону до первого адреса .ru
базу (ну или массив в данном случае) сортировать нет смысла имхо, т.к. в строчке лога может встретиться домен который находится в начале массива, следующий домен из лога будет из конца массива, следующий из середины итд...


Serik писал(а):
06.12.2007 09:21
Обработанные значения опять идут в БД ? Если да, то имеет смысл делать это в ХП. Загрузить все данные во временную таблицу, построить нужные индексы и т.д. Или построчно передавать ХП, которая будет их добавлять в таблицу. Современные СУБД (я имею в виду PostgreSQL :) хорошо работают со строками и с большими массивами строк.

Если данные нужны в программе, имеет смысл перейти на С++/STL. У меня в std::map более 20k записей, ключ по строке, 99% строк длиннее 64 символов. Полный обход по ключу, т.е. из сырых данных вытаскивается строка и ищется в std::map, всех 20k записей идет ~3 сек на мощном железе. Но ищется точное соответствие, регулярные выражения я не использую.

Так же имеет смысл, как уже было сказано выше, до поиска разделить url на части: протокол, хост (может даже домены), путь к файлу, параметры.
Ну в конце все это сохраняется в виде репорта то есть там то, встретился такой урл (домен). Что такое ХР :)? Точные соответсвия у меня тоже быстро работали :(
Спасибо сказали:
Serik
Сообщения: 149
ОС: SuSE Linux

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение Serik »

borov писал(а):
06.12.2007 13:41
Что такое ХР :)?
Хранимая процедура
Я не понял, почему не точное соответствие ? Вытаскивайте домен 1 и 2 уровня, и диапазон поиска сразу уменьшится до десятка вариантов.
Спасибо сказали:
borov
Сообщения: 17
ОС: Ubuntu 7.10

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение borov »

вначале я хотел сделать примерно так, брать из базы домены, разделив их по уровню 2, 3-го итд., потом читаем лог, из строчки лога берем урл, отбрасываем http:// и все после /, потом начинаем отсекать куски от доменного имени, то есть

http://video.google.com/dslfj?id=Jjdfs
превращается в video.google.com, смотрим в массиве точное совпадение по video.google.com, если не совпало, отбрасываем video., начинаем искать google.com если такое найдено, все ок. начальнег сказал шо это все хрень, и делать надо с регулярным выражением итд, я переделал в то что показал в первом посту темы, пока урлов в базе было мало - все летало.

есть ли в таком алгоритме какие то уязвимости, то есть возможно ли что попадутся какие то не те урлы (домены)? имхо таки вроде все правильно, может к нему вернуться опять
Спасибо сказали:
borov
Сообщения: 17
ОС: Ubuntu 7.10

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение borov »

в общем сделал так как написал постом выше:

Код: Выделить всё

    function domain_from_urls($domain, $urls, $check_type = "extended") {
         if ($check_type == "exact") {
              if (in_array($domain, array_keys($urls))) {
                   return $urls[$domain];
              }
         }
         if ($check_type == "extended") {
            if (isset($urls[$domain])) {
                return $urls[$domain];
            }
            while (preg_match('/^[a-zA-Z0-9\-]+\.(.*)$/', $domain, $matches)) {
                $domain = $matches[1];
                if (isset($urls[$domain])) {
                    return $urls[$domain];
                }
            }
        }
        return false;
    }


работает очень быстро. раньше один урл проверялся где-то полсекунды, теперь 1000 урлов примерно за 1-2 секунды
Спасибо сказали:
Аватара пользователя
КВН
Сообщения: 242
Статус: Новичок

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение КВН »

Т.к. автор использует БД для хранения адресов, то и поиск лучше было бы возложить на сервер БД. Результат скорости выполнения был бы гораздо выше, учитывая рост количества адресов. И программирование в этом случае свелось к правильному проектированию базы данных и построению sql-запросов. Конечно же, если целью не было само программирование.
Спасибо сказали:
Аватара пользователя
Folderx
Сообщения: 296
ОС: fedora, mandriva

Re: Медленный поиск по массиву с регулярным выраженим, посоветуйте как ускорить

Сообщение Folderx »

(borov) писал(а):превращается в video.google.com, смотрим в массиве точное совпадение по video.google.com, если не совпало, отбрасываем video.,

Сначала отделяешь .com, потом этот .com ищешь в массиве, начиная с него ищешь video.google.com или google.com

(borov) писал(а):базу (ну или массив в данном случае) сортировать нет смысла имхо, т.к. в строчке лога может встретиться домен который находится в начале массива, следующий домен из лога будет из конца массива, следующий из середины итд...

Как раз отсортировав массив свой, ты будешь каждый раз проходить не по всему списку, а по его отдельной части, которая занимает времени меньше, чем весь список.

И даже ссылки вида 0wdg2ytaz94y.info явно показывают, что домен первого уровня чаще встречается, чем домен второго.
Спасибо сказали: