Решил на днях написать на Clojure утилиту поиска файлов по шаблону – аналог утилиты find. Это один из классических учебных примеров, который пишут при изучении нового языка. Основная процедура по поиску файлов выглядит так.
(defn find-files [matcher-func directory]
(if (or (nil? directory) (nil? matcher-func))
nil
(let [current (File. directory)
cur-list (seq (.list current))
dirs (filter #(and (not (= % ".")) (not (= % "..")))
(filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
found (vec (map #(concat-dirs directory %)
(filter #(matcher-func %) files)))]
(loop [d dirs
f found]
(if (or (nil? d) (empty? d))
f
(recur (next d)
(join f (find-files matcher-func
(concat-dirs directory (first d))))))))))
В current создается объект File с указанной директорией; cur-list содержит список всех файлов и поддиректорий в указанной директории; dirs содержит только поддиректории; files – только файлы указанной директории; found – только файлы, совпавшие с указанным регулярным выражением. В цикле loop для каждой поддиректории запускается эта же функция find-files, а результат накапливается в переменной f. Когда цикл закончится, функция вернет вектор всех найденных файлов.
Здесь не показаны функции concat-dirs (соединение базовой директории с поддиректорией или файлом при помощи File.separator), matcher-func (функция содержит откомпилированный Pattern для сравнения с именем файла) и join, которая объединяет элементы двух векторов в один.
Впринципе, функция работает хорошо и находит файлы довольно шустро. Но Clojure знаменит тем, что в нем concurrency работает «из коробки», поэтому хотелось бы как-нибудь ее распараллелить.
Например, можно было бы поиск файлов в каждой директории выполнять в отдельном параллельном потоке. Но что будет, если директорией значительно больше, чем ядер процессора? Значительное время уйдет на коммуникацию между потоками и на переключение между ними. Поэтому я решил в отдельный поток пускать только процесс сравнения файлов с заданным шаблоном. Изменить в исходники пришлось совсем немного.
(defn find-files [matcher-func directory]
(if (or (nil? directory) (nil? matcher-func))
nil
(let [current (File. directory)
cur-list (seq (.list current))
dirs (filter #(and (not (= % ".")) (not (= % "..")))
(filter #(.isDirectory (File. (concat-dirs directory %))) cur-list))
files (filter #(.isFile (File. (concat-dirs directory %))) cur-list)
found (future (vec (map #(concat-dirs directory %)
(filter #(matcher-func %) files))))]
(loop [d dirs
f []]
(if (or (nil? d) (empty? d))
(join f @found)
(recur (next d)
(join f (find-files matcher-func
(concat-dirs directory (first d))))))))))
Как видите, главное изменение в том, что теперь в переменной found содержится не мгновенно вычисленный список совпавших с шаблоном файлов, а объект «future», который вычисляет этот список в отдельном потоке. В тот момент, когда нужно получить вычисленное значение, обращаться нужно к переменной так: @found. При таком обращении к переменной found, Clojure заблокирует текущий поток до вычисления future. Впрочем, на большом количестве директорий и файлов, вряд ли когда-либо приходится включать блокировку; в большинстве случаев этот параллельный поток по поиску файлов завершается раньше основного.
Весь исходник программы можно посмотреть здесь: https://gist.github.com/792198 .
Интересно было сравнить производительность моей программы с существующими. Для сравнения я использовал поиск на большом количестве файлов и директорий при помощи следующих утилит: Nautilus 2.32.0, find 4.4.2, find-file-st – первая, однопоточная версия программы на clojure; find-file-mt – вторая, многопоточная версия. Сравнение проводил на ноутбуке Acer Aspire 5745G, Ubuntu 10.10 (32-битная). Искал по паттерну «A.*» среди залежей своих книжек, сгруппированных по темам.
Получилось вот что:
| Nautilus | Find-file-st | Find-file-mt | Find |
| 2min 20sec | 34sec | 18sec | 2sec |
Любопытно отметить следующее. Утилита find является однопоточной (по крайней мере мне не удалось найти упоминание создания потоков в ее исходниках), но явно очень круто оптимизированной. Никаких других объяснений ее волшебной скорости я не нашел.
Nautilus же поиск выполняет во многопоточном режиме, при том судя по всему на каждую директорию он создает отдельный поток (проверял в htop-е). В результате отвратительной реализации поиска, Nautilus значительно отстает по скорости не только от find, но даже от однопоточной версии моей программы, работающей, кстати, под jvm.
В общем, разрабатывать конкурентные программы на clojure удобно и быстро.
Комментариев нет:
Отправить комментарий