Построить дерево из списка путей к файлам (Python) - зависит от производительности

Question

Привет, я работаю над высокопроизводительным инструментарием для управления / анализа файлов, написанным на python.Я хочу создать функцию, которая дает мне список или что-то подобное в древовидном формате.Нечто подобное в этом вопросе (связанном с java)

From:

dir/file
dir/dir2/file2
dir/file3
dir3/file4
dir3/file5

Примечание: список путей не отсортирован

To:

dir/
    file
    dir2/
        file2
    file3
dir3/
    file4
    file5

[[dir, [file, [dir2, [file2]], file3]], [dir3, [file4, file5]]]

что-то в этом роде.Я играл с некоторыми идеями, но ни одна из них не дала желаемой скорости.

Примечание: у меня уже есть список путей, так что не беспокойтесь об этом.Функция берет список путей и список деревьев.

Заранее спасибо

Answer 1

Теперь, когда вы прояснили вопрос немного больше, я думаю, вам нужно следующее:

from collections import defaultdict

input_ = '''dir/file
dir/dir2/file2
dir/file3
dir2/alpha/beta/gamma/delta
dir2/alpha/beta/gamma/delta/
dir3/file4
dir3/file5'''

FILE_MARKER = '<files>'

def attach(branch, trunk):
    '''
    Insert a branch of directories on its trunk.
    '''
    parts = branch.split('/', 1)
    if len(parts) == 1:  # branch is a file
        trunk[FILE_MARKER].append(parts[0])
    else:
        node, others = parts
        if node not in trunk:
            trunk[node] = defaultdict(dict, ((FILE_MARKER, []),))
        attach(others, trunk[node])

def prettify(d, indent=0):
    '''
    Print the file tree structure with proper indentation.
    '''
    for key, value in d.iteritems():
        if key == FILE_MARKER:
            if value:
                print '  ' * indent + str(value)
        else:
            print '  ' * indent + str(key)
            if isinstance(value, dict):
                prettify(value, indent+1)
            else:
                print '  ' * (indent+1) + str(value)



main_dict = defaultdict(dict, ((FILE_MARKER, []),))
for line in input_.split('\n'):
    attach(line, main_dict)

prettify(main_dict)

Это выводит:

dir3
  ['file4', 'file5']
dir2
  alpha
    beta
      gamma
        ['delta']
        delta
          ['']
dir
  dir2
    ['file2']
  ['file', 'file3']

Несколько замечаний:

• Сценарий интенсивно использует defaultdicts , в основном это позволяет пропустить проверку на наличие ключа и его инициализацию, если его там нет
• Имена каталогов сопоставлены с ключами словаря, я подумал, что это может быть хорошей функцией для вас, так как ключи хешируются, и вы сможете получать информацию намного быстрее, чем со списками. Вы можете получить доступ к иерархии в форме main_dict['dir2']['alpha']['beta'] ...
• Обратите внимание на разницу между .../delta и .../delta/. Я подумал, что это поможет вам быстро отличить лист, являющийся каталогом или файлом.

Надеюсь, это ответит на ваш вопрос. Если что-то неясно, оставьте комментарий.

Answer 2

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

Что касается проблем с производительностью, рассматривали ли вы использование Pypy, Cython или Shedskin?У меня есть дедуплицирующая система резервного копирования, над которой я работал ради удовольствия, которая может запускать один и тот же код на Pypy или Cython;запуск его на Pypy на самом деле превосходит версию, дополненную Cython (в 32-битной версии и в 64-битной версии).Я бы тоже хотел сравнить shedskin, но он, очевидно, не может выйти за границы shedskin / cpython.

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

Answer 3

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

Во-вторых, трудно поверить, что узким местом в "инструменте управления / анализа файлов" будет эта функция . Операции ввода-вывода на диске, по крайней мере, на несколько порядков медленнее, чем все, что происходит в памяти. Профилирование вашего кода - единственный точный способ оценить это, но ... я готов заплатить вам пиццу, если я ошибаюсь! ;)

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

from timeit import Timer as T

PLIST = [['dir', ['file', ['dir2', ['file2']], 'file3']], ['dir3', ['file4', 'file5', 'file6', 'file7']]]

def tree(plist, indent=0):
    level = []
    for el in plist:
        if isinstance(el, list):
            level.extend(tree(el, indent + 2))
        else:
            level.append(' ' * indent + el)
    return level

print T(lambda : tree(PLIST)).repeat(number=100000)

Это выводит:

[1.0135619640350342, 1.0107290744781494, 1.0090651512145996]

Поскольку список тестовых путей составляет 10 файлов, а число итераций равно 100000, это означает, что за 1 секунду вы можете обработать дерево из примерно 1 миллиона файлов. Теперь ... если вы не работаете в Google, это кажется мне приемлемым результатом.

В отличие от этого, когда я начал писать этот ответ, я щелкнул опцию «свойство» в корне моего основного 80-гигабайтного HD (это должно дать мне количество файлов на нем, используя C-код). Прошло несколько минут, и у меня около 50 ГБ, 300000 файлов ...

НТН! :)