про Reg Expression вопрос

[bella]

Добрый день,
Попалась я похоже, тупо using Regular Expression. Если кто-нибудь сталкивался с проблемой или знает/прдполагает какое-то решение, то отзовитесь, пожалуйста.
У меня проблема с performance при использовании Reg Expr. Речь идеть о java, но проблема не в языке, а в моем алгоритме поиска, точнее, отсутствии такового.
У меня есть hashmap of 700+ пар ( word -> translation), и есть набор файлов (порядка 180-200) по 2000-3500 строк кода в каждом. Мне надо было быстренько найти words по заданным в Reg Expr rules и заменить их на translations во всех случаях, за исключением случаев, когда word попадает под Exclude Rules. Excluded Rules тоже заданы как Reg Expression.
Я не специалист в области Reg Expr или в области быстрого поиска. Это была одноразовая задача и я тупо перебираю по одной строчки фаилов и по одному подставляю words from hashmap to Reg Expr. pattern.
Все работает, но время не лезет ни в какие ворота. С увеличением количества строк и размера hashmap время растет по экспоненте.
Посоветуйте, please, какой мне использовать алгоритм поиска, что почитать по этому поводу.
Если есть какая-то ссылка на какой-нибудь пример, то это вообще было бы замечательно. Мне не нужно писать home made Reg Expr, я буду по-прежнему использовать java build-in reg expression, но сам search надо как-то менять.

Спасибо.

[Marmot]

Навскиду, попробуйте засунуь в hashmap не слова, а скомпилрованные regexps, это раз.
Во вторых, зачитайте *весь* файл в один больший String и работайте с ним.
От этого уже станет быстрее...

Ну и в третьих, я бы подумал над возможность генерации одно большого regexpа, сразу делающего то, что надо, не уверен правда, насколько это будет лучше...

[Весенняя]

Да, точно, стоит закешировать pattern-ы и сделать по одному matcher-у на файл. Объединять regexp-ы лучше не стоит -- на длинных текстах выражения с перебором вариантов медленнее могут работать, чем отдельные по очереди.
Вот тут про оптимизацию можно глянуть: http://www.javaworld.com/javaworld/jw-0 ... regex.html

[bella]

Спасибо.
Засунуть в HashMap не пары ( word -> translation), а пары ( Pattern.compile(Reg. Expression(word)) -> translation) - это идея. Только видимо в это случае придется несколько HashMap-s держать, т.к. у меня еще есть набор excluded patterns.
Все мои Reg. Expr., excluded and valid, содержат (word) kak parameter.
Рассматривать фаил не по строкам,а как один buffer, я попробовала сначала, но отказалась от этого дела, т.к. собрать все свои valid+excluded reg. expressions в один у меня не получилось и я просто запуталась, прикладывая сначала excluded, a потом valid patterns, и не похоже было, чтобы перформанс улучшилась в разы, т.к. я по-прежнему перебираю весь набор пар, хранящихся в HashMap проходя через весь файл.
A результат, как обычно, надо было выдать сразу и чтобы все работало. Поэтому я и вернулась обратно рассматривать файлы по lines, а не как buffer.
Но замедление перформанс конечно, с увеличением количества файлов + увеличением количества пар в HashMap растет по ехпоненте. Апликация stand-alone i работает, поэтому пока терпит, но конечно такое безобразие надо переделать.
Мне вот тут еще посоветовали по-прежнему рассматривать строки, но разбить каждую строку на слова, а потом рассмотреть каждый (word) на наличие в HashMap ( myHashMap.isЕxist(word)). И уже если word (or words) is valid, то только тогда и проверять current line, прогоняя последовательно все (Excluded Reg. Expr(word-s)) + если надо все (valid Reg. Expr(word-s)) содержащие только эти valid words в качестве параметра. Тогда мне не надо будет перебирать все 700+ пар, которые находятся в HashMap.
Kak вам такой алгоритм, покритикуйте, пожалуста. По идее должно быть быстрее, за счет уменьшения количества вариантов Reg. Expression(valid word-s) ???
Спасибо.

[Marmot]

Спасибо.
Заунуть в HashMap не пары ( word -> translation), а пары ( Pattern.compile(Reg. Expression(word)) -> translation) - это идея. Только видимо в это случае придется несколько HashMap-s держать, т.к. у меня еще есть набор excluded patterns.

Ну и что? Какая в этом проблема-то?

Рассматривать фаил не по строкам,а как один buffer, я попробовала сначала, но отказалась от этого дела, т.к. собрать все свои valid+excluded reg. expressions в один у меня не получилось и я просто запуталась, прикладывая сначала excluded, a потом valid patterns, и не похоже было, чтобы перформанс улучшилась в разы, т.к. я по-прежнему перебираю весь набор пар, хранящихся в HashMap проходя через весь файл. A результат, как обычно, надо было выдать сразу и чтобы все работало. Поэтому я и вернулась обратно рассматривать файлы по lines, а не как buffer.

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

