Algorithme de recherche de dossier

Question

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

J'ai un ensemble de dossiers, structurés comme suit :

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

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

Marques et modèles (par ex.Faire:Alfa Roméo, modèle :145) sont disponibles en différentes finitions ou versions.Chaque version ou version peut être trouvée dans un certain nombre de véhicules qui se ressemblent mais présentent des différences dans le type de carburant ou la cylindrée du moteur.

Pour éviter la duplication, la structure de dossiers ci-dessus utilise un dossier par défaut...Et les images apparaissent pour la version par défaut à partir de 2000.Je dois produire le tableau des liens pour chaque version - selon qu'elles ont leurs propres images de remplacement ou si elles utilisent la version par défaut...

Ainsi, par exemple, la version_1 n'a pas de fichiers image, je dois donc créer des liens vers les images par défaut, à partir de 2000 et jusqu'en 2009.

La version 2, en revanche, utilise les images par défaut en 2000, mais utilise ensuite deux nouveaux ensembles, d'abord pour 2001-2002, puis 2003-2009.La liste des liens requis est 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
...

(La valeur par défaut n'est que cela : un espace réservé, et aucun lien n'est requis pour cela.)

En ce moment, je parcours les dossiers, je crée des tableaux, puis je réduis le gras à la fin.Je me demandais simplement s'il existait un raccourci, 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 pseudocode Python, assez proche de l'exécutable (nécessite des importations appropriées et une définition pour une fonction writerow qui effectuera l'écriture réelle - que ce soit dans 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 default_version de modifier l'ensemble de fichiers dans certaines années - ici, je suppose que cela n'arrive pas (seules les versions spécifiques changent de cette façon, la version par défaut comporte toujours un ensemble de fichiers).

Si ce n'est pas le cas, que se passe-t-il si la version par défaut change au cours des années (disons) 1999 et 2003, et que la version 1 change en 2001 et 2005 - quels fichiers la version 1 doit-elle utiliser pour 03 et 04, les nouveaux dans la version par défaut , ou ceux spécifiés en 01 ?

Dans la version la plus compliquée de la spécification (où la version par défaut et une version spécifique peuvent changer, la modification la plus récente étant prioritaire, et si la version spécifique et la version par défaut changent la même année, la version spécifique prend la priorité), il faut obtenir tous les séquence "prochaine année de changement", pour chaque version spécifique, par une "fusion prioritaire" minutieuse des séquences d'années de changement pour la version par défaut et la version spécifique, au lieu de simplement utiliser years (la séquence de changements dans la version spécifique) comme je le fais ici - et chaque année de changement placée dans la séquence doit bien sûr être associée à l'ensemble de fichiers approprié.

Donc, si la spécification exacte peut être exprimée, jusque dans les moindres cas, je peux montrer comment effectuer la fusion nécessaire en modifiant ce pseudocode -- je préfère ne pas faire le travail jusqu'à ce que les spécifications exactes soient clarifiées, car, si le les spécifications sont effectivement plus simples, le travail serait inutile !-)

Modifier:comme l'a précisé un nouveau commentaire, les spécifications exactes sont en effet les plus complexes, nous devons donc procéder à la fusion de manière appropriée.Ainsi, la boucle à la fin de la réponse simpliste ci-dessus se transforme en :

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 changement clé est le merged = dict(... doubler:en Python, cela signifie fusionner un nouveau dict (un dict est un mappage générique, serait généralement appelé 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 a la priorité - ce qui répond à la condition clé d'une année présente (c'est-à-dire une année avec un changement dans les fichiers) dans les deux cas.

Après, c'est tout simple :anydict.pop(somekey) renvoie la valeur correspondant à la clé (et la supprime également de anydict) ;min(anydict) renvoie la clé minimale dans le dictionnaire.Notez l'expression "sentinelle" à merged[max_year + 1] = None:cela dit que l'année "une après la maximale" est toujours considérée comme une année de changement (avec une valeur d'espace réservé factice de Aucun), de sorte que le dernier ensemble de lignes soit toujours écrit correctement (avec une année maximale de max_year + 1 - 1, c'est-à-dire exactement max_year, comme voulu).

Cet algorithme n’est pas d’une efficacité maximale, mais simplement le plus simple !Faisaient 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 dizaines d'années de changement au maximum, 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 de 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 clés de merged dans l'ordre trié, et je suis passé au for instruction pour parcourir cette liste du début à la fin (et une instruction if pour ne rien afficher du premier coup).La sentinelle est maintenant mise dans default_version (elle est 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 légèrement supérieur) s'avère plus petite et plus simple que les précédentes ;-).