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

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. Он возьмет последние события, найдет все, что относится к текущему каталогу, и соответствующим образом обновит индекс.

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

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

Edit:

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

Не заблуждайтесь, чтобы построить индекс файловой системы, вы должны, по определению, "посетить" каждый файл. Если ваши файлы хранятся в дереве, то рекурсивный обход, вероятно, будет самым быстрым способом доступа к каждому файлу. Если вопрос «могу ли я написать код Python, чтобы точно делать то, что делает os.walk, но быть на порядок быстрее, чем os.walk», то ответом будет no . Если вопрос «могу ли я написать код 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 гарантирует, что он работает на всех платформах, и они прекрасно справляются со своей задачей. И не нужно ничего индексировать.

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