文件系统的数据结构

我在内存中存储/缓存文件系统（仅限文件名）以便能够快速研究àla Everything。因此我不想使用操作系统的内置文件搜索GUI。文件系统的数据结构

我做：

import os 
L = [] 
for root,dirs,files in os.walk(PATH): 
    L.append([root, files])

，结果是这样的：

[['D:\\', ['a.jpg', 'b.jpg']], 
... 
['D:\\Temp12', ['test.txt', 'test2.txt']]]

的问题是，做研究需要太多的时间，当L将包含数百万个元素：

query = 'test2' #searching for filename containg this text 
for dir in L: 
    for f in dir[1]: 
     if query in f: 
      print '%s found: %s' % (query, os.path.join(dir[0],f))

事实上，这是一个非常幼稚的搜索，因为它需要浏览ŧ他整个列表找到物品。

如何使查询速度更快？

也许看起来列表并不是正确的数据结构来做全文研究，有没有树状结构？

来源

2016-12-16 Basj

在Python中，我觉得'字典'是你正在寻找的东西！ – Acepcs

@Acepcs：即使我使用字典'{'D：\\'：['a.jpg'，'b.jpg']，...，'D：\\ Temp12'：['test.txt '，'test2.txt']}'，我将不得不迭代所有数千个键/值来进行搜索......你能确切地记住你的想法吗？ – Basj

我的脑海里恰好有一个完整的算法。当你浏览你的操作系统中的目录时，试着制作一个文件名字典，每个键是字母表中的一个字符，每个值都是一个以该字符开头的文件名列表，例如'{'a'： ['a3.jpg'，'ab.jpg']，'b'：['banana.gif'，'bad.jpg']}'，所以通过建立前缀键可以节省大量的时间。如果你的数据量真的很大，你可以构建嵌套的前缀字典，就像在Python中实现的树（在一定程度上） – Acepcs

研究一个列表是O（n）时，在研究的字典摊销O（1）。如果您不需要关联值，请使用集合。

如果您想了解更多关于这一点：https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

在你的情况，我会用套。它会让你的查询更快。

编辑：

你正在做它，检查比赛的每个文件不能更快这样的方式。即使你使用字典，你也要检查每个文件名的匹配。

新的想法：您可以创建所有的文件名作为密钥和根为每个值的字典。这样您可以稍后重新创建完整路径。

现在的想法是创建一个树是每个节点都是一个字母，是每次必做的话（文件名）之间的路径。这可能很难实现，并且结果可能不会更快，这取决于您构建树的方式。

你必须记住要检查每个文件名，并使用列表或字典也不会改变这一点。树/图是我能想到的唯一解决方案。

来源

2016-12-16 08:43:00 iFlo

正如其他评论所述，即使我使用字典'{'D：\\'：['a.jpg'，'b.jpg']，...，'D：\\ Temp12'：['' test.txt'，'test2.txt']}'，我将不得不遍历所有数千个键/值来执行搜索......您能详细说明如何使用'dict'来实现此操作，或者'set'？在我看来，人们必须迭代整个结构才能进行搜索。 – Basj

你可以考虑使用数据库吗？

SQLite提供：memory：option，它只在内存中创建数据库。当然，你可以像其他答案和评论中指出的那样，优化你的算法和数据结构，但是数据库一般都已经非常擅长编制索引，而且你不需要设计类似的东西。

您的表格可能只是一个带有full_path和filename字段的表格，如果您通过文件名索引它，它会很快。这会存储大量冗余信息，因为每个文件都将在full_path中具有完整路径。更好的解决方案是为目录设置一个表格，为文件设置另一个表格，并且仅从文件中引用目录以获取匹配的完整路径。

只是一个想法。

Hannu

来源

2016-12-16 12:29:16 Hannu

文件系统的数据结构

回答

相关问题