python - 搜索目录名具有特定模式的文件

Question

假设我们有 100k 个目录和 1M 个文件，其结构存储在如下列表中:

DIRS = ['C:\\', 'C:\\LAB\\', 'C:\\ABB\\', 'C:\\CDA\\', 'C:\\EABZ\\', 'C:\\CDA\\FOO\\']
FILES = [['a.txt', 2], ['b.txt', 3], ['c.txt', 3], ['r.txt', 1], 
         ['s.txt', 1], ['k.txt', 0], ['m.txt', 4]]   # [filename, dir_index], for 
                                                     # example, a.txt is here: C:\ABB\a.txt

现在我想搜索其目录名称包含AB的文件。我在这里看到的唯一方法如下。

• (1) 首先获取包含AB的DIRS索引:

  I = [i for i in range(len(DIRS)) if 'AB' in DIRS[i]]          # here [1, 2, 4]
                                                                # but can be of size 1000
  

  我们只在 DIRS 上循环一次，即 100k，这样就可以了。

• (2) 现在我们需要循环 I(例如，可以是 1000)和 FILES(例如 100 万)，并且 < strong>这太多了，因为 1000 * 1M = 10 亿次操作:

  FOUND_FILES = []
  for i in I:
      for f in FILES:
          if f[1] == i:
              FOUND_FILES.append(f)
  

这操作太多了! 如何在保留DIRS/FILES数据结构的同时进行更有效的研究？(如果100%完全不可能，我应该使用哪种其他结构考虑一下？)

<小时/>

注意:(2)的这种替代方案不会加速我认为的任何事情:

for f in FILES:      # we loop over 1M items
    if f[1] in I:    # to test if f[1] is contained in I, we might loop over 1000 items too
        FOUND_FILES.append(f)

Answer 1

如果您创建 FILES ，替代方法的时间复杂度可以降低至 O(n) (其中 n 是 I 的长度)一个集合，而不是原始的 O(n*m)(其中 m 是 I 的长度):

I = {i for i, x in enumerate(DIRS) if 'AB' in x}

集合的重要用途之一是快速成员资格查找； O(1)。

您还可以通过使用列表理解来构建最终的 FOUND_FILES 来获得一些重要的 CPU 时间。列表:

FOUND_FILES = [f for f in FILES if f[1] in I]

<小时/>

如果您通过读取父目录的全部内容来构建文件列表，请使用 os.listdir ，您应该申请 glob.glob 相反，直接根据您的模式构建列表。