Представлен (http://savannah.gnu.org/forum/forum.php?forum_id=8393
) новый выпуск популярной утилиты для организации поиска данных в текстовых файлах - GNU Grep 2.22 (http://www.gnu.org/software/grep/). В новом выпуске проведена оптимизация производительности поиска с использованием масок, содержащих очень длинные строки. Время обработки регулярного выражения в N байт сокращено с O(N^2)  до почти линейного вида. Например, ранее команда "grep -f <(seq -s '' 99999)" выполнялась больше минуты, а теперь отрабатывает меньше чем за секунду. В новом выпуске также устранена уязвимость CVE-2015-1345, которая могла привести к чтению неинициализированных данных из области за пределами выделенного буфера.

URL: http://savannah.gnu.org/forum/forum.php?forum_id=8393
Новость: http://www.opennet.me/opennews/art.shtml?num=43244

• Выпуск GNU grep 2.22,soarin, 06:18 , 03-Ноя-15
  • Выпуск GNU grep 2.22,бедный буратино, 07:19 , 03-Ноя-15
    • Выпуск GNU grep 2.22,Mihail Zenkov, 13:39 , 03-Ноя-15
  • Выпуск GNU grep 2.22,Аноним, 08:00 , 03-Ноя-15

> grep -f <(seq -s '' 99999)

grep: out of memory

Ась?

гарантировалось время выполнения в секунду
результат никто не гарантировал

То есть суть нового алгоритма - съесть всю память меньше чем за секунду? :)

time grep -f <(seq -s '' 99999)