Но замедление перформанс конечно, с увеличением количества файлов + увеличением количества пар в HashMap растет по ехпоненте. Апликация stand-alone i работает, поэтому пока терпит, но конечно такое безобразие надо переделать.
Мне вот тут еще посоветовали по-прежнему рассматривать строки, но разбить каждую строку на слова, а потом рассмотреть каждый (word) на наличие в HashMap ( myHashMap.isЕxist(word)). И уже если word (or words) is valid, то только тогда и проверять current line, прогоняя последовательно все (Excluded Reg. Expr(word-s)) + если надо все (valid Reg. Expr(word-s)) содержащие только эти valid words в качестве параметра. Тогда мне не надо будет перебирать все 700+ пар, которые находятся в HashMap.
Kak вам такой алгоритм, покритикуйте, пожалуста. По идее должно быть быстрее, за счет уменьшения количества вариантов Reg. Expression(valid word-s) ???
Спасибо.

Ну это все зависит от ваших regexp-ов, если они таковы, что ваши слова там должны присутсвовать целиком и как отдельные слова, тогда это может помочь, вы же нам не написали какого типа regexp-ы вы используете...
Хотя, компилировать и кешить паттерны все равно не помешает... Ну и использование "коротких" строк в этом случае будет оправданным.

PS В догонку, а какие у вас все-таки regexp-ы, может они вам на самом деле и не нужны?

[CdR]

- хранить скомпилированые regexp -- сам бог велел, тут без вариантов. (то же для excluded). Чтобы не делать эту работу при каждом запуске -- я бы оформил "демона", который держит актуальные правила подстановки в памяти. (trivial)
- закачать в память весь файл сразу (буферизация потоков рулит, но на тут пограничный вариант, так что может помочь)
- разбивка по words - rulez, но при увеличении потока исходных данных может вдруг стать задержкой, так что стоит этот параметр мониториить.

Распараллеливать нитками с хранимыми в виде shared самыми hasрmaps -- это тоже тривиальная идея.
Дальше моя фантазия упирается в анализ собственно предметной области и возможных regexp-ов.

PS: А вот когда regex'овстанет по-настоящему много, то не придётся ли решать обратную задачу (эффективного хранения и использования самих regexp?)

[bella]

Ну это все зависит от ваших regexp-ов, если они таковы, что ваши слова там должны присутсвовать целиком и как отдельные слова, тогда это может помочь, вы же нам не написали какого типа regexp-ы вы используете...
Хотя, компилировать и кешить паттерны все равно не помешает... Ну и использование "коротких" строк в этом случае будет оправданным.

PS В догонку, а какие у вас все-таки regexp-ы, может они вам на самом деле и не нужны?

Совершенно точно, word (в тексте далее "original"), присутствует в составе Reg Expr в виде отдельного слова
Написать одно Reg Expr подходящее для всего и чтобы при этом все работало, у меня не получилось

HashMap<String, String> состоит из пар <original, replacement>. Пока 700+ пар, будет больше. Заполняется 1 раз вначале. Количество файлов пока 140-150, будет больше. Размер фаилов: 2000-3000 строк.
"originals" бывают 3 типов, в зависимости от типа "exclude" and "match" rules are different.
"originals" 1 типа не имеют exclude rules
Exclude rules для 2 и 3 типа:
excludePatterns.add("(mx|flash)\\." +"(([A-z]+\\.)?)" + original + "\\.");
excludePatterns.add("mx:" + original + "[>\\s*]");
excludePatterns.add("\"\\s*- " +"((\\/|-|\\,|\\s|[A-z])+)?" + original+ "((\\/|-|\\,|\\s|[A-z])+)?" +
"(100%)?\\.<BR>");

"match" rules for the "originals" of the types 1 and 2:
"([\\.\"\\s*])" + original +"([\\.\"\\s*])"
"match" rules for the "originals" of 3d type:
"([\\.\\(\\)\\[\\}\\{\"! :=<\\s*]|</)"+original+"([\\.\\(\\)\\{\\}\\[,;\"=:\\s*]|$)"
"replace" rules для всех одинаковы (пока)
"$1" + replace + "$2"

[bella]

- хранить скомпилированые regexp -- сам бог велел, тут без вариантов. (то же для excluded). Чтобы не делать эту работу при каждом запуске -- я бы оформил "демона", который держит актуальные правила подстановки в памяти. (trivial)
- закачать в память весь файл сразу (буферизация потоков рулит, но на тут пограничный вариант, так что может помочь)
- разбивка по words - rulez, но при увеличении потока исходных данных может вдруг стать задержкой, так что стоит этот параметр мониториить.

Распараллеливать нитками с хранимыми в виде shared самыми hasрmaps -- это тоже тривиальная идея.
Дальше моя фантазия упирается в анализ собственно предметной области и возможных regexp-ов.

PS: А вот когда regex'овстанет по-настоящему много, то не придётся ли решать обратную задачу (эффективного хранения и использования самих regexp?)

Как я уже писала, апликация stand alone, not embedded. На мое предложение написать thread pool mechanism и таким образом улучшить перформанс, начальство сказало категорическое "НЕТ".
По-правде говоря (погружаясь в даааааавние воспоминания) я когда-то делала банчмарк for Solaris W/S, с 2 процессорами. Задача заключалась в том, что надо было прочитать несколько довольно больших фаилов ( не помню размер) в память и в памяти надо было обработать много таблиц. Попробовали улучшить перформанс, разбив на подзадачи и назначив thread для каждой подзадачи. Бенчмарк я делала на строгом С, posix threads library, назначив принудительно thread-y его процессор-Id. Результат был плачевный, улучшение перформанс порядка на 15%.
Что в настоящее время с современными языками (based on virtual machine) benchmarks показывают, если строить thread-pool mechanism, на какой порядок это может улучшить перформанс?

[bella]

дубль

[Stanislav]

Ну это все зависит от ваших regexp-ов, если они таковы, что ваши слова там должны присутсвовать целиком и как отдельные слова, тогда это может помочь, вы же нам не написали какого типа regexp-ы вы используете...
Хотя, компилировать и кешить паттерны все равно не помешает... Ну и использование "коротких" строк в этом случае будет оправданным.

PS В догонку, а какие у вас все-таки regexp-ы, может они вам на самом деле и не нужны?

Совершенно точно, word (в тексте далее "original"), присутствует в составе Reg Expr в виде отдельного слова
Написать одно Reg Expr подходящее для всего и чтобы при этом все работало, у меня не получилось

HashMap<String, String> состоит из пар <original, replacement>. Пока 700+ пар, будет больше. Заполняется 1 раз вначале. Количество файлов пока 140-150, будет больше. Размер фаилов: 2000-3000 строк.
"originals" бывают 3 типов, в зависимости от типа "exclude" and "match" rules are different.
"originals" 1 типа не имеют exclude rules
Exclude rules для 2 и 3 типа:
excludePatterns.add("(mx|flash)\\." +"(([A-z]+\\.)?)" + original + "\\.");
excludePatterns.add("mx:" + original + "[>\\s*]");
excludePatterns.add("\"\\s*- " +"((\\/|-|\\,|\\s|[A-z])+)?" + original+ "((\\/|-|\\,|\\s|[A-z])+)?" +
"(100%)?\\.<BR>");

"match" rules for the "originals" of the types 1 and 2:
"([\\.\"\\s*])" + original +"([\\.\"\\s*])"
"match" rules for the "originals" of 3d type:
"([\\.\\(\\)\\[\\}\\{\"! :=<\\s*]|</)"+original+"([\\.\\(\\)\\{\\}\\[,;\"=:\\s*]|$)"
"replace" rules для всех одинаковы (пока)
"$1" + replace + "$2"

ИМХО Я бы перевернул все вверх ногами: зачитал бы файл в память, шинковал бы его токенайзером по словам и искал в БД (слово, перевод), которую отсортировал под бинарный поиск. 700 пар - это менее 10 шагов поиска на каждое слово и даже при драматическом увеличении БД поиск не будет намного дольше.

[Весенняя]

Беру обратно свои слова про объединение regexp-ов, что их не стоит объединять

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

В общем, как-то так должно побыстрее работать в урощенном виде (без учета исключений для примера):
1) Нужен Map строк original -> replacement (то, что у вас и есть).
2) Сделать 1 regexp из каждого шаблона замены, подставив в него варианты возможных слов через "или".
3) Подправить сам regexp, чтобы побыстрее работал и чтобы не прихватывал и не запоминал соседний текст (non capturing lookehead/lookbehind вместо обычных capturing групп по бокам regexp-а, и /s* вроде можно просто на /s заменить в вашем случае).
4) Замены делать с помощью appendReplacement и appendTail.

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

        Map<String, String> replacements = new HashMap<String, String>();
        replacements.put("cat", "kitten");
        replacements.put("dog", "puppy");
        replacements.put("rat", "baby rat");
        
        Pattern p = Pattern.compile("(?<=[\\.\"\\s])(cat|dog|rat)(?=[\\.\"\\s])");
        Matcher m = p.matcher(bigText);
        StringBuffer sb = new StringBuffer();

        while (m.find()) {
            String replacement = replacements.get(m.group());
            if (replacement == null) {
                //do smth real in real app
                replacement = m.group(); // or just leave the original value
            }
            m.appendReplacement(sb, replacement);
        }
        m.appendTail(sb);