Изучаем алгоритм работы регулярных выражений в Ruby

[@Renius]

Так я не понял, синтаксическое дерево это хорошо? Если плохо, то я готов возразить, что для любого алгоритма можно найти случай, в котором он будет работать плохо. Тем более когда используется алгоритм Томпсона, который можно легко зациклить.
Напротив, AST имеет большой плюс: его производительность предсказуема, т.о. мы всегда можем знать на перед какие задачи нужно решать инфраструктурно :)

[@stdfox]

Я не уверен, что автор статьи озабочен непосредственно AST, скорее он выражает некое недовольство тем, что используется не самый эффективный в плане скорости алгоритм. Его мнение целиком и полностью основано на статьях Russ Cox, в которых очень хорошо описано, почему зависимость скорости выполнения такая, а не другая. Скажем так, его претензии скорее сводятся к использованию стека отката, в котором, безусловно, может находится огромное количество не ведущих к цели путей нахождения результата.

Ну и график к первой статье Russ Cox, конечно же, производит некоторое впечатление.

[@Renius]

Это важный график, поскольку камни теперь полетят в большинство интепретируемых языков, нежели только в руби.

[@zed_0xff]

на дворе уже даже Ruby 2.1, а они все еще 1.8 тестируют…

[@stdfox]

Это график из статьи Russ Cox, датируемой 2007 годом, поэтому на нем немного устаревшие версии программ.
Ruby с версии 2.0 использует форк Onigmo, в который добавлены некоторые улучшения (но, по-сути, это та же Oniguruma).

[@amarao]

Не колесница, а повозка любого типа. И oni — не дьявол. Чёрт — может быть, но не из христианско-диалектической мифологии.

[@stdfox]

Вполне вероятно, что так. Но автор оригинала пользовался англоязычной статьей википедии, где в качестве перевода используется «Devil's Chariot», что на русский язык все-таки более правильно переводить как «Колесница Дьявола».

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

[@bubuq]

Чтобы вы не искали, какой бы текст не разбирали...

Это уж совсем как-то за гранью.

Чтобы вы не искали, мы нашли это за вас.
Что бы вы ни искали, вы это не найдёте.

[@stdfox]

Оу! Как это прошло мимо меня.
Большое спасибо! Поправил.

[@akzhan]

Тут надо отметить, что Russ Cox потом предложил и движок RE2 для решения «правильно».

И учитывая, что Google выпустил для Chrome Irregexp, стало интересно, что же мы получили в результате:

john.freml.in/re2-benchmark

[@akzhan]

хм, в этом бенче рассматривается только cl-irregsexp, а не Google irregexp.