Скорость регулярных выражений в Java

Question

Некоторые примеры времени настенных часов для большого количества строк:

.split("[^a-zA-Z]"); // .44 seconds
.split("[^a-zA-Z]+"); // .47 seconds
.split("\\b+"); // 2 seconds

Есть какие-нибудь объяснения резкого увеличения?Я могу представить шаблон [^ a-zA-Z], выполняемый в процессоре, как набор из четырех операций сравнения, все четыре из которых выполняются, только если это истинный случай.Что насчет \ b?Кому-нибудь есть что взвесить за это?

Answer 1

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

Во-вторых, никогда не используйте \b в Java: оно испорчено и не синхронизировано с \w.

Более полное объяснение этого, особенно о том, как заставить его работать с Юникодом, см. в этом ответе .

Answer 2

\b - утверждение нулевой ширины, которое принципиально отличается от [^A-Za-z].Поскольку \b реализовано как if / then (см. Комментарий tchrist ниже), вероятно, будет больше работы, чтобы проверить это для каждой буквы в каждой строке.Кроме того, плюс вызывает откат, который умножает эту стоимость.

Кроме того, когда вы разбиваете границы слов, вы будете сопоставлять больше мест, чем если бы вы просто делили на [^a-zA-Z]+.Это приведет к выделению большего количества строк, что также займет больше времени.Чтобы увидеть это, попробуйте эту программу:

import java.lang.String;

class RegexDemo {
    private static void testSplit(String msg, String re) {
        String[] pieces = "the quick brown fox".split(re);
        System.out.println(msg);
        for (String s : pieces) {
            System.out.println(s);
        }
        System.out.println("----");
    }

    public static void main(String args[]) {
        testSplit("boundary:", "\\b+");
        testSplit("not alpha:", "[^A-Za-z]+");
    }
}

Возможно, не связано, когда вы используете String.split (), регулярное выражение должно быть скомпилировано для каждого использования.Если вы предварительно скомпилируете регулярное выражение в виде шаблона, например,

Pattern boundary = Pattern.compile("\\b+");

, а затем разделите его с помощью boundary.split(testString), вы сэкономите на стоимости компиляции регулярного выражения для каждой тестовой строки.Таким образом, возможно, компиляция «\ b +» медленнее, чем компиляция других шаблонов, которые вы можете проверить, используя здесь предварительно скомпилированную идиому, хотя это вряд ли мне объяснит.

Для получения дополнительной информации о производительности регулярных выражений прочитайте эти статьи Расса Кокса http://swtch.com/~rsc/regexp/ и ознакомьтесь с http://www.regular -expressions.info / тоже.