Что менее накладно: поиск файла в директории или поиск строки в файле ?

[ksa]

Вопрос по практической части. Что накладнее (и, соответственно, дольше): искать файл по определенному имени в каталоге (утилитой find) либо искать определенную строку в файле (искать с помощью, например, grep или sed) ? Подозреваю, что второй вариант. Но все же хотелось бы получить больше информации на этот счет, если кто имеет, что сказать по этому поводу.
Грубо говоря, если определенную информацию (определенного объема) представить в двух ниже перечисленных вариантах, то какой из вариантов поиска (обозначенных выше) будет быстрее ?
1) куча файлов в директории
2) файл с кучей строк, равной количеству файлов в первом случае

[ruslandh]

Теоретически одно и то-же - каталог - это-же тот-же файл. Правда при рекурсивном поиске, когда меняются имена каталогов, быстрее искать в одном файле.

[ksa]

Правда при рекурсивном поиске, когда меняются имена каталогов, быстрее искать в одном файле.

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

[ASte]

все ниженаписанное - мое ИМХО.
Если искомые данные представлены короткой строкой, а описывает она некий значительный по сравнению с "ключевой" строкой объем данных то у нас будет файл с коротким именем и некоторым содержимым.
Утилите find понадобится прочитать с диска только сам каталог и искать в нем короткую строку среди коротких. Но искать штатно мы сможем только по имени файла.
Если же все строки находятся в файле, и "ключевой" является только часть длинной строки, то для поиска искомой подстроки утилите grep придется считать весть файл и искать подстроку в каждой длинной строке.  Т.е прочитать и обработать понадобится больше байт. Но искать сможем любую подстроку в "большой" строке.
В этих условиях теоретически поиск в каталоге должен быть быстрее.

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

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

[Speccyfighter]

Шут его знает...
Так как-то, скорость поиска (время в секундах):

locate:

Код: [Выделить]

$ rpm -qa|grep locate
mlocate-0.26-alt1


Код: [Выделить]

# База создана только для /home
# updatedb --add-prunepaths "/bin /dev /lost+found /mnt /proc /run /selinux /sys /usr /boot /etc /lib /media /opt /root /sbin /srv /tmp /var"


Код: [Выделить]

# time -f %e locate -i acpi
/home/user/Документы/eeepc-acpi-scripts.txt
/home/user/Документы/salix-acpi.txt
/home/user/Загрузки/ACPI_5.pdf
0.51


Код: [Выделить]

# echo 3 > /proc/sys/vm/drop_caches


Код: [Выделить]

$ updatedb -l 0 -U /home/user/ -o /home/user/base/mlocate.db


Код: [Выделить]

$ time -f %e locate -d /home/user/base/mlocate.db -i acpi
/home/user/Документы/eeepc-acpi-scripts.txt
/home/user/Документы/salix-acpi.txt
/home/user/Загрузки/ACPI_5.pdf
0.50


Код: [Выделить]

# echo 3 > /proc/sys/vm/drop_caches

find:

Код: [Выделить]

# time -f %e find /home/user/[A-Z,a-z,А-Я,а-я,]* -iname "*acpi*"
/home/user/Документы/salix-acpi.txt
/home/user/Документы/eeepc-acpi-scripts.txt
/home/user/Загрузки/ACPI_5.pdf
1.14


Код: [Выделить]

# echo 3 > /proc/sys/vm/drop_caches

grep:

Код: [Выделить]

$ du -m ~/Загрузки/tasks-161462-build-100-i586-rpms/161704/gstreamer1.0/palemoon-26.1.1-alt5.ca77.i586.rpm
22 /home/user/Загрузки/tasks-161462-build-100-i586-rpms/161704/gstreamer1.0/palemoon-26.1.1-alt5.ca77.i586.rpm


Код: [Выделить]

$ time -f %e grep -rHi c1e9 ~/Загрузки/tasks-161462-build-100-i586-rpms/161704/gstreamer1.0/palemoon-26.1.1-alt5.ca77.i586.rpm
Двоичный файл /home/user/Загрузки/tasks-161462-build-100-i586-rpms/161704/gstreamer1.0/palemoon-26.1.1-alt5.ca77.i586.rpm совпадает
0.49

Т.е.:
При поиске в одном массиве операции выполняются быстрее.

[ASte]

Speccyfighter
У Вас в примере обходим несколько каталогов. В граничных условиях задачи было что каталог один и в нем много-много файлов...
Вы подтвердили что

Правда при рекурсивном поиске, когда меняются имена каталогов, быстрее искать в одном файле.

[ksa]

Благодарю за ваши ответы. Тоже подумал, что обход каталога (вполне можно это считать индексом, если имена файлов изначально задуманы как элементы этого индекса определенного шаблона) может быть быстрее. К тому же, каталог в нашем случае получается ещё и практически удобнее. Насчет же самого главного параметра - количества - затрудняюсь сказать (полагаю, что десяток тысяч вполне может быть; тут все будет зависеть от активности пользователей альта).

[ksa]

Однако, для определенных операций один файл действительно будет быстрее. Спасибо Speccyfighter за подсказку насчет утилиты для создания базы имен файлов (с точки зрения поиска среди имен файлов или части имени).

[ksa]

Создал для проверки базу из ~80500 файлов, получил файл размером 3 с копейками мегабайта. Вполне приемлемо надо сказать. Время создания (без использования данных из кэша, имитация первого запуска) в районе 17 секунд на одноядерном селероне, который  D. Та же операция, но с задействованием кэша - 0.57 секунды. Если стараться сервер держать все время в работе, то обновление базы из кэша будет занимать незначительное время, поиск при этом заметно ускорится.

[ksa]

Однако, найден способ, который быстрее этой базы (правда места больше ест, но кто в наш век об этом думает, если разница в размерах менее трех раз) и это, как не странно, использование гнутых утилит.

[ruslandh]

Однако, найден способ, который быстрее этой базы (правда места больше ест, но кто в наш век об этом думает, если разница в размерах менее трех раз) и это, как не странно, использование гнутых утилит.

И какой? Кстати, если создать файл-индекс  с путями до всех нужных файлов, отсортированных по именам, то поиск можно сделать ещё быстрее :) И кстати, тогда файлы можно раскладывать в разные каталоги, например, исходя из удобства анализа источников данных.

[ksa]

И какой?

Простой как три копейки.

Кстати, если создать файл-индекс  с путями до всех нужных файлов, отсортированных по именам, то поиск можно сделать ещё быстрее :)

Не придумали ещё более быстрых инструментов для работы с файлами, чем гнутые утилиты из поставки coreutils. Загнал через find список файлов в файл и погрепал. Скорость космическая, никаким locate не снилась (файлов ~ 71000 было). Поиск грепом занимает 0.03 единицы по показаниям time, независимо от того, сколько строк в выводе. А у locate чем больше строк в выхлопе, тем оно медленнее. И меньше 0.40 единиц по показаниям time поиск по базе не занимает, даже с учетом кэша. Минусом космического варианта является то, что размер "базы" получается больше (в данном конкретном случае в файле database.txt присутствуют полные пути, если оставить только имена файлов в русле условий имеющейся задачи, то размер сравняется и разницы практически не будет).

Код: [Выделить]

# du -b /var/lib/mlocate/mlocate.db
2797625 /var/lib/mlocate/mlocate.db
# du -b /home/user/database.txt
9190473 /home/user/database.txt

[ksa]

в данном конкретном случае в файле database.txt присутствуют полные пути, если оставить только имена файлов в русле условий имеющейся задачи, то размер сравняется и разницы практически не будет

И в этом случае преимущество в простом файле со списком имен:

Код: [Выделить]

# du -b /home/user/database.txt
1799107 /home/user/database.txt
# du -b /var/lib/mlocate/mlocate.db
2797625 /var/lib/mlocate/mlocate.dbПри этом по показаниям time время работы grep по текстовому файлу 0.00 (в нашем случае использование/не использование кэша роли не играет, т.к. картину существенно не меняет, но показывает оптимистичный расклад по работе в реальных условиях).
Добавление в "базу" списка файлов посредством find (по показаниям time) около 0.5
Если перефразировать и перевести на русский все, что сказано выше, то получается, что за то время, пока locate только ищет, мы успеваем и обновить "базу" и найти нужное.

[Speccyfighter]

grep по файлу
Для ускорения поиска, кеш нельзя дропать, и нельзя допускать чтобы он дропался. Поэтому, чем больше выделено памяти под кеш, тем лучше.
И важно, чтобы кеша всегда было много.

Код: [Выделить]

# rpm -ql $(rpm -qa) > base-files.txt


Код: [Выделить]

# du -b base-files.txt
6019475 base-files.txt


Код: [Выделить]

# wc -l base-files.txt
111347 base-files.txt


Код: [Выделить]

# echo 3 > /proc/sys/vm/drop_caches


Код: [Выделить]

# time -f %e grep '\/sh$' base-files.txt
/bin/sh
/usr/share/bash-completion/completions/sh
0.53


Код: [Выделить]

# time -f %e grep '\/rkhunter' base-files.txt
/etc/rkhunter.conf
...
дохрена
...
/var/lib/rkhunter/tmp
0.02


Код: [Выделить]

# echo 3 > /proc/sys/vm/drop_caches


Код: [Выделить]

# time -f %e grep '\/rkhunter' base-files.txt
/etc/rkhunter.conf
...
дохрена
...
/var/lib/rkhunter/tmp
0.42


Код: [Выделить]

# time -f %e grep '\/acpi' base-files.txt
/lib/modules/4.1.19-std-def-alt1/kernel/drivers/acpi
/lib/modules/4.1.19-std-def-alt1/kernel/drivers/acpi/ac.ko
...
очень дохрена
...
/etc/acpi/lib/sound.sh
/etc/acpi/lib/touchpad.sh
0.05

Иначе разница будет нивелирована.

[ksa]

Для ускорения поиска, кеш нельзя дропать, и нельзя допускать чтобы он дропался. Поэтому, чем больше выделено памяти под кеш, тем лучше.
И важно, чтобы кеша всегда было много.

Конкретно в этом случае, вполне будет достаточно 10 метров под кэш (думаю, что подобный размер обеспечит любое железо, даже не совсем свежее). Не могу даже вообразить, сколько нужно будет времени, чтобы довести размер файла до такой величины (очень продолжительное время размер будет менее 2 мегабайт). То есть, говорить вообще не о чем в этом конкретном случае. А вот для другого применения надо будет посмотреть на разницу. В любом случае надо будет комплексную проверку провести, только время надо найти подходящее количество на все и дописать прототип по части пропуска в хранилще. Плюс ещё преимущество многих файлов перед одним файлом - гипотетические проблемы с диском. Какой-то сегмент может и выпасть, но большая часть файлов может быть сохранена (при условии, что бэкапов нет). С базой же (изначально) сложнее - утилиты нужны из соответствующих пакетов в системе, где они могут быть не нужны от слова совсем (либо это какая-то железка, на которую имеется ограниченное количество пакетов) плюс повреждение файла базы может быть критично для возможности восстановления (безотносительно возможностей утилит).