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

Question

Я хочу извлечь строки с конкретными шаблонами в большой файл Python. Я пытался открыть файл в ваннах и извлечь строки с помощью регулярных выражений. Поскольку файл настолько большой, для меня важна производительность. Итак, я управлял следующими шаблонами:

import re
start = time.time()

s = re.findall('1167331\t\d{4,}', file)

middle = time.time()

s2 = re.findall('\d{4,}\t1167331', file)

end = time.time()
print(end - middle, middle - start)

Результаты:

87.53701615333557 1.5457119941711426

В чем причина разницы? и как я могу решить это? Я думаю, что регулярное выражение идет от начала паттерна до конца, поэтому первый паттерн будет быстрее. Как утверждается в документации:

Возвращать все непересекающиеся совпадения шаблона в строке в виде списка строк. Строка сканируется слева направо, и совпадения возвращаются в указанном порядке.

Если это правильно, есть ли способ придумать это? Можно ли заставить регулярное выражение совпадать справа налево? Ответ в этом посте говорит о том, что есть в .NET. Часть моих данных:

file[:200]

'1000061\t11172522\n1000211\t1084791\n1000211\t1087381\n1000211\t1113071\n1000211\t1167331\n1000211\t5997662\n1000211\t7006722\n1000211\t7763732\n1000211\t13075162\n1000211\t13550632\n1000211\t14367563\n1000211\t14373036\n100'

Answer 1

Ваше регулярное выражение ведет себя так, потому что \d{4,} может соответствовать МНОГИМ различных комбинаций, а если число после \t недопустимо, , оно должно проверить их все . Предположим, у нас есть:

1000211\t875349678\t1000211

Если \d{4} стоит первым, а число после \t не 1167331, он должен проверить 1000211\t, 000211\t, 00211\t, 0211\t, прежде чем он определит, что число после \t недопустимо. Представьте, если бы ваши номера были длиннее - нужно было бы проверить еще больше контента, прежде чем переходить к следующему! Что еще хуже, если число после \t равно почти допустимо, оно также проверит все эти символы, и потребуется еще больше времени для запуска.

Если 1167331 будет первым, ононужно только проверить 10, прежде чем он выйдет из строя и перейдет к следующему номеру.

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