Быстрое регулярное выражение, которое проверяет количество раз символ, появляется на строке в Vim?

Ваш regex подвержен столкновению с некоторым O (N^2) поведение “отслеживания в обратном порядке” regex механизм, используемый в Vim (и много других языков и сред).

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

/^\([^|]*|\)\{8}.*$

В целом Вы не должны соответствовать “восемь или больше”, с тех пор если Вы уже знаете, что строка проблематична, если она имеет восемь (имеет ли она больше или не).

Если на самом деле необходимо соответствовать всей строке (например, потому что это - часть a :s операция), затем необходимо будет сохранить последнюю часть (.*$); если Вы просто используете regex для нахождения эти “восемь или больше” строки, то можно уехать .*$ от конца.

Кроме того, я советую только пытаться соответствовать одной “стороне” канала в группе это, что Вы повторяетесь. Это упрощает и думающий о том, как regex соответствует строкам, и как сам regex механизм выполняется (он устраняет источник отслеживания в обратном порядке).

Теперь, для объяснения бита об “отслеживании в обратном порядке”. Полагайте, что у Вас есть строка, которая действительно имеет восемь символов вертикальной черты на нем:

aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh

Следующий отрывок описывает, как regex механизм пытается соответствовать Вашему выражению против вышеупомянутой строки (я добавил дополнительный пробел к regex строкам для показа (приблизительно), где части regex соответствуют символам самой строки).

Первое .* является жадным и будет соответствовать всему в конец строки, оставляя символ вертикальной черты unmatchable.

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                                            |

Новое “стягиваемое” соответствие бросает биты своего соответствия и пробует остальную часть regex снова. Это происходит один символ за один раз в этом случае (так как . будет соответствовать любому отдельному символу). Эти доходы отслеживания в обратном порядке до остальной части выражения могут соответствовать (или пока это не отслеживает в обратном порядке к началу — который является единственным способом, которым это знает, что строка не соответствует выражению!).

  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
^(.*                                |.*)(.*|.*)(.*|.*)(.*|.*    )(.*|

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

В моем выражении, каждом повторении ([^|]*) никогда соответствия что-либо, что следующий элемент (|) соответствовал бы, таким образом, отслеживание в обратном порядке чисто линейно. После того как отслеживание в обратном порядке запускается для каждого “стягиваемого” соответствия, оно будет (в линейное время), находят, что нет никаких более ранних мест, где следующее выражение может соответствовать; это вынуждает отслеживание в обратном порядке продолжить предыдущее “стягиваемое” соответствие, пока ничто не соответствует, и целая строка решена для несоответствования.

Вместо “нуля или большего количества неканала, затем передайте по каналу” ([^|]*|), также возможно использовать . с явно нежадным повторением (\{-} в Vim, но это варьируется; другое regex использование языков *?).

^\(.\{-}|\)\{8}.*$