Алгоритм поиска папок

Question

Не уверен, что это обычный вопрос, который задают здесь, или я получу какие-либо ответы на этот, но я ищу псевдокодовый подход к генерации записей, связывающих БД, из структуры папок, содержащих файлы изображений.

У меня есть набор папок, структурированных следующим образом:

+-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 для функции writerow, которая будет выполнять фактическую запись - будь то в промежуточный файл, 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 годах, а версия 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 это означает создание объединенного нового dict (dict - это общее отображение, обычно называемое hashmap на других языках), которое является суммой или слиянием default_version и years_dict, но когда ключ присутствует в обоих из них, значение из years_dict имеет приоритет - который соответствует ключевому условию для текущего года (т. Е. является годом с изменением файлов) в обоих.

После этого все пойдет как по маслу:anydict.pop(somekey) возвращает значение, соответствующее ключу (а также удаляет его из anydict);min(anydict) возвращает минимальный ключ в словаре.Обратите внимание на идиому "страж" в merged[max_year + 1] = None:это говорит о том, что год "один после максимального" всегда считается годом изменения (с фиктивным значением заполнителя None), так что последний набор строк всегда записывается правильно (с максимальным годом 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, чтобы ничего не выводить с первого раза).sentinel теперь помещен в default_version (так что он находится вне цикла, для еще одной небольшой оптимизации).Забавно видеть, что эта оптимизированная версия (в основном потому, что она работает на несколько более высоком уровне абстракции) оказывается меньше и проще предыдущих;-).