Algorithme de recherche de dossier

Question

Je ne sais pas si c'est la question habituelle qui est posée ici, ou si j'obtiendrai des réponses à celle-ci, mais je cherche une approche de pseudo-code pour générer des enregistrements de liaison DB à partir d'une structure de dossiers contenant des fichiers image.

J'ai un ensemble de dossiers, structuré comme 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 
    ... ... ... 

En substance, il représente les images possibles pour les véhicules, par année à partir de 1999.

modèles et les marques (par exemple Marque: Alfa Romeo, modèle: 145) viennent dans diverses garnitures ou versions. Chaque garniture, ou version, peut être trouvée dans un certain nombre de véhicules qui auront la même apparence mais auront des différences de type de carburant ou de cylindrée.

Pour éviter la duplication, la structure de dossiers ci-dessus utilise un dossier par défaut ... Et des images apparaissent pour la version par défaut à partir de 2000. J'ai besoin de produire la table des liens pour chaque version - selon qu'ils ont leurs propres images, ou utilisent la version par défaut ...

Donc par exemple, la version_1 n'a pas de fichiers image, donc je dois faire des liens pour les images par défaut, en commençant en 2000 et continuant jusqu'en 2009.

La version 2 commence par utiliser les images par défaut en 2000, mais utilise deux nouveaux ensembles d'abord pour 2001-2002, puis 2003 -2009. La liste des liens nécessaires sont donc ...

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

(valeur par défaut est juste que - un porte-lieu, et aucun lien sont nécessaires pour cela.)

En ce moment je suis en cours d'exécution à travers les dossiers , la construction de tableaux, puis tailler la graisse à la fin. Je me demandais juste s'il y avait un raccourci, en utilisant une sorte d'approche de traitement de texte? Il y a environ 45 000 dossiers, dont la plupart sont vides :-)

Answer 1

Voici un pseudo-code Python, assez proche de l'exécutable (qui nécessite des importations appropriées et un def pour une fonction d'écriture qui fera l'écriture proprement dite - que ce soit un fichier intermédiaire, DB, CSV, peu importe):

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

Une ambiguïté dans la spécification et l'exemple est de savoir s'il est possible pour le default_version de changer l'ensemble des fichiers dans quelques années - ici, je suppose que n » t se produisent (seules les versions spécifiques changent de cette façon, la version par défaut contient toujours un ensemble de fichiers). Si ce n'est pas le cas, que se passe-t-il si la version par défaut change en années (disons) 1999 et 2003, et en version1 en 2001 et 2005 - quels fichiers la version 1 devrait utiliser pour 03 et 04, les nouveaux dans la version par défaut, ou ceux qu'il a spécifié dans 01?

Dans la version la plus compliquée de la spécification (où default_version et un spécifique peuvent changer, avec le changement le plus récent ayant préséance, et si les deux changent spécifiques et par défaut dans la même année) pour obtenir toute la séquence "next change year", pour chaque version spécifique, en faisant attention à la "fusion de priorité" des séquences d'années de changement pour la version par défaut et spécifique, au lieu de simplement utiliser years (la séquence des changements dans la version spécifique) Je fais ici - et chaque année de changement placée dans la séquence doit être associée à l'ensemble approprié de fichiers bien sûr.Donc, si la spécification exacte peut être exprimée, jusqu'aux cas extrêmes, je peux montrer comment faire la fusion nécessaire en modifiant ce pseudo-code - je préfère ne pas faire le travail jusqu'à ce que les spécifications exactes soient clarifiées, parce que, si les spécifications sont en effet plus simple, le travail serait inutile -)

Modifier: comme un nouveau commentaire précise, les spécifications exactes est en effet le plus complexe, nous avons donc faire faire la fusion appropriée. Ainsi, la boucle à la fin de la réponse simpliste au-dessus des modifications à:

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) 

Le principal changement est la ligne merged = dict(...: en Python, cela signifie faire fusionna une nouvelle dict (un dict est une application générique, serait généralement appelée hashmap dans d'autres langages) qui est la somme, ou la fusion, de default_version et years_dict, mais lorsqu'une clé est présente dans les deux, la valeur de years_dict est prioritaire - ce qui correspond à la condition clé pour une année présente (ie, est une année avec un changement dans les fichiers) dans les deux. Après cela, c'est simple: anydict.pop (somekey) renvoie la valeur correspondant à la clé (et la supprime aussi de anydict); min (anydict) renvoie la clé minimale dans le dictionnaire. Notez l'idiome "sentinel" au merged[max_year + 1] = None: ceci dit que l'année "un après le maximum un" est toujours réputée être une année de changement (avec une valeur fictive de None), de sorte que le dernier ensemble de lignes est toujours écrit correctement (avec une année maximale de max_year + 1 - 1, c'est-à-dire exactement max_year, au choix).

Cet algorithme n'est pas efficace au maximum, juste le plus simple! Nous faisons min(merged) encore et encore, ce qui en fait O (N au carré) - Je pense que nous pouvons nous le permettre parce que chaque merged devrait avoir quelques douzaines d'années de changement tout au plus, mais un puriste grimacerait. Nous pouvons bien sûr présenter une solution O (N logN) - il suffit de trier les années une fois pour toutes et de parcourir cette séquence pour obtenir les valeurs successives pour next_change. Juste pour être complet ...:

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 

Ici sorted donne une liste avec les touches de merged dans l'ordre de tri, et je suis passé à la déclaration for marcher cette liste du début à la fin (et une instruction if ne rien sortir la première fois). La sentinelle est maintenant mise en default_version (donc en dehors de la boucle, pour une autre légère optimisation). C'est marrant de voir que cette version optimisée (essentiellement parce qu'elle fonctionne à un niveau d'abstraction un peu plus élevé) s'avère plus petite et plus simple que les précédentes ;-).