文件夹搜索算法

Question

不知道这是在这里被问到的常见问题，或者我会得到任何答案，但我正在寻找一种伪代码方法来生成数据库链接记录来自包含图像文件的文件夹结构。

我有一组文件夹，结构为folllows：

+-make_1/ 
    | +--model_1/ 
    | +-default_version/ 
    | | +--1999 
    | | +--2000 
    | | | +--image_01.jpg 
    | | | +--image_02.jpg 
    | | | +--image_03.jpg 
    | | | ... 
    | | +--2001 
    | | +--2002 
    | | +--2003 
    | | ... 
    | | +--2009 
    | +--version_1/ 
    | | +--1999 
    | | ... 
    | | +--2009 
    | +--version_2/ 
    | | +--1999 
    | | +--2000 
    | | +--2001 
    | | | +--image_04.jpg 
    | | | +--image_05.jpg 
    | | | +--image_06.jpg 
    | | | ... 
    | | +--2002 
    | | +--2003 
    | | | +--image_07.jpg 
    | | | +--image_08.jpg 
    | | | +--image_09.jpg 
    | | ... 
    | | +--2009 
    ... ... ... 

从本质上讲，它代表了车辆可能图像，通过一年在1999年

品牌和型号的开始（如品牌：阿尔法罗密欧，型号：145）进来各种修剪或版本。每种装饰或版本都可以在许多车辆中找到，这些车辆看起来相同，但是在燃料类型或发动机容量方面存在差异。

为了节省重复，上面的文件夹结构使用了默认文件夹...并且图像显示为从2000年开始的默认版本。我需要为每个版本生成链接表 - 根据是否有自己的压倒性图像，或者是否使用默认版本...

因此，例如，version_1没有图像文件，所以我需要在2000年开始并且一直持续到2009年，创建链接以用于默认图像。

另一方面，版本2在2000年开始使用默认图像，但之后在2001-2002中使用两个新套装，然后在2003年使用两套新套装-2009。因此所需的链接列表是...

version start  end file_name 
======= ===== ===== ========= 
version_1 2000 2009 image_01.jpg 
version_1 2000 2009 image_02.jpg 
version_1 2000 2009 image_03.jpg 
... 
version_2 2000 2001 image_01.jpg 
version_2 2000 2001 image_02.jpg 
version_2 2000 2001 image_03.jpg 
version_2 2001 2003 image_04.jpg 
version_2 2001 2003 image_05.jpg 
version_2 2001 2003 image_06.jpg 
version_2 2003 2009 image_07.jpg 
version_2 2003 2009 image_08.jpg 
version_2 2003 2009 image_09.jpg 
... 

（默认就是这样 - 一个占位符，并没有链接都需要它。）

目前我在文件夹中运行，建立数组，然后在最后修剪脂肪。我只是想知道是否有捷径，使用某种文本处理方法？大约有45,000个文件夹，其中大部分都是空的:-)

Answer 1

下面是一些Python伪代码，非常接近可执行文件（需要合适的导入和def作为编写器函数，它将执行实际的写入 - 无论是对于中间文件，数据库，CSV，等等）：

的规范，例如

# first, collect all the data in a dict of dicts of lists 
# first key is version, second key is year (only for non-empty years) 

tree = dict() 
for root, dirs, files in os.walk('make_1/model_1'): 
    head, tail = os.path.split(root) 
    if dirs: 
     # here, tail is a version 
     tree[tail] = dict 
    elif files: 
     # here, tail is a year 
     tree[os.path.basename(head)][tail] = files 

# now specialcase default_version 
default_version = tree.pop('default_version') 
# determine range of years; rule is quite asymmetrical: 
# for min, only years with files in them count 
min_year = min(d for d in default_version if default_version[d]) 
# for max, all years count, even if empty 
max_year = max(default_version) 

for version, years in tree.iteritems(): 
    current_files = default_version[min_year] 
    years.append(max_year + 1) 
    y = min_year 
    while years: 
     next_change = min(years) 
     if y < next_change: 
      for f in current_files: 
       writerow(version, y, next_change-1, f) 
     y = next_change 
     current_files = years.pop(y) 

一个不确定度是它是否是可能的default_version更改设置文件在某些​​年份 - 在这里，我假设没有按”不会发生（只有特定的版本以这种方式改变，默认版本总是携带一组文件）。

如果不是这种情况，如果默认版本在年份（比如说）1999和2003中发生变化，并且版本1在2001和2005中发生变化 - 版本1在03和04中使用哪些文件，在默认版本中，还是在01中指定的那些？

在规范最复杂的版本中（其中default_version和特定的版本都可以更改，最近的更改优先，并且如果特定和默认更改在同一年，则具体优先）需要为每个特定版本获得所有“下一个变更年”序列，方法是对默认和特定版本的变更年份序列进行小心的“优先合并”，而不是仅使用years（特定版本中的变更序列）作为我在这里做的 - 当然，每个更改年份都必须与适当的文件集相关联。因此，如果确切的规格可以表达出来，直到角落的情况下，我可以通过修改这个伪代码来演示如何完成所需的合并 - 我宁愿不做工作，直到确切的规格被澄清，因为，如果规格确实是简单的，工作是不必要的 - ）

编辑：作为一个新的评论澄清，确切的规格的确是最复杂的一个，所以我们做的做适当的合并。因此，在这简单的答案的上述变化对最终的循环：

for version, years_dict in tree.iteritems(): 
    # have years_dict override default_version when coincident 
    merged = dict(default_version, **years_dict) 
    current_files = merged.pop(min_year) 
    merged[max_year + 1] = None 
    y = min_year 
    while merged: 
     next_change = min(merged) 
     for f in current_files: 
      writerow(version, y, next_change-1, f) 
     y = next_change 
     current_files = merged.pop(y) 

关键的变化是merged = dict(...线：在Python，这意味着使合并的新字典（一个字典是一个通用的映射，将通常称为其他语言的散列表），它是default_version和years_dict的总和或合并，但是如果两个键都存在键，则years_dict的值优先 - 这符合存在一年的关键条件（即，文件更改的一年）。在此之后，它是一帆风顺的：anydict.pop（somekey）返回与该键相对应的值（并将其从anydict中移除）; min（anydict）返回字典中的最小密钥。请注意0​​处的“定位”成语：这表示“最大一个之后”的年份始终被视为变更年份（虚拟占位符值为“无”），以便始终写入最后一组行（最大年份为max_year + 1 - 1，也就是max_year）。

该算法不是最高效的，只是最简单！我们一遍又一遍地做min(merged)，使它成为O（N平方） - 我认为我们可以负担得起，因为每个merged最多应该有几十个变更年，但是一个纯粹主义者会变得迟钝。我们当然可以提供一个O（N logN）解决方案 - 只需按年排序一次，然后按顺序排列以获得next_change的连续值。只是为了完整性...：

default_version[max_year + 1] = None 

for version, years_dict in tree.iteritems(): 
    merged = dict(default_version, **years_dict) 
    for next_change in sorted(merged): 
     if next_change > min_year: 
      for f in merged[y]: 
       writerow(version, y, next_change-1, f) 
     y = next_change 

这里sorted给出了的merged按排序顺序按键名单，我已经切换到for语句在这个列表里从开始到结束（和if语句第一次输出什么都没有）。现在将标记置于default_version（因此它在循环之外，用于另一个轻微的优化）。看到这个优化版本（主要是因为它在稍微高一点的抽象层次上工作）变得比以前的版本更小更简单，这很有趣---)。