Как grep работает так быстро?

Я действительно поражен функциональностью GREP в оболочке, раньше я использовал метод подстроки в java, но теперь я использую для него GREP, и он выполняется за считанные секунды, он невероятно быстрее, чем код Java, который я писал. (по моему опыту я могу ошибаться)

При этом я не мог понять, как это происходит? в сети также мало что доступно.

Кто-нибудь может мне с этим помочь?

Предполагая, что ваш вопрос касается GNU grepконкретно. Вот заметка автора Майка Хэртела:

GNU grep работает быстро, потому что НЕ ИСПОЛЬЗУЕТ КАЖДЫЙ ВХОДНОЙ БАЙТ.

GNU grep работает быстро, потому что ВЫПОЛНЯЕТ ОЧЕНЬ НЕСКОЛЬКО ИНСТРУКЦИЙ ДЛЯ КАЖДОГО БАЙТА, который просматривает.

GNU grep использует хорошо известный алгоритм Бойера-Мура, который сначала ищет последнюю букву целевой строки и использует таблицу поиска, чтобы сообщить ей, насколько далеко вперед он может пропустить ввод при обнаружении несоответствующего символа.

GNU grep также разворачивает внутренний цикл Бойера-Мура и настраивает записи дельта-таблицы Бойера-Мура таким образом, что ему не нужно выполнять тест выхода из цикла на каждом развернутом шаге. Результатом этого является то, что в пределе GNU grep в среднем выполняет менее 3 инструкций x86, выполняемых для каждого входного байта, который он фактически просматривает (и полностью пропускает много байтов).

GNU grep использует исходные системные вызовы ввода Unix и избегает копирования данных после их чтения. Более того, GNU grep ИЗБЕГАЕТ РАЗРЫВА ВВОДА НА ЛИНИИ. Поиск новых строк замедлит grep в несколько раз, потому что для поиска новых строк он должен будет просматривать каждый байт!

Поэтому вместо использования строчно-ориентированного ввода GNU grep считывает необработанные данные в большой буфер, выполняет поиск в буфере с помощью Бойера-Мура, и только когда он находит совпадение, он переходит и ищет ограничивающие символы новой строки (некоторые параметры командной строки, такие как - n отключить эту оптимизацию.)

Этот ответ является частью информации, взятой отсюда .

Чтобы добавить к отличному ответу Стива.

Возможно, это не широко известно, но grep почти всегда работает быстрее при поиске более длинной строки шаблона, чем короткой, потому что в более длинном шаблоне Бойер-Мур может пропустить вперед более длинными шагами, чтобы достичь еще лучших сублинейных скоростей:

Пример:

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

Более длинная форма на 35% быстрее!

Как придешь? Бойер-Мур составляет таблицу перехода вперед из строки шаблона, и всякий раз, когда есть несоответствие, он выбирает самый длинный возможный пропуск (от последнего символа к первому), прежде чем сравнивать один символ во входных данных с символом в таблице пропуска.

Вот видео, объясняющее Бойера Мура (Кредит kommradHomer)

Другое распространенное заблуждение (для GNU grep) заключается в том, что fgrepон быстрее, чем grep. fin fgrepне означает «быстро», это означает «фиксированный» (см. справочную страницу), и поскольку обе являются одной и той же программой и обе используют Бойера-Мура , между ними нет разницы в скорости при поиске фиксированных - строки без специальных символов регулярного выражения. Единственная причина , почему я использовать fgrep, когда есть регулярное выражение специальный символ (например ., []или *) Я не хочу, чтобы это было истолковано как таковой. И даже тогда более портативная / стандартная форма grep -Fпредпочтительнее fgrep.