Структура данных для файловой системы

Question

Я храню/кэширую файловую систему (только имена файлов), чтобы иметь возможность делать быстрые исследования à la Everything. Таким образом, я не хочу использовать встроенный графический интерфейс поиска файлов в ОС.

Я делаю это с:

import os 
L = [] 
for root,dirs,files in os.walk(PATH): 
    L.append([root, files]) 

и результат таков:

[['D:\\', ['a.jpg', 'b.jpg']], 
... 
['D:\\Temp12', ['test.txt', 'test2.txt']]] 

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

query = 'test2' #searching for filename containg this text 
for dir in L: 
    for f in dir[1]: 
     if query in f: 
      print '%s found: %s' % (query, os.path.join(dir[0],f)) 

Действительно, это очень наивный поиск, потому что он требует просмотра он весь список, чтобы найти предметы.

Как сделать запросы быстрее?

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

Answer 1

Исследование в списках O (n), исследование в словарях амортизируется O (1). Если вам не нужно связывать значения, используйте наборы.

Если вы хотите больше об этом: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

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

EDIT:

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

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

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

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

Answer 2

Не могли бы вы использовать базу данных для этого?

SQLite предлагает: memory: option, который создает вашу базу данных только в памяти. Конечно, вы можете оптимизировать свой алгоритм и структуру данных, как указано в других ответах и ​​комментариях, но базы данных, как правило, уже очень хороши в этом с их индексацией, и вам не нужно будет создавать что-то подобное.

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

Просто мысль.

Hannu