сличение номера

[Mayor]

имеется таблица диапазонов def вида:

ЗАО "РП Технологии"    Республика Удмуртия    950     с 8100000
по 8399999    26.02.2006
ЗАО "РП Технологии"    Республика Удмуртия    904    с 2450000
по 2499999    02.11.2005
ЗАО "РП Технологии"    Республика Удмуртия    904    с 2750000
по 2799999    02.11.2005

размером от 31 кб

требуется по быстрому определить принадлежность номеров к таблице
* 79042451234 - будет относится ко 2й строке верхнего примера

какой алгоритм быстрее будет реализовать?
какой алгоритм будет быстрее работать?

по идее думал над:
950     с 8100000
по 8399999
1 => 9508100000,9508399999 c последующим тупым перебором массива $num>= $def[0] && $num <=$def[1]
2 => 95081,95082,95083 c последующим RXLовским сравнением типа substr($_, 0, length($prefix)) eq $prefix
3 => 95081,95082,95083 с созданием асоциативного списка и поиском if defined $def{$a} , где $a в цикле от substr($_,1,6) До substr($_,1,4)

[Finch]

Тут напрашиваются маски. Диапазон можно представить ввиде маски например с 8100000 и до 8399999. Маска 81, 82, 83. Их можно считать хешами диапазонов. Потом только твое число под хеш проверять.

[RXL]

Ассоциативный массив быстрее за счет индексной таблицы и реализации алгоритма на C. Другой вопрос,  что ключ или совпадает или нет, а вхождение не проверяется.
Значит в твоем случае будет лучше 2-й вариант.

[Mayor]

че то сроки стали слегка поджимать

так что попробую первый вариант - его быстрее всего написать, потом когда будет свободное время сравню производительность с RXLловским методом и через асоциативные списки

пока что в тестовом наборе получилось 355 диапазонов номеров ( найдена 1 опечатка в мобильных телесистемах по св области ) и порядка 5-6 метров звонков

по идее расчетное время работы алгоритма должно уложиться в 15 минут на моем компе, хм если время\данные выростут до нескольких часов, придется модернизировать алгоритм или переходить на С

[RXL]

Mayor1, а можно оптимизировать. В свое время я писал программу, которая разбирала логи АТС. Я написал более двух сотен шаблонов. Чтобы не потерять производительность, я применил индексирование по первому символу сообщения. Это раз в 10-20 повысило скорость, т.к. мне не надо перебирать все RE, а только небольшой набор, объединенный в группу по первому символу.
В твоем случае можно сделать нечто похожее (чисто на вскидку): хеш по первым N (наверное 3-м) символам, в хеше - еше хеш, где ключи - остальные цифры префикса, а значения - что-то, что идентифицирует оператора (или кого тебе надо).

Кстати, упомянутая программа была написана на C с библиотекой pcre. На perl писать проще...

[Mayor]

Mayor1, а можно оптимизировать. В свое время я писал программу, которая разбирала логи АТС. Я написал более двух сотен шаблонов. Чтобы не потерять производительность, я применил индексирование по первому символу сообщения. Это раз в 10-20 повысило скорость, т.к. мне не надо перебирать все RE, а только небольшой набор, объединенный в группу по первому символу.
В твоем случае можно сделать нечто похожее (чисто на вскидку): хеш по первым N (наверное 3-м) символам, в хеше - еше хеш, где ключи - остальные цифры префикса, а значения - что-то, что идентифицирует оператора (или кого тебе надо).

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

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

я в принципе предпочел реализовать $num>= $def[0] && $num <=$def[1], из-за простоты реализации + как бонус пошла простата проверки кодов def, неправильно оценил сложность алгоритма: на 5 метрах он выполнился за несколько секунд

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

что можете посоветовать из oss субд, с поддержкой доступа к апи из перла, наличием поддержки перла в качестве языка хранимых процедур?

какие щас ваще популярны субд? ( что бы было кому задавать по ним вопросы)

[Sla]

Mayor1, а какие ты СУБД знаешь?

зы. Какие требования по быстродействию обработки логов, и чем чревата медленная обработка?

[RXL]

Mayor1, тяжно порой тебя читать.

