为目录中的文件存储查找 table 的高效设计

Question

假设我有三个目录 dir1、dir2 和 dir3，每个目录中有数千个文件。每个文件都有一个没有模式的唯一名称。

现在，给定一个文件名，我需要找到它在三个目录中的哪一个。我的第一个想法是创建一个字典，其中文件名作为键，目录作为值，如下所示：

{'file1':'dir1', 
 'file2':'dir3',
 'file3':'dir1', ... }

但是鉴于只有三个唯一值，这似乎有点多余并且占用了 space。

有没有更好的实现方式？如果我可以在 space 上妥协但需要更快的查找怎么办？

Answer 1

解决这个问题的一个简单方法是直接查询文件系统，而不是将所有文件名缓存在 dict 中。这将节省大量 space，如果只有几百个目录要搜索，速度可能会足够快。

这是一个简单的函数：

def find_directory(filename, directories):
    for directory in directories:
        path = os.path.join(directory, filename)
        if os.path.exists(path):
            return directory

在我的 Linux 系统上，当搜索大约 170 个目录时，第一次搜索大约需要 0.3 秒，之后只需要大约 0.002 秒。这是因为 OS 进行文件缓存以加速重复搜索。但请注意，如果您使用 dict 在 Python 中执行此缓存，您仍然需要支付类似的初始成本。

当然，随后的 dict 查找会比直接查询文件系统更快。但你真的需要额外的速度吗？对我来说，对于大多数用途来说，千分之二秒似乎很容易 "fast enough"。而且您可以获得永远不需要刷新文件缓存的额外好处（因为 OS 会为您完成）。

PS:

我可能应该指出上述时间是最坏情况：也就是说，我首先删除了所有系统文件缓存，然后搜索了一个文件名在最后一个目录中。

Answer 2

您可以将索引存储为集合字典。它可能更节省内存。

index = {
    "dir1": {"f1", "f2", "f3", "f4"},
    "dir2": {"f3", "f4"},
    "dir3": {"f5", "f6", "f7"},
}

filename = "f4"
for dir, files in index.iteritems():
    if filename in files:
         print dir

说到成千上万的文件，您几乎看不出此方法与您的倒排索引有任何区别。

此外，python 中的可重复字符串可以 interned 以节省内存。有时 CPython 会自己实习短字符串。

为目录中的文件存储查找 table 的高效设计

Efficient design to store lookup table for files in directories

python

lookup

dictionary

file-search