从文件路径列表构建树形结构（Python）- 性能相关

Question

从文件路径列表构建树形结构（Python）- 性能相关

19

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

我想创建一个函数，它可以以树形格式给出列表或类似的东西。

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

大概是这样的。我一直在尝试一些想法，但它们都没有提供我想要的速度。

注意：我已经有路径列表了，所以不用担心这个。该函数接收路径列表并给出树形列表。

谢谢提前。

- cwoebker

10

我正在开发一个用Python编写的非常高性能的文件管理/分析工具。 - mac

1

哈哈，我知道，我想先实现一些合理的东西，然后再使用更低级别的Cython等实现。 - cwoebker

3个回答

1

我对你的现有情况和需求不是很清楚（如果你能提供一些运行缓慢的代码将会很有帮助），但你可能应该将路径名拆分为目录名和文件名，然后使用一个专门的类或至少一个列表或字典的层次结构来构建树形结构。然后，通过各种遍历方式，你可以按照几乎任何你需要的方式进行序列化。

至于性能问题，你考虑过使用Pypy、Cython或者Shedskin吗？我一直在开发一个有趣的重复备份系统，它可以在Pypy或Cython上运行相同的代码；在32位上，使用Pypy实际上可以比Cython增强版本表现得更好（64位上稍微好一点）。我很想测试一下Shedskin，但显然无法在shedskin/cpython边界间进行迭代操作。

此外，当你遇到性能问题时，分析工具是必不可少的，至少在你已经选择了适当的算法的情况下。

- dstromberg

Cython 是计划在以后使用的。 - cwoebker

0

首先，“非常高的性能”和“Python”不太搭配。如果您要优化性能到极致，转换为C将带来比您想到的任何智能代码优化更好的效果。

其次，很难相信在一个“文件管理/分析工具包”中瓶颈会是这个函数。磁盘上的I/O操作至少比内存中发生的任何事情慢几个数量级。对代码进行分析是唯一准确的方法，但是……如果我错了，我愿意请你吃披萨！;)

我编写了一个简单的测试函数来进行一些初步的测量：

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万个文件的树。现在...除非您在Google工作，否则我认为这是一个可接受的结果。

相比之下，当我开始撰写这篇答案时，我点击了我的主80GB硬盘根目录上的“属性”选项[使用C代码应该给我它上面的文件数量]。几分钟过去了，我已经到了50 GB左右，300000个文件...

希望对你有所帮助！ :)

- mac

这确实很快，但与我的问题无关。我需要使用正则表达式或其他方法分析所有路径，然后获得像您在输入中使用的树形结构。 - cwoebker

@cwoebker - 你可能需要澄清你的问题，因为现在它并不清楚你的输入和期望输出是什么。如果你可以访问文件系统并从中读取文件名，那么这将有所帮助，或者你必须使用你希望举例说明的输入。 :) - mac

我添加了示例输入... 我可以访问文件系统。在项目中，我有一个 Redis 实例中的文件索引，我从那里读取路径，因此我不希望再次访问这些文件。 - cwoebker

1

我认为在谈到Python的高性能时提到切换到C语言已经成为陈词滥调。每个人都知道这一点，但你并没有看到每个人都回到了C语言。每种语言都有其自己的目的，很明显OP指的是在Python中实现最快算法，即以最少的时间顺序工作的算法。 - Ishan Srivastava

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mac · Accepted Answer

现在你更明确了问题，我猜以下是你想要的：

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/之间的区别。我认为这有助于您快速区分您的叶子是目录还是文件。

希望这回答了你的问题。如果有什么不清楚的，请发表评论。