Давай не будем коверкать слова?
1. Хеш - мужского рода и мягкий знак ему не положен.
2. Массив - простое и понятное слово. Не надо "арреев".
3. Префикс - принятый в телефонии термин, означающий начало номера. "маска диапазона" - это не понятно.

Еще бы грамматику подтянуть - вообще замечательно было бы. ж)

Не стоит сравнивать телефонные номера как числа - это строки.

Perl через интерфейс DBI поддерживает многие СУБД, как свободные, так и коммерческие. Нужен только драйвер - модуль BDB для данной СУБД. Вызов процедуры делается через SQL - "поддержка вызова" не нужна.

какие щас ваще популярны субд?

Абстрактный вопрос... Разные!
Все зависит от требований к СУБД, планируемого объема данных, режима работы, толщины кошелька и прочих параметров. В том числе и от пристрастий разработчика.

Что такое "oss"?

[Mayor]

Mayor1, а какие ты СУБД знаешь?

практически сейчас никакие
работал давно с MySQL MSSQL,
формальные представления о возможностях Oracle FireBird PostgreSQL SQLite

зы. Какие требования по быстродействию обработки логов, и чем чревата медленная обработка?

уложиться за 15мин - 6 часов
грозит тем что буду искать другой алгоритм пока обрабатывается текущий

Mayor1, тяжно порой тебя читать.
Давай не будем коверкать слова?
1. Хеш - мужского рода и мягкий знак ему не положен.
2. Массив - простое и понятное слово. Не надо "арреев".
3. Префикс - принятый в телефонии термин, означающий начало номера. "маска диапазона" - это не понятно.
Еще бы грамматику подтянуть - вообще замечательно было бы. ж)

о сорри
1 русский особо не учил, настрою какую нить хрень на фаерфоксе
по 2му это у меня от английского издания Programming Perl 2nd Ed, никак не могу отвязатся
3 нада будет запомнить

Не стоит сравнивать телефонные номера как числа - это строки.

когда как числа некоторые алгоритмы лучше срабатывают, лишь бы ведущих 0 не было

какие щас ваще популярны субд?

Абстрактный вопрос... Разные!
Все зависит от требований к СУБД, планируемого объема данных, режима работы, толщины кошелька и прочих параметров. В том числе и от пристрастий разработчика.

халявная документация, халявное распространение

ну если конкретно, то пожалуй:
 кто, сколько, с какой субд, проработал и чем был мотивирован ее выбор?

Что такое "oss"?

Open Source Software


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

в плане хешей побеседовал с математиком, теоретически оказалось их использование не выгодным, самое эффективное простой бинарный поиск в отсортированном массиве - обгонит и перекрестный запрос к 2м таблицам субд и поиск через ассоциативный массив, единственная проблемма то что если часть номер представляет собой строку ( начинается с 0 ) с этим возникнут неопределенные трудности

[Finch]

уложиться за 15мин - 6 часов
грозит тем что буду искать другой алгоритм пока обрабатывается текущий

Какой примерно объём данных для обработки? Есть ли возможность распаралелить работу на несколько компов. Т.е создать кластер вычислений.

Могу дать мною написанный и применяемый класс на С++, для быстрого поиска ключевых слов. Класс работает на алгоритме дерева поиска.

[Mayor]

Какой примерно объём данных для обработки? Есть ли возможность распаралелить работу на несколько компов. Т.е создать кластер вычислений.
Могу дать мною написанный и применяемый класс на С++, для быстрого поиска ключевых слов. Класс работает на алгоритме дерева поиска.

спс но пока не актуально, я поначалу боялся, что из-за незнания архитектуры перла алгоритм выйдет за временные рамки, но после беседы с знакомым математиком, модифицированый алгоритм обрабатывает 5 метров менее чем за 10 сек, агрегатные запросы тоже его особо не нагружают, учитывая максимально объем логов с которым сталкивался  100 метров, я думаю на одном перле управиться

зы конечно мк, говорил что на С\С++ с самописным аллокатором памяти данную задачу можно заставить работать под 100 метров в секунду ... наверное если из хардов рейд создать ... но мне пока такие навороты еще рановаты