Производительность Java regex - PullRequest
Новая
       33

Производительность Java regex

3 голосов
/ 12 октября 2010

Я пытаюсь разобрать ссылки с регулярным выражением с Java.

Но я думаю, что это слишком медленно. Например, чтобы извлечь все ссылки из:

... это тратит 34642 миллисекунды (34 секунды !!!)

Вот регулярное выражение: 

private final String regexp = "<a.*?\\shref\\s*=\\s*([\\\"\\']*)(.*?)([\\\"\\'\\s].*?>|>)";

Флаги для рисунка: 

private static final int flags = Pattern.CASE_INSENSITIVE | Pattern.DOTALL |Pattern.MULTILINE | Pattern.UNICODE_CASE | Pattern.CANON_EQ;

И код может быть примерно таким: 

private void processURL(URL url){
    URLConnection connection;
    Pattern pattern = Pattern.compile(regexp, flags);
    try {
        connection = url.openConnection();
        InputStream in = connection.getInputStream();
        BufferedReader bf = new BufferedReader(new InputStreamReader(in));
        String html = new String();
        String line = bf.readLine();            
        while(line!=null){
            html += line;
            line = bf.readLine();
        }
        bf.close();
        Matcher matcher = pattern.matcher(html);
        while (matcher.find()) {
            System.out.println(matcher.group(2));
        }
     } catch (Exception e){
     }
 }

Можете ли вы дать мне подсказку?

Дополнительные данные:
1Мбит
Core 2 Duo
1 ГБ ОЗУ
Однопоточная

Ответы [ 4 ]

14 голосов
/ 12 октября 2010

Подсказка: не используйте регулярные выражения для извлечения ссылок или других задач «разбора» HTML!

В вашем регулярном выражении 6 (SIX) повторяющихся групп.Выполнение этого повлечет за собой много отступлений.В худшем случае он может даже приблизиться к O(N^6), где N - количество вводимых символов.Вы можете немного ослабить это, заменив нетерпеливое сопоставление ленивым сопоставлением, но избежать патологических случаев практически невозможно;например, когда входные данные достаточно искажены, чтобы регулярное выражение не соответствовало.

Гораздо лучшим решением будет использование какого-либо существующего строгого или разрешающего анализатора HTML.Даже написание специального синтаксического анализатора вручную будет лучше, чем использование грубых регулярных выражений.

Эта страница , в которой перечислены различные парсеры HTML для Java.Я слышал хорошие новости о TagSoup и HtmlCleaner.

3 голосов
/ 05 июня 2012

Я написал простой тест для сравнения производительности 10 миллионов операций RegExp с String.indexof() со следующим результатом : 

0.447 seconds
6.174 seconds
13.812080536912752 times regexp longer.

import java.util.regex.Pattern;

public class TestRegExpSpeed {
    public static void main(String[] args) {
        String match = "FeedUserMain_231_Holiday_Feed_MakePresent-1_";
        String unMatch = "FeedUserMain_231_Holiday_Feed_Make2Present-1_";

        long start = System.currentTimeMillis();
        for (int i = 0; i <= 10000000; i++) {
            if (i % 2 == 0) {
                match.indexOf("MakePresent");
            } else {
                unMatch.indexOf("MakePresent");
            }
        }

        double indexOf = (System.currentTimeMillis() - start) / 1000.;
        System.out.println(indexOf + " seconds");

        start = System.currentTimeMillis();
        Pattern compile = Pattern.compile(".*?MakePresent.*?");
        for (int i = 0; i <= 10000000; i++) {
            if (i % 2 == 0) {
                compile.matcher(match).matches();
            } else {
                compile.matcher(unMatch).matches();
            }
        }
        double reaexp = (System.currentTimeMillis() - start) / 1000.;
        System.out.println(reaexp + " seconds");

        System.out.println(reaexp / indexOf + " times regexp longer. ");
    }
}
3 голосов
/ 12 октября 2010

Все ваше время, все из них тратится здесь: 

 html+=line;

Используйте StringBuffer.Еще лучше, если вы можете, запустить матч на каждой строке и не накапливать их вообще.

3 голосов
/ 12 октября 2010

Попробуйте Прогулка . Пожалуйста, не используйте регулярные выражения для этого.

Использование регулярных выражений и злоупотребление регулярными выражениями

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

Источник

...