Работает ли Unix grep быстрее с длинными или короткими поисковыми терминами?

Question

Это быстрее искать длинные или короткие условия поиска? Или это вообще влияет на скорость? Другими словами, должны ли вы сделать условия поиска максимально точными?

Существует более 100 000 файлов, и каждый файл содержит от 20 до более 5000 строк данных. Обычно grep используется для поиска только одного экземпляра поискового запроса.

Допустим, поисковым термином является SEARCHTERM , и он будет в следующей строке:

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

Быстрее искать "ПОИСК" или "ПОИСК"? Допустим, в этом случае нам все равно, найдем ли мы совпадения и в других несвязанных строках.

Вот как я сейчас это делаю:

grep NAD+DP 123* | grep SEARCHTERM

Но я все еще нахожу это довольно медленно. Обычно поиск данных занимает около 3-5 минут, даже если я знаю приблизительное имя файла, которое ограничивает диапазон до 10 000 файлов.

Так поможет ли более длинный или короткий поисковый запрос? Насколько я знаю, grep ищет "блоки" слов определенной длины?

Answer 1

Некоторые справочные материалы:

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

Почему GNU grep быстр.

Алгоритм предварительно обрабатывает искомую строку (шаблон), но не искомую строку (текст). [...] В общем, алгоритм работает быстрее с увеличением длины шаблона.

из алгоритма поиска строки Бойера – Мура.

Вывод: используйте более длинные строки.

Теперь немного эталона для развлечения:

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v` # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

Результаты: 0,952 с - среднее значение для короткой строки, 0,244 с - среднее значение для длинной строки.

NB . Длина не является единственным критерием, который необходимо принимать во внимание.

Answer 2

Вы можете попробовать себя, используя ПОИСК или ПОИСК. Также попробуйте изменить порядок двух команд grep. В любом случае единственной полезной опцией, скорее всего, будет использование нескольких ядер ЦП для одного поиска. Смотрите parallel команду.

Answer 3

Я не думаю, что указание более конкретного поискового запроса сделает его заметно быстрее.

С таким большим количеством файлов для поиска, вам нужно как-то проиндексировать ваши данные, чтобы сделать поиск быстрее.

Я могу предложить несколько способов:

• Создайте базу данных (PostgreSQL или MySQL), импортируйте ваши данные в базу данных - один файл в одной строке, добавьте индекс FTS (полнотекстовый поиск). Создайте некоторую утилиту для запроса базы данных.

• Импортируйте данные в базу данных более детальным способом, возможно, одной строкой в одну строку (или, возможно, более чем одну таблицу), создавайте индексы, чтобы ваши данные можно было искать с помощью индекса (ов). Создайте некоторую утилиту для запроса базы данных.

• Добавьте ваши файлы в репозиторий git , сожмите его с помощью git gc , используйте git grep для поиска. По моему опыту, git grep может быть быстрее, чем стандартный grep , в 10–100 раз.

Answer 4

Логически, более короткий срок потребует меньше процессорного времени, как это делает grep

if (filechar[i] == pattern[i]) ...

меньше раз  В действительности, я бы предположил, что grep будет связан с вводом / выводом, а не с процессором, так что это не будет иметь значения.