Использование индекса для рекурсивного получения всех файлов в каталоге очень быстро

Question

Попытка № 2:

Кажется, люди не понимают, что я пытаюсь сделать. Позвольте мне увидеть, могу ли я заявить об этом более четко:

1) Чтение списка файлов намного быстрее, чем обход каталога.

2) Итак, давайте возьмем функцию, которая просматривает каталог и записывает полученный список в файл. Теперь, в будущем, если мы хотим получить все файлы в этом каталоге, мы можем просто прочитать этот файл, а не ходить по каталогу. Я называю этот файл индексом.

3) Очевидно, что при изменении файловой системы индексный файл выходит из синхронизации. Чтобы преодолеть это, у нас есть отдельная программа, которая подключается к ОС, чтобы отслеживать изменения в файловой системе. Он записывает эти изменения в файл, называемый журналом монитора. Сразу после того, как мы прочитали файл индекса для определенного каталога, мы используем журнал монитора, чтобы применить различные изменения к индексу, чтобы он отражал текущее состояние каталога.

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

Исходное сообщение:

Мне нужна функция, которая будет рекурсивно получать все файлы в любом каталоге и фильтровать их по различным параметрам. И я хочу, чтобы это было быстро - на порядок быстрее, чем просто идти по дороге. И я бы предпочел сделать это на Python. Кроссплатформенность предпочтительнее, но Windows наиболее важна.

Вот моя идея, как это сделать:

У меня есть функция с именем all_files:

def all_files(dir_path, ...parms...):
    ...

Когда я в первый раз вызываю эту функцию, она использует os.walk для создания списка всех файлов вместе с информацией о файлах, такой как, являются ли они скрытыми, символическая ссылка и т. Д. Я запишу эти данные в файл называется ".index" в каталоге. При последующих вызовах all_files будет обнаружен файл.index, и я буду читать этот файл, а не ходить по каталогу.

Это оставляет проблему отсутствия синхронизации индекса при добавлении и удалении файлов. Для этого у меня будет вторая программа, которая запускается при запуске, обнаруживает все изменения во всей файловой системе и записывает их в файл с именем "mod_log.txt". Он обнаруживает изменения через сигналы Windows, как метод, описанный здесь. Этот файл будет содержать одно событие на строку, причем каждое событие состоит из затронутого пути, типа события (создание, удаление и т. Д.) И отметки времени. Файл.index также будет иметь временную метку на время последнего обновления. После того, как я прочитал файл.index в all_files, я запишу mod_log.txt и найду все события, которые произошли после отметки времени в файле.index. Он возьмет эти последние события, найдет все, что относится к текущему каталогу, и соответствующим образом обновит индекс.

Наконец, я возьму список всех файлов, отфильтрую его по различным параметрам и верну результат.

Что вы думаете о моем подходе? Есть лучший способ сделать это?

Редактировать:

Проверьте этот код. Я вижу резкое ускорение от чтения кэшированного списка за рекурсивную прогулку.

import os
from os.path import join, exists
import cProfile, pstats

dir_name = "temp_dir"
index_path = ".index"

def create_test_files():
    os.mkdir(dir_name)
    index_file = open(index_path, 'w')
    for i in range(10):
        print "creating dir: ", i
        sub_dir = join(dir_name, str(i))
        os.mkdir(sub_dir)
        for i in range(100):
            file_path = join(sub_dir, str(i))
            open(file_path, 'w').close() 
            index_file.write(file_path + "\n")
    index_file.close()
#

#  0.238 seconds
def test_walk():            
    for info in os.walk("temp_dir"):
        pass

#  0.001 seconds
def test_read():
    open(index_path).readlines()

if not exists("temp_dir"):
    create_test_files()

def profile(s):
    cProfile.run(s, 'profile_results.txt')
    p = pstats.Stats('profile_results.txt')
    p.strip_dirs().sort_stats('cumulative').print_stats(10)

profile("test_walk()")
profile("test_read()")

Answer 1

Лучший ответ пришел от Michał Marczyk к нижней части списка комментариев по первому вопросу. Он указал, что то, что я описываю, очень близко к программе поиска UNIX. Я нашел версию для Windows здесь: http://locate32.net/index.php. Это решило мою проблему.

Изменить: На самом деле поисковая система Все выглядит еще лучше. Очевидно, Windows ведет журналы изменений в файловой системе, и все использует это для поддержания базы данных в актуальном состоянии.

Answer 2

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

Ваша схема ошибочна во многих отношениях, и она не даст вам улучшения на порядок.

Недостатки и потенциальные проблемы:

Вы всегда будете работать со снимком файловой системы. Вы никогда не будете знать с уверенностью, что это не существенно отличается от реальности. Если это находится в пределах рабочих параметров вашего приложения, нет пота.

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

Чтобы повысить точность кэша, необходимо увеличить частоту, с которой работает монитор файловой системы. Чем больше он работает, тем меньше фактического времени вы экономите.

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

Я мог бы продолжить.

Если, на самом деле, вы не заботитесь о работе со снимком файловой системы, который может сильно отличаться от реальности, я думаю, что вам было бы гораздо лучше сохранить индекс в памяти и выполнить обновление с помощью самого приложения. Это позволит устранить любые проблемы с конфликтами файлов, которые могут возникнуть в противном случае.

Answer 3

Разве Windows Desktop Search не предоставляет такой индекс как побочный продукт? На Mac указатель прожектора может быть запрошен для имен файлов, таких как: mdfind -onlyin . -name '*',

Конечно, это намного быстрее, чем ходить по каталогу.

Answer 4

Короткий ответ - нет". Вы не сможете построить систему индексации в Python, которая опередит файловую систему на порядок.

"Индексирование" файловой системы является интенсивной / медленной задачей, независимо от реализации кэширования. Единственный реальный способ избежать огромных накладных расходов на создание индексов файловой системы - это "индексировать по ходу", чтобы избежать большого обхода. (В конце концов, сама файловая система уже является индексатором данных.)

Существуют функции операционной системы, которые могут выполнять индексацию файловой системы "строим по ходу". Это основа таких сервисов, как Spotlight для OSX и Windows Desktop Search.

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

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

Здесь есть два урока. (а) Для создания правильного теста важно отделить "настройку" от "теста". Здесь ваш тест производительности по сути говорит: "Что быстрее, обход структуры каталогов или чтение индекса, который уже был создан заранее?" Очевидно, что это не сравнение яблок с апельсинами.

Тем не менее, (б) вы наткнулись на правильный ответ в то же время. Вы можете получить список файлов намного быстрее, если используете уже существующий индекс. Здесь вам нужно использовать что-то вроде индексов Windows Desktop Search или Spotlight.

Не заблуждайтесь, чтобы построить индекс файловой системы, вы должны, по определению, "посетить" каждый файл. Если ваши файлы хранятся в дереве, то рекурсивный обход, вероятно, будет самым быстрым способом доступа к каждому файлу. Если вопрос "могу ли я написать код Python, чтобы сделать именно то, что os.walk но на порядок быстрее, чем os.walk"Ответ - громкое нет. Если вопрос в том," могу ли я написать код Python для индексации каждого файла в системе, не тратя время на фактическое посещение каждого файла ", то ответ по-прежнему нет.

(Изменить в ответ на "Я не думаю, что вы понимаете, что я пытаюсь сделать")

Давайте проясним ситуацию: практически все здесь понимают, что вы пытаетесь сделать. Кажется, вы берете "нет, это не сработает так, как вы хотите, чтобы это сработало", что означает, что мы не понимаем.

Давайте посмотрим на это с другой стороны. Файловые системы с самого начала были важным компонентом современных вычислений. Категоризация, индексация, хранение и поиск данных являются серьезной частью информатики и вычислительной техники, и многие из самых блестящих умов в информатике постоянно работают над этим.

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

Если бы было так просто ускорить этот процесс на порядок (!), Просто сохраняя в текстовом файле индекс имен файлов и атрибутов, не думаете ли вы, что каждая существующая файловая система и операционная система будет делать именно это?

Тем не менее, конечно, кэширование результатов ваших конкретных запросов может привести к небольшому увеличению производительности. И, как и ожидалось, файловая система и дисковое кэширование являются фундаментальной частью любой современной операционной системы и файловой системы.

Но ваш вопрос, как вы его задали, имеет четкий ответ: нет. В общем случае вы не получите на порядок быстрее переопределения os.walk, Возможно, вы сможете добиться лучшего амортизируемого времени выполнения с помощью кеширования, но вы не сможете превзойти его на порядок, если правильно включите работу по созданию кеша в свое профилирование.

Answer 5

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

class DirectoryIterator:
    def __init__(self, start_dir, pattern):
        self.directory = start_dir
        self.pattern = pattern

 def __iter__(self):
     [([DirectoryIterator(dir, self.pattern) for dir in dirnames], [(yield os.path.join(dirpath, name)) for name in filenames if re.search(self.pattern, name) ]) for dirpath, dirnames, filenames in os.walk(self.directory)]

 ###########

 for file_name in DirectoryIterator(".", "\.py$"): print file_name

Answer 6

Я хотел бы рекомендовать вам просто использовать комбинацию os.walk (чтобы получить деревья каталогов) & os.stat (чтобы получить информацию о файле) для этого. Использование std-lib гарантирует, что он работает на всех платформах, и они прекрасно справляются со своей задачей. И не нужно ничего индексировать.

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