从文件路径列表构建树（Python） - 性能依赖

19 投票

3 回答

14310 浏览

提问于 2025-04-17 08:16

嘿，我正在用Python开发一个高性能的文件管理和分析工具包。

我想创建一个函数，能够给我一个以树形结构展示的列表，类似于这个问题（与Java相关）。

从：

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

注意：这个路径列表是无序的。

到：

dir/
    file
    dir2/
        file2
    file3
dir3/
    file4
    file5

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

大概是这样的。我尝试了一些想法，但都没有达到我想要的速度。

注意：我已经有了路径列表，所以不用担心这个。这个函数会接收路径列表，然后返回树形列表。

提前谢谢你！

性能优化数据结构函数设计树形结构文件管理高性能计算无序列表路径解析

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秒钟内你可以处理大约100万个文件。现在……除非你在谷歌工作，否则这个结果对我来说是可以接受的。

相比之下，当我开始写这个回答时，我在我的主80GB硬盘的根目录上点击了“属性”选项（这应该能告诉我上面的文件数量，使用C语言代码）。过了几分钟，我发现大约有50GB，300000个文件……

希望这对你有帮助！ :)

回答于 2025-04-17 由 Python大师

分享举报

我不太清楚你现在有什么和需要什么（如果能提供一些你觉得运行太慢的代码，那会更有帮助），但你可以考虑把路径名分成目录名和基本名，然后用一个专门的类来构建一个树形结构，或者至少用列表或字典来建立一个层级关系。这样的话，通过不同的遍历方式，你就可以几乎以任何你需要的方式来序列化数据。

至于性能问题，你有没有考虑过使用Pypy、Cython或者Shedskin？我自己在做一个去重备份系统，出于好玩，发现它可以在Pypy或Cython上运行；在Pypy上运行的速度其实比加了Cython的版本快很多（在32位系统上差别很大，在64位系统上差别稍微小一点）。我也想比较一下Shedskin，但听说它在Shedskin和CPython之间不能进行切换。

另外，当你遇到性能问题时，进行性能分析是非常重要的——至少在你已经选择了合适的算法的情况下。

回答于 2025-04-17 由 Python大师

分享举报

现在你把问题说得更清楚了，我想你想要的内容是：

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']

有几点需要注意：

这个脚本大量使用了 defaultdict，简单来说，这样可以省去检查某个键是否存在以及初始化它的步骤。
目录名被映射为字典的键，我觉得这对你来说是个不错的功能，因为键是经过哈希处理的，这样你能比用列表更快地获取信息。你可以通过 main_dict['dir2']['alpha']['beta'] 的形式访问层级结构……
注意 .../delta 和 .../delta/ 之间的区别。我觉得这对你很有帮助，可以快速区分你的叶子是目录还是文件。

希望这能解答你的问题。如果还有不清楚的地方，欢迎留言。

回答于 2025-04-17 由 Python大师

分享举报

从文件路径列表构建树（Python） - 性能依赖

3 个回答

撰写回答