Python: Рекурсивный поиск каталогов, содержащих файл с расширением, исключая подкаталоги, когда файл найден.

Question

Вот пример моей структуры каталогов: https://pastebin.com/XimFQdS7

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

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

Это будет желаемый результат для приведенной выше структуры:

[
    'root/dir1/dirA/',
    'root/dir1/dirB/',
    'root/dir2/',
    'root/dir3/dirA/dirX/',
    'root/dir3/dirA/dirY/'
]

Это мой текущий код поиска:

def getSubDirectoriesContainingFileType(root, extension):
    os.chdir(root)
    fileFormat = '**/*.{}'.format(extension)
    files = glob.glob(fileFormat, recursive = True)

    matchingDirs = [os.path.dirname(os.path.abspath(file)) for file in files]

    return matchingDirs

Я использовал glob, так как обнаружил, что он немного быстрее, чем os.walk () но я думаю, что для реализации алгоритма, о котором я говорю выше, мне пришлось бы go вернуться к os.walk ().

Идея алгоритма:

def searchDirs(root):
    dirs = []

    for dir in rootDirs:
        search for file with ext
        if found:
            append dir to dirs
        else:
            append searchDirs(dir) to dirs
    return dirs

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

Answer 1

Мне показался ваш вопрос интригующим, поэтому я провел небольшое тестирование. Сравнение сырого результата из glob без фильтрации нежелательных подкаталогов с функцией поиска Speci c для желаемых результатов .

Кажется, что поиск с указанием c примерно в два раза быстрее , давая желаемый результат без какой-либо дополнительной обработки.

Я думаю, что фокус в

1 немедленная остановка l oop, если файл prj обнаружен

2 в том же l oop, одновременный поиск поддиректорий и файла prj.

import os
import random
from pathlib import Path
import time

# --------------------------------------------------------
def make_sub_dirs(dir):

    new_dir_paths = []

    for i in range(4):
        new_dir_path = os.path.join(dir, f'dir{i}')
        os.makedirs(new_dir_path)
        if random.randint(0, 3) == 1:
            prj_file = os.path.join(new_dir_path, 'test.prj')
            Path(prj_file).touch()

        new_dir_paths.append(new_dir_path)

    return new_dir_paths

# --------------------------------------------------------
def make_tree():

    base_dir = [r'K:\test_tree']

    if os.path.exists(base_dir[0]):
        # already made
        return

    current_level_dir_paths = base_dir

    for depth in range(3):
        new_dir_paths = []
        for dir in current_level_dir_paths:
            new_dir_paths.extend(make_sub_dirs(dir))

        current_level_dir_paths = new_dir_paths

# --------------------------------------------------------
def search_first_prj_dirs(search_dir_path):

    dirs_found = []

    dir_entries = os.listdir(search_dir_path)

    for dir_entry in dir_entries:
        dir_entry_path = os.path.join(search_dir_path, dir_entry)
        if os.path.isfile(dir_entry_path):
            if os.path.splitext(dir_entry)[-1] == '.prj':
                # found !!!!!!
                return [search_dir_path]
        else:
            # this should be a dir
            dirs_found.append(dir_entry_path)

    # no prj found, recurse into the found sub dirs
    first_prj_dirs = []
    for dir in dirs_found:
        first_prj_dirs.extend(search_first_prj_dirs(dir))

    return first_prj_dirs

# --------------------------------------------------------

make_tree()

start_time = time.time()
raw_glob_result = list(Path(r'K:\test_tree').rglob('*.prj'))
end_time = time.time()
print('raw glob', len(raw_glob_result), end_time - start_time)

start_time = time.time()
search_first_prj_dirs_result = search_first_prj_dirs(r'K:\test_tree')
end_time = time.time()
print('specific', len(search_first_prj_dirs_result), end_time - start_time)

print('-------------')

raw_glob_result.sort()
for result in raw_glob_result:
    print(result)

print('-------------')

search_first_prj_dirs_result.sort()
for result in search_first_prj_dirs_result:
    print(result)

Результат

raw glob 17 0.023003816604614258
specific 11 0.010011434555053711
------------- raw glob
K:\test_tree\dir0\dir0\dir0\test.prj
K:\test_tree\dir0\dir3\dir2\test.prj
K:\test_tree\dir1\dir0\dir2\test.prj
K:\test_tree\dir1\dir0\test.prj
K:\test_tree\dir1\dir2\dir1\test.prj
K:\test_tree\dir1\dir2\dir3\test.prj
K:\test_tree\dir1\dir3\dir0\test.prj
K:\test_tree\dir1\dir3\dir1\test.prj
K:\test_tree\dir1\dir3\test.prj
K:\test_tree\dir2\dir0\dir2\test.prj
K:\test_tree\dir2\dir1\dir1\test.prj
K:\test_tree\dir2\dir2\dir1\test.prj
K:\test_tree\dir2\dir3\dir2\test.prj
K:\test_tree\dir3\dir1\dir1\test.prj
K:\test_tree\dir3\dir2\dir3\test.prj
K:\test_tree\dir3\dir3\test.prj
K:\test_tree\dir3\test.prj
------------- specific
K:\test_tree\dir0\dir0\dir0
K:\test_tree\dir0\dir3\dir2
K:\test_tree\dir1\dir0
K:\test_tree\dir1\dir2\dir1
K:\test_tree\dir1\dir2\dir3
K:\test_tree\dir1\dir3
K:\test_tree\dir2\dir0\dir2
K:\test_tree\dir2\dir1\dir1
K:\test_tree\dir2\dir2\dir1
K:\test_tree\dir2\dir3\dir2
K:\test_tree\dir3

Answer 2

Использование Path.rglob

from pathlib import Path

def searchDirs(root):
    return list(Path(root).rglob('*.prj'))

Вывод:

/root/dir1/dirB/project.prj
/root/dir1/dirB/test/project.prj
/root/dir1/diraA/project.prj
/root/dir3/dirx/project.prj
/root/dir2/project.prj