442
правки
Изменения
→Несколько полезных оптимизаций на примере Haskell
== Несколько полезных оптимизаций на примере Haskell ==
Gabriel Gonzalez <ref>[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez{{---}} Regex in Haskell] </ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
* использовал Word вместо Integer, ещё в 8 раз быстрее
* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
В итоге его реализация оказалась всего в 4 раза медленнее grep. Но это не предел, у него получилось реализовать параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf параллельный конечный автоматData-Parallel Finite-State Machines] </ref> и сделать свою реализацию в 1.5 раза быстрее, чем grep.
== ReDoS (regular expression denial of service) ==
