Почему less сильно медленнее grep? Поиск по простой строке в лог-файле 3.5G занимает 2.3сек grep-ом и 58сек less-ом. Пробовал отключать номера строк "less -n" — результат тот же.

$ grep --version
GNU grep 2.6.3

Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

$ less --version
less 436
Copyright (C) 1984-2009 Mark Nudelman

less comes with NO WARRANTY, to the extent permitted by law.
For information about the terms of redistribution,
see the file named README in the less distribution.
Homepage: http://www.greenwoodsoftware.com/less

Здравствуйте, ·, Вы писали:

·>Почему less сильно медленнее grep?
Потому что они принципиально по-разному работают с текстом.
Если grep — это чисто потоковый проходчик, которому надо хранить минимальный контекст, то less должен обеспечить поиск в обоих направлениях, хранения фрагмента текста в памяти (с догрузкой — он же не все 3.5 Гб сразу в ОЗУ запихал) + моменты связанные с обработкой управляющих символов, форматирования и т.п.

Здравствуйте, DOOM, Вы писали:

DOO>·>Почему less сильно медленнее grep?
DOO>Потому что они принципиально по-разному работают с текстом.
DOO>Если grep — это чисто потоковый проходчик, которому надо хранить минимальный контекст, то less должен обеспечить поиск в обоих направлениях,
Да я ищу в одинаковом направлении, да и даже
tac file | grep some-string
работает 5.6сек. Не должно оно быть в 20 раз медленнее...

DOO>хранения фрагмента текста в памяти (с догрузкой — он же не все 3.5 Гб сразу в ОЗУ запихал) + моменты связанные с обработкой управляющих символов, форматирования и т.п.
А зачем это для поиска позиции?.. Искать можно поточно, как grep, а потом, чтобы отобразить с найденной позиции — требуются только данные, которые влазят на экран.
В общем наверное придётся в исходниках покопаться, чтобы точно понять.

Здравствуйте, ·, Вы писали:

·>Почему less сильно медленнее grep? Поиск по простой строке в лог-файле 3.5G занимает 2.3сек grep-ом и 58сек less-ом. Пробовал отключать номера строк "less -n" — результат тот же.

Можно искать методом грубой силы (типа strstr()), наверняка этот метод
не используется в обоих программах... ввиду дикой алгоритмической сложности.

Можно использовать алгоритмы Бойера-Мура или Кнута-Морриса-Пратта. Скорей
что-то подобное и используется. Но если grep ищет строку как есть и вопрос
применимости алгоритмов не стоит, всё тривиально, то less ищет регулярное выражение.
Которое после ввода компилируется в конечный автомат разбирающий строки.
И как он стыкуется с алгоритмами быстрого поиска -- ещё вопрос.

Потом можно просматривать текст не побайтово, а машинными словами
(по 4 или даже 8 байт за раз). Т.е. текст на вход поступает в виде последовательности
слов, к ним применяются маски (для отсечения ненужных символов) и сравниваются
с образцами. И так N фаз (4 или 8, неизвестно на сколько сдвинут текст).
Использует ли это grep -- не знаю, потому как такая методика опять же плохо
стыкуается с алгоритмами быстрого поиска. Наверняка в grep есть множество
вариантов как искать и под конкретный случай подбирается более подходящий
по скорости. А в less используется более медленное универсальное решение.

Здравствуйте, ·, Вы писали:

DOO>>·>Почему less сильно медленнее grep?
DOO>>Потому что они принципиально по-разному работают с текстом.
DOO>>Если grep — это чисто потоковый проходчик, которому надо хранить минимальный контекст, то less должен обеспечить поиск в обоих направлениях,
·>Да я ищу в одинаковом направлении

А откуда less'у знать что ты например не перейдёшь в самое начало через g? — вот ему и нужно хранить весь выхлоп
Кстати, more в отличии от less ищет только в одном направлении, и не позволяет переходить назад, и поэтому он может позволить себе не хранить весь stdin.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP> ·>Да я ищу в одинаковом направлении
EP> А откуда less'у знать что ты например не перейдёшь в самое начало через g? — вот ему и нужно хранить весь выхлоп
Да, тут надо частный случай рассматривать. Если просто поток, то его надо где-то сохранять, а если файл — то можно иметь random access к любой позиции.

EP> Кстати, more в отличии от less ищет только в одном направлении, и не позволяет переходить назад, и поэтому он может позволить себе не хранить весь stdin.
Было бы удобно иметь less-подобную программу, но оптимизированную для работы с файлами...