文件夾搜索算法

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（因此它在循環之外，用於另一個輕微的優化）。看到這個優化版本（主要是因爲它在稍微高一點的抽象層次上工作）變得比以前的版本更小更簡單，這很有趣---)。