* Считается, что регулярные выражения, о которых писал статью ANDLL, -- это самый быстрый способ разбора строки. Вполне может быть, что так оно и есть; но это означало бы только, что остальные способы ещё медленнее, а не то, что регулярные выражения работают быстро. Собственно, о времени работы регулярных выражений речь и пойдёт.
Если регулярное выражение -- действительно регулярное, т.е. описывает регулярный язык, то по такому выражению можно построить ДКА, который будет работать линейное время по длине строки. И всё же возможности тех "регулярных выражений", которые поддерживаются современными инструментами, не ограничиваются лишь регулярными языками. Так, man-страница grep(1) заканчивается секцией BUGS следующего содержания:
Large repetition counts in the {m,n} construct may cause grep to use
lots of memory. In addition, certain other obscure regular expressions
require exponential time and space, and may cause grep to run out of
memory.
Backreferences are very slow, and may require exponential time.
Другими словами, использование ссылок назад сразу же выводит алгоритм из линейного времени работы в неполиномиальное. То, насколько это плохо -- неполиномиальное время работы, можно проиллюстрировать следующим примером:
- Код: Выделить всё
bash-2.05b$ time perl -e '$_="123454895:4890182361"; /((\d+)|\:|\2)*(\1|\2)$/'
real 1m32.795s
user 1m31.482s
sys 0m0.079s
Входная строка случайная; от конкретных символов время работы не зависит. Важно только то, что для входной строки из 20 символов этот 22-символьный регэксп работает полторы минуты, и добавление нового символа во входную строку увеличивает время работы примерно втрое.
Можно, однако наращивать не длину входной строки, а количество ссылок назад в регэкспе:
- Код: Выделить всё
bash-2.05b$ time perl -e '$_="123454895:4890182361"; /((\d+)|\:|\2)*(\1|\2)+\3/'
real 1m44.623s
user 1m44.078s
sys 0m0.095s
На той же 20-символьной строке получаем лишние 13 секунд работы; рост втрое при добавлении символа сохраняется.
Здесь по задумке должен был идти вывод о проделанной работе; может быть, я его ещё сочиню и допишу сюда.
* Не знаю как остальных, но нас с начальной школы и до сих пор учителя пугают неимоверным количеством времён в английском языке, насчитывая всякий раз не по одному десятку.
Поэтому естественно, что я не мог не обратить внимания на этот топик. По нему выходит, что времён всего два: прошедшее и непрошедшее. Тогда, кроме времён, формы глагола разделяются по "аспектам" (по-русски это, наверное, виды) и залогам. И действительно, сразу же получается ясная и многомерная картина форм английского глагола, вместо этого жуткого списка всех "времён" вперемешку, занимавшего в учебнике целую страницу.
Кроме этого факта, в привлекшем моё внимание топике описывается "давнопрошедшее" время ([url=http://ru.wikipedia.org/wiki/Плюсквамперфект]плюсквамперфект[/url]), сохранившееся по словам автора в южнорусских говорах. Если носители этих говоров читают мой блог, прошу их оставить комментарии по этому поводу
* Теперь, наконец, про нравы. О вреде злоупотребления алкоголем написано и нарисовано очень много, но интересно сравнить эти два схожих по своему сюжету плаката -- советский и китайский. Вот один из комментариев в их отношении:
GSerg писал(а):А плакаты в целом одинаковы, ведь у нас одна рюмка и одно маленькое "нет", а там две бутылки и куча текста - пропорции соблюдены
+Молния: СГУ и АлтГТУ респект!!
