Ваше регулярное выражение склонно сталкиваться с некоторым O (N ^ 2) поведением движка регулярных выражений «backtracking», используемого в Vim (и многих других языках и средах).
К счастью, есть способы написать эквивалентные выражения, которые не вызывают чрезмерного возврата. Например:
/^\([^|]*|\)\.*$
Как правило, вам не нужно сопоставлять «восемь или более», поскольку, если вы уже знаете, строка является проблематичной, если у нее восемь (независимо от того, имеет она больше или нет).
Если вам действительно нужно сопоставить всю строку (например, потому что она является частью :s
операции), то вам нужно будет оставить последнюю часть ( .*$
); если вы просто используете регулярное выражение, чтобы найти «восемь или более» строк, то вы можете оставить .*$
конец.
Кроме того, я советую только пытаться сопоставить одну «сторону» трубы внутри группы, которую вы повторяете. Это упрощает как размышления о том, как регулярное выражение сопоставляет строки, так и о том, как выполняется сам механизм регулярного выражения (это устраняет источник обратного отслеживания).
Теперь, чтобы объяснить немного о «возврате». Предположим, у вас есть строка с восемью символами канала:
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh
Следующий отрывок описывает, как механизм регулярных выражений пытается сопоставить ваше выражение с вышеуказанной строкой (я добавил дополнительный пробел к строкам регулярного выражения, чтобы показать (приблизительно), где части регулярного выражения соответствуют символам самой строки).
Первый .*
является жадным и будет соответствовать всему концу строки, оставляя непропорциональный символ канала.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |
Самое последнее «сжатое» совпадение отбрасывает биты своего совпадения и снова пытается выполнить остальное регулярное выражение. Это происходит по одному символу за раз в этом случае (так как .
будет соответствовать любому отдельному символу). Этот возврат продолжается до тех пор, пока не совпадет остальная часть выражения (или пока он не вернется к началу - это единственный способ узнать, что строка не соответствует выражению!).
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|
Таким образом, первый .*
отступил достаточно, чтобы позволить остальным групповым матчам, но не было ничего для второй группы, чтобы соответствовать. Пора отступить еще немного.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|
Отступление нашло новую точку «остановки», но теперь второй .*
в первой группе делает жадное сопоставление. Вторая группа не соответствует. Откат второго .*
в первой группе начинается.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.* )(.*|
Вторая группа нашла совпадение, но третья группа не совпала. Снова вернитесь назад, начиная с более позднего матча. Второй .*
из второй группы отступает, чтобы вернуться ни к чему. Первая .*
из второй группы отступает ни к чему. Второй .*
из первой группы отступает ни к чему. Первый .*
из первой группы возвращается успешно.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|
Но опять же, вторая .*
жадная, поэтому она не оставляет ничего для второй группы.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.*)(.*|.* )(.*|
В конце концов, все три группы совпадают, но четвертый экземпляр группы дает сбой. Начните возвращаться.
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.* )(.*|.*)(.*|.* )(.*| aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff| gg | gg |hhhhhh ^(.* |.*)(.*|.*)(.*|.*)(.*|.* )(.*|
Вы можете видеть, как это сжигает много времени (на диаграммах даже пропускается обратный отбор за символом, который на самом деле происходит; только «высокие точки» показаны выше). Проблема возникает из-за того, что более ранний фрагмент регулярного выражения жадно сопоставляется с чем-то, что в конечном итоге должна будет соответствовать более поздняя часть регулярного выражения, чтобы получить правильное количество повторений группы.
В моем выражении каждый repetition ( [^|]*
) никогда не совпадает ни с чем, что бы соответствовал следующему элементу ( |
), поэтому обратное отслеживание является чисто линейным. Как только обратное отслеживание начинается для каждого «сжатого» совпадения, оно (в линейное время) обнаружит, что не существует более ранних мест, где может соответствовать следующее выражение; это вынуждает вернуться к предыдущему «усадочному» совпадению, пока ничто не совпадет, и вся линия не будет решена как несоответствующая.
Вместо «ноль или более не труба, а труба» ( [^|]*|
) также можно использовать .
с явно не жадным повторением ( \{-}
в Vim, но оно варьируется; другие языки регулярного выражения используют *?
).
^\(.\{-}|\)\.*$