скорость Regex в 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.

Для более полного объяснения этого, особенно, как заставить его работать с Unicode, см. this answer.

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 +» медленнее, чем компиляция других шаблонов, которые вы могли бы проверить, используя здесь предварительно скомпилированную идиому, хотя это не похоже на меня как на объяснение.

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