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

嘿，我正在研究用python编写的非常高性能的文件管理/分析工具包。我想创建一个函数给我一个树形格式的列表或类似的东西。喜欢的东西在这个question (java-related)从列表os文件路径构建树（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]]]

类似的规定。我一直在玩弄一些想法，但没有一个提供我想要的速度。

注：我已经有路径列表，所以不用担心。该函数获取路径列表并给出树列表。

由于提前

来源

2011-12-13 cwoebker

*“我正在研究用Python编写**非常高性能的**文件管理/分析工具包**。* *哎呀！ :( – mac

哈哈我知道，我想要一些合理的实施第一和后者我将使用更低层次的实施与cython等... – cwoebker

现在你澄清这个问题有点多，我想下面是你想要什么：

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，基本上这允许跳过检查一个密钥的存在和它的内itialisation如果它不存在
目录名称映射到字典键，我认为这可能是一个很好的功能，因为键被哈希，并且您将能够以比列表更快的方式检索信息。您可以访问main_dict['dir2']['alpha']['beta']表格中的层次结构...
请注意.../delta和之间的差异。我认为这有助于你快速区分你的叶子是一个目录还是一个文件。

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

来源

2011-12-13 22:03:19 mac

看起来不错，我会检查出来，告诉你它是否工作 – cwoebker

好吧感谢这有助于很多，并正常工作。我可能会改变我索引文件的方式，所以我可以使所有基于它的效率更高。但是，非常感谢，非常感谢！ – cwoebker

@cwoebker - 没问题，开心帮忙！祝你好运！ – mac

我不是你有什么VS你需要什么（它很可能有助于提供一些你有太慢代码的）完全清楚，但你可能应该只是休息将你的路径命名为dirnames和basenames，然后使用专门制作的类或至少一个列表或词典的层次结构来构建树。然后各种遍历应该允许你几乎以任何你需要的方式序列化。

至于性能问题，你考虑过使用Pypy，Cython还是Shedskin？我有一个重复数据删除备份系统，我一直在努力工作，可以在Pypy或Cython上运行相同的代码;在Pypy上运行它实际上胜过Cython增强版本（在32位上稍多一点，在64位上稍多）。我很想比较棚边皮，但它显然不能穿过棚边皮/边界皮。

另外，当您遇到性能问题时，性能分析是必须的 - 至少，如果您已经选择了合适的算法。

来源

2011-12-13 07:22:30 dstromberg

Cython计划在稍后。 – cwoebker

首先，“很HIGHT性能”和“巨蟒”不拌匀。如果您正在寻找的是将性能优化到极致，切换到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个文件，并且迭代次数这意味着在1秒内你可以处理一个约100万个文件的树。现在...除非你在谷歌工作，这对我来说似乎是可以接受的结果。相反，当我开始写这个答案时，我点击了我的主80Gb HD根目录下的“属性”选项[这应该是给我使用C代码的文件数量]。几分钟后，我在50GB左右，300000个文件...

HTH！ :)

来源

2011-12-13 07:56:27 mac

这确实很快，但与我无关问题，我需要用正则表达式或其他东西来分析我所有的路径，然后得到一个像你在输入中使用的树结构 – cwoebker

@cwoebker - 那么你应该澄清一下你的问题，就像现在一样，不清楚你的输入是什么，预期的输出，这也有助于知道你是否可以访问文件系统，并且可以从中读取文件名，或者如果你必须使用输入你希望将作为例证:) – mac

我添加了示例输入...我可以访问文件系统。在项目中，我有一个redis实例中的文件索引，我从那里读取路径，所以我不想再次访问文件 – cwoebker

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

回答

相关问题