algoritmo di ricerca delle cartelle

Question

Non so se questo è il solito tipo di domanda che viene chiesto da queste parti, o se vado a prendere eventuali risposte a questo, ma sto cercando un approccio pseudo-codice per la generazione di DB record di collegamento da una cartella struttura che contiene i file di immagine.

Ho una serie di cartelle, strutturato come 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
  ...  ... ...  

In sostanza, essa rappresenta le possibili immagini per veicoli, per anno a partire dal 1999.

marche e modelli (ad esempio Costruttore: Alfa Romeo, modello: 145) sono disponibili in varie finiture o le versioni. Ogni assetto, o versione possono essere trovati in un certo numero di veicoli che avranno lo stesso aspetto, ma hanno detto differenze nel tipo di combustibile o di cilindrata.

Per salvare la duplicazione, la struttura delle cartelle di cui sopra si avvale di una cartella di default ... E le immagini appaiono per la versione di default dal 2000 in poi. Ho bisogno di produrre la tabella di link per ogni versione - a seconda che l'hanno le loro immagini di primaria importanza, o se fare uso della versione di default ...

Così, per esempio, VERSION_1 non ci sono file di immagini, quindi ho bisogno di fare i collegamenti per le immagini predefinite, a partire dal 2000 e continua fino al 2009.

La versione 2 d'altra parte inizia con le immagini predefinite nel 2000, ma poi si avvale di due nuovi set prima per il periodo 2001-2002, e poi 2003-2009. L'elenco dei collegamenti richiesti sono quindi ...

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

(di default è proprio questo -. Un posto da titolare, e senza collegamenti sono necessari per esso)

Al momento sto correndo attraverso le cartelle, la costruzione di array, e poi tagliare il grasso alla fine. Mi stavo chiedendo se ci fosse una scorciatoia, utilizzando una sorta di approccio di elaborazione del testo? Ci sono circa 45.000 cartelle, molti dei quali sono vuoti: -)

Answer 1

Ecco alcuni pseudocodice Python, abbastanza vicino a eseguibili (ha bisogno di importazioni adatti e un def per una funzione writerow che farà lo scrittura vera e propria - che si tratti di un file intermedio, DB, CSV, a prescindere):

# 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)

Un'ambiguità nelle specifiche e l'esempio è se è possibile per il default_version per cambiare il set di file in alcuni anni - qui, sto supponendo che non accada (solo le versioni specifiche cambiano in questo modo, la versione di default sempre porta un set di file).

Se questo non è il caso, che cosa succede se i cambiamenti di versione di default in anni (diciamo) 1999 e il 2003, e Version1 modifiche nel 2001 e nel 2005 - quali file dovrebbero versione 1 uso per il 03 e 04, quelli nuovi in la versione di default, o di quelli che specificato nel 01?

Nella versione più complicata delle specifiche (in cui sia default_version e uno specifico può cambiare, con il più recente cambiamento che ha la precedenza, e se sia il cambiamento specifico e predefinito nello stesso anno poi la specifica prevalgono) uno ha bisogno di ottenere tutta la sequenza "successivo cambio l'anno", per ogni versione specifica, da un'attenta "fusione priorità" delle sequenze di anni di cambiamento per impostazione predefinita e la versione specifica, invece di utilizzare years (la sequenza di cambiamenti nella versione specifica) come ho fare qui -. ed ogni anno il cambiamento posto in sequenza deve essere associato con l'insieme appropriato di file, naturalmente,

Quindi, se le specifiche esatto può si prega di essere espressa, fino ai casi d'angolo, posso mostrare come fare la fusione necessaria modificando questo pseudocodice - io preferirei non farei il lavoro fino a quando le specifiche esatte sono chiarite, perché , se le specifiche sono infatti più semplici, l'opera sarebbe non necessarie -!)

Modifica : come un nuovo commento chiarito, le specifiche esatte è infatti la più complessa, quindi abbiamo fare fare la fusione in modo appropriato. Così il ciclo al termine della risposta semplicistica sopra modifiche:

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)

Il cambiamento principale è la linea merged = dict(...: in Python, questo significa fare fuse un nuovo dict (un dict è una mappatura generica, sarebbe tipicamente chiamato HashMap in altre lingue), che è la somma, o unire, di default_version e years_dict, ma quando una chiave è presente in entrambi questi, il valore da years_dict ha la precedenza - che soddisfa la condizione chiave per un anno che è presente (ad esempio, è un anno con un cambio di file) sia

Dopo che è rose e fiori: anydict.pop (somekey) restituisce il valore corrispondente alla chiave (e anche lo rimuove dal anydict); min (anydict) restituisce la chiave minima nel dizionario. Si noti l'idioma "sentinella" in merged[max_year + 1] = None: questo dice che l'anno "uno dopo l'uno max" è sempre considerato un cambiamento anni (con un valore segnaposto fittizio di None), in modo che l'ultima serie di righe è sempre scritto correttamente (con un anno massimo di max_year + 1 - 1, che è, esattamente max_year, se lo desideri).

Questo algoritmo non è massimamente efficiente, solo più semplice! Stiamo facendo min(merged) più e più volte, il che rende O (N al quadrato) - Penso che possiamo permettercelo perché ogni merged dovrebbe avere qualche cambiamento anni dozzina al massimo, ma un purista sarebbe sussultare. Possiamo naturalmente presentare una soluzione (N log N) O - basta ordinare gli anni una volta per tutte e camminare quella sequenza per ottenere i valori successivi per next_change. Solo per completezza ...:

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

Ecco sorted fornisce un elenco con le chiavi di merged in modo ordinato, e ho acceso la dichiarazione for a camminare quella lista dall'inizio alla fine (e un if per niente uscita la prima volta attraverso). La sentinella è ora messo in default_version (in modo che sia al di fuori del ciclo, per un altro lieve ottimizzazione). E 'divertente vedere che questa versione ottimizzata (essenzialmente perché funziona a un livello leggermente più alto di astrazione) turnos fuori per essere più piccolo e più semplice rispetto a quelli precedenti; -).