폴더 검색 알고리즘

Question

이 질문에 대한 일반적인 질문이 있거나이 질문에 대한 답을 얻지 못하면 확실하지 않지만 DB 연결 레코드를 생성하기위한 의사 코드 접근 방법을 찾고 있습니다 이미지 파일이 들어있는 폴더 구조에서.

본질적으로

+-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

차종과 모델부터 연도 별 차량에 대한 가능한 이미지를 나타냅니다 :

나는 일련의 폴더, folllows 같은 구조를 가지고 알파를 Romeo, Model : 145)는 다양한 트림이나 버전으로 제공됩니다. 각 트림 또는 버전은 동일하게 보일 것이지만 연료 유형 또는 엔진 용량에 차이가 있다고 말하는 다수의 차량에서 발견 될 수 있습니다.

중복을 저장하려면 위의 폴더 구조가 기본 폴더를 사용하고 이미지는 2000 년 이후의 기본 버전으로 표시됩니다. 각 버전에 대한 링크 테이블을 만들 필요가 있습니다 - 이미지를 우선할지 여부 또는 기본 버전을 사용할지 여부를 기반으로 ...

예를 들어, version_1에는 이미지 파일이 없으므로 2000 년부터 2009 년까지 기본 이미지에 대한 링크를 만듭니다.

버전 2 다른 한편으로는 버전 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

여기 파이썬 의사 코드는 실행 파일에 매우 가깝습니다 (실제 작성을 수행하는 writerow 함수에 적합한 가져 오기와 def가 필요합니다. 중간 파일, DB, 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 년에 변경되고 2001 년과 2005 년에 버전 1이 변경되면 어떻게 될까요? 버전 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(... 라인은 다음과 같습니다 파이썬에서이 과정이 새로운 딕셔너리를 합병하게하는 것을 의미한다 (A 딕셔너리는 일반적인 매핑 될 것이다 default_version 및 years_dict의 합계 또는 병합 인 일반적으로 해시 맵이라고도 함)하지만 키가 모두 해당 키에있는 경우 years_dict의 값이 우선적으로 적용됩니다. 현재있는 연도의 주요 조건을 충족합니다 (즉, 파일이 변경된 연도).

그 후에는 명백한 항해 중입니다. anydict.pop (somekey)는 키에 해당하는 값을 반환합니다 (또한 anydict에서 제거합니다). min (anydict)는 사전의 최소 키를 리턴합니다. merged[max_year + 1] = None의 "센티넬"관용구에 주목하십시오. "최대 하나 이후의 하나"라는 연도는 항상 바뀌는 연도 (더미 자리 표시 자 값 없음)로 간주되므로 마지막 행 세트가 항상 기록됩니다 적절하게 (최대 연도는 max_year + 1 - 1, 즉 정확히 max_year).

이 알고리즘은 최대한 효율적이지는 않지만 간단합니다! 우리는 min(merged)을 반복하여 O (N square)로 만들고 있습니다 - 나는 각각 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에 넣어집니다 (그래서 약간의 최적화를 위해 루프 바깥에 있습니다). 이 최적화 된 버전 (근본적으로 약간 더 높은 수준의 추상화에서 작동하기 때문에)이 이전 버전보다 더 작고 간단하다는 것을 알면 재밌습니다.