Quelle est la manière la plus efficace de stocker ces données?

9

Je suis en charge de réécrire un ancien code VB. Je comprends comment cela fonctionne, mais j'ai l'impression qu'il existe un moyen beaucoup plus efficace de faire ce qu'ils ont fait. Je ne peux pas comprendre ce que c'est. Voici un exemple artificiel qui, en termes d'exigences de données, est vraiment similaire à ce que je dois faire.

L'utilisateur doit choisir le fabricant, la marque, le modèle et la couleur de sa voiture dans une interface graphique. J'ai un gros fichier texte qui ressemble à ceci:

Ford Truck F150 red
Ford Truck F150 blue
Ford Truck F150 black
Ford Truck F150 silver
Ford Truck F250 red
Ford Truck F250 green
Ford Sedan Taurus red
Ford Sedan Taurus green
Ford Sedan Taurus white
Ford...
...

Subaru SUV Forester blue
Subaru SUV Forester red
Subaru SUV Outback Black
Subaru SUV Outback Green
Subaru SUV Outback Blue
Subaru SUV Outback Red
Subaru...
...

etc.

Donc, si la première sélection est Subaru, la deuxième case (marque) ne devrait pas avoir d'option pour sélectionner Truck car aucun des Subarus n'est un camion. De même, s'ils sélectionnent Ford, Sedan et Taurus, la dernière case (couleur) ne devrait pas afficher une option pour sélectionner le bleu. Ou noir. Ou autre chose que du rouge, du vert ou du blanc.

Les personnes qui ont écrit le code avant moi ont trouvé ceci (en python-y psuedocode):

def getValidOptions():
    items = []
    for i from 0 to numRows:
        options = getLine().split()
        if selectingManufacturer:
            if options[0] not in items:
                items.append(options[0])
        else if selectingMake:
            if selectedManufacturer == options[0] and options[1] not in items:
               items.append(options[1])
        else if selectingModel:
            if selectedManufacturer == options[0] and selectedMake == options[1] and options[2] not in items:
                items.append(options[2])
        else if selectingColor:
            if selectedManufacturer == options[0] and selectedMake == options[1] and selectedModel == options[2] and options[3] not in items:
                items.append(options[3])
    return items

Je pense que c'est tout simplement hideux, à la fois au niveau de l'algorithme et au niveau de la syntaxe. D'une part, il analyse l'ensemble du fichier, alors qu'il n'a besoin de lire que quelques lignes s'il est bien fait. Pour rendre cela encore plus inefficace, mes données réelles ont 6 options à sélectionner, plutôt que seulement 4. Cela stocke également plus de données que nécessaire, compte tenu de la quantité de duplication des données.

Je cherche soit une manière différente de stocker les données dans le fichier, soit une façon différente de les analyser pour rendre la getValidOptionsfonction à la fois plus jolie et plus efficace. Existe-t-il des moyens de le faire?

James
la source
2
pourquoi ne pas utiliser une base de données?
Tulains Córdova

Réponses:

6

Toutes les autres réponses que j'ai lues semblent ignorer deux règles très fondamentales du développement logiciel:

  • clarifier d'abord les exigences (en particulier les exigences de performances et de stockage)

  • Restez simple, stupide (voir KISS )

Vous avez écrit "le fichier texte est grand", mais vous n'avez pas écrit trop grand, donc je suppose qu'il n'y a rien de mal à sa taille, sauf votre intuition. Donc, si le chargement du fichier ne prend pas trop de temps et que votre service informatique ou quelqu'un d'autre ne se plaint pas de l'espace disque gaspillé et que personne ne se plaint de problèmes de maintenance du fichier, laissez le format du fichier tel quel - ne sous-estimez pas le valeur de simplicité.

Vous vous plaignez également de l'efficacité de l'algorithme, qui n'est en fait pas aussi efficace qu'il pourrait l'être, mais il a un très gros avantage: il est simple et cérébral et fonctionne. Aussi, tant qu'il est suffisamment efficace, n'appliquez aucune optimisation prématurée.

Supposons donc que le programme fonctionne assez rapidement, ce que vous devez d'abord demander, comment améliorer le code en termes de simplicité et de principe DRY? Et c'est en effet un point qui devrait être amélioré, puisque le code actuel n'est pas SEC. Dans votre exemple, il apparaît quatre fois le même test de bloc de code si les options des "niveaux supérieurs" correspondent à la ligne actuelle, ce qui entraîne quatre fois le même type d'appel "d'ajout" (dans votre code réel, la répétition se produit au moins six fois, comme vous l'avez écrit). Vous pouvez facilement éviter cela en introduisant un niveau de sélection numérique ou en passant les options déjà sélectionnées dans une liste ordonnée. En utilisant votre pseudo-code, cela conduit à quelque chose dans le sens de

# selectedOptions is a list, containing either nothing, or "selectedManufacturer"
# or [selectedManufacturer, selectedMake], ..., and so on
def getValidOptions(selectedOptions):
    items = []
    level = selectedOptions.size()
    for i from 0 to numRows:
        options = getLine().split()
        if selectedOptions == options[0:level-1] and options[level] not in item:
            items.append(options[level])
    return items

Il s'agit donc essentiellement du même algorithme sans code répété.

Puisqu'il est évident getValidOptionsqu'il faut l'appeler plus d'une fois (au moins une fois par niveau), je suggère d'appliquer une seule optimisation (si ce n'est pas déjà le cas): assurez-vous que la getLinefonction extrait ses données de la mémoire principale et ne lire le fichier depuis le disque encore et encore.

Doc Brown
la source
Vous souhaitez déplacer "level = selectedOptions.size ()" avant la boucle numRows.
AI Breveleri
6

Eh bien, les données dont vous disposez ont une structure arborescente, où pour chaque fabricant, vous avez un arbre de modèles et pour chaque modèle, vous avez une couleur (et ainsi de suite).

Ainsi, vous pouvez séparer le processus de ces données en deux étapes:

  1. Après toute mise à jour du fichier texte, vous devez traiter ce fichier et le convertir en arborescence.
  2. Lors du chargement de l'application, vous ne chargez que l'arborescence.

La structure arborescente peut être implémentée avec ce qu'on appelle un hachage , un tableau associatif ou un dictionnaire dans des langages comme Java, PHP, Javascript ou Python. Avec cette structure, vous avez:

  • Les premières clés sont les fabricants.
  • Leurs valeurs ne sont qu'un autre hachage ou dictionnaire où chaque clé est le modèle.
  • Leurs valeurs sont les couleurs. Ou une autre structure gardant dans leurs clés le troisième niveau et comme valeur le quatrième niveau.
  • Etc...

Selon votre langage de programmation, cela peut être implémenté plus rapidement ou plus lentement. Par exemple:

  • C # : vous pouvez implémenter une structure arborescente 1 , puis la marquer comme sérialisable.
  • VB.Net : vous pouvez générer l'arborescence dans une seule application et la sérialiser dans un fichier.
    • Pour cela, quelque chose comme Runtime.Serialization.Formatters.Binary.BinaryFormatterpourrait être utile, mais je ne suis pas un expert en sérialisation avec VB.Net.
  • Javascript : vous pouvez générer l'arborescence dans un fichier JSON, qui doit être chargé à chaque fois que l'application est chargée.
  • PHP : vous pouvez générer une version sérialisée de la structure de données arborescente, ou vous pouvez également charger un JSON.
  • Java : vous pouvez sérialiser cette structure de données, en créant un Classqui implémente l'interface java.io.Serializable.

Références :

1: https://dvanderboom.wordpress.com/2008/03/15/treet-implementing-a-non-binary-tree-in-c/
- Une explication complète sur l'implémentation d'un arbre en C #.
- Recherchez un commentaire dans lequel quelqu'un vous demande de sérialiser cet objet et la réponse à ce commentaire.

Nicolás
la source
1
Oui, j'avais pensé à utiliser un arbre, mais je ne sais pas si c'est la meilleure idée car il n'y a pas de structure arborescente intégrée (que je sache) en C #, et le projet est assez petit donc je ne sais pas si cela vaudrait la peine de passer beaucoup de temps à travailler sur une tree with an arbitrary number of nodesimplémentation.
James
Pour l'instant, je ne suis pas un expert en C #, mais au moins dans d'autres langages comme Java et PHP, vous pouvez avoir une sorte de dictionnaires, où chaque clé peut avoir comme valeur un autre dictionnaire.
Nicolás
J'ai mis à jour ma réponse. Voyez ce que vous pensez de l'alternative de hachage ou de dictionnaire. J'ai également ajouté une référence avec un article intéressant.
Nicolás
3

Une façon simple de stocker les données consiste simplement à les placer dans une base de données SQLite. SQLite, contrairement à la plupart des bases de données SQL, est bien adapté pour une utilisation en tant que format de fichier d'application. Cette approche présente plusieurs avantages:

  1. Pas besoin de coder un sérialiseur ou un désérialiseur.
  2. Le fichier est modifiable et interrogeable par de nombreux programmes existants.
  3. Le désordre conditionnel que vous mentionnez dans la question est évité. Pour limiter les listes déroulantes, générez une simple clause where sur chaque colonne (par exemple, select distinct model where manufacturer='ford' and color = 'red').

Cela vous oblige à apprendre SQL, mais évite d'avoir à apprendre un format de fichier personnalisé.

Brian
la source
1

Je suppose que vous pouvez accéder de manière aléatoire aux lignes du fichier et donc traiter le fichier comme un tableau d'enregistrements. Si vous ne pouvez pas accéder au hasard aux lignes, l'algorithme que vous avez est le meilleur que vous puissiez faire.

Pour un accès plus rapide, stockez les données dans 6 fichiers, où chaque fichier est un index dans le suivant.

Il existe de nombreuses façons de créer des indices de fichiers plats. J'utilise généralement une plage d'indices. Au fur et à mesure que l'utilisateur effectue chaque sélection, utilisez la plage pour limiter la lecture du fichier suivant.

Voici comment je créerais les indices pour les exemples de données que vous avez fournis.

Bien sûr, le fichier doit être trié. J'ai numéroté les lignes à titre d'illustration; les numéros de ligne ne doivent pas apparaître dans le fichier.

--| file3.dat |--
 0 Ford Truck F150 red
 1 Ford Truck F150 blue
 2 Ford Truck F150 black
 3 Ford Truck F150 silver
 4 Ford Truck F250 red
 5 Ford Truck F250 green
 6 Ford Sedan Taurus red
 7 Ford Sedan Taurus green
 8 Ford Sedan Taurus white
 9 Subaru SUV Forester blue
10 Subaru SUV Forester red
11 Subaru SUV Outback Black
12 Subaru SUV Outback Green
13 Subaru SUV Outback Blue
14 Subaru SUV Outback Red

Pour créer le premier index, créez un enregistrement pour chaque combinaison unique des trois premiers champs du fichier. Dans chaque enregistrement, stockez les premier et dernier numéros de ligne dans lesquels cette combinaison apparaît.

--| file2.dat |--
 0 Ford Truck F150       0   3
 1 Ford Truck F250       4   5
 2 Ford Sedan Taurus     6   8
 3 Subaru SUV Forester   9  10
 4 Subaru SUV Outback   11  14

Le deuxième index est construit de manière similaire, en utilisant les deux premiers champs du premier index.

--| file1.dat |--
 0 Ford Truck        0   1
 1 Ford Sedan        2   2
 2 Subaru SUV        3   4

Et le troisième, le niveau supérieur dans ce cas, l'index.

--| file0.dat |--
 0 Ford          0   1
 1 Subaru        2   2

Je pense que je surexplique le concept, mais en général, vous créez un index en supprimant le dernier champ et en éliminant les enregistrements en double.

Vous pouvez réduire davantage les besoins de stockage de fichiers en éliminant certaines données redondantes.

Par exemple, le "premier" indice de chaque enregistrement d'index est toujours un de plus que le "dernier" indice de l'enregistrement précédent, ou zéro s'il n'y a pas d'enregistrement précédent. Vous n'avez donc pas besoin de stocker les "premiers" indices. Je les laisse en place ci-dessous pour illustration.

De plus, comme vous n'utiliserez que le dernier champ de chaque enregistrement pour remplir la liste de sélection, vous n'avez pas besoin de stocker les autres champs.

Le rendu minimal de la cascade d'index finit par ressembler à ceci, où la coche 'indique un nombre qui n'est pas réellement stocké dans le fichier.

--| file0.dat |--
 0' Ford         0'   1
 1' Subaru       2'   2

--| file1.dat |--
 0' Truck        0'   1
 1' Sedan        2'   2
 2' SUV          3'   4

--| file2.dat |--
 0' F150         0'   3
 1' F250         4'   5
 2' Taurus       6'   8
 3' Forester     9'  10
 4' Outback     11'  14

--| file3.dat |--
 0' red
 1' blue
 2' black
 3' silver
 4' red
 5' green
 6' red
 7' green
 8' white
 9' blue
10' red
11' Black
12' Green
13' Blue
14' Red

Lorsque vous remplissez une liste de sélection à partir d'un index, vous utilisez les "premier" et "dernier" indices de la sélection de l'utilisateur dans l'index précédent pour limiter les lignes lues.

Exemple:

Vous remplissez la première liste de sélection parmi tous file0.dat. (Ford, Subaru)

L'utilisateur sélectionne "Ford". Les indices correspondants sont 0 et 1.

Vous remplissez la deuxième liste de sélection des lignes 0 à 1 de file1.dat. (Camion, berline)

L'utilisateur sélectionne "Sedan". Les indices correspondants sont 2 et 2.

Comme vous pouvez le voir, au moment où l'utilisateur a sélectionné, par exemple, "Ford" "Berline" "Taurus", vous constaterez que vous avez besoin de lire uniquement les lignes 6 à 8 de file3.datpour remplir la quatrième liste de sélection.

Je m'excuse pour la description assez longue mais il est très tard ici et je n'ai pas le temps d'en rédiger une courte.

AJOUTÉ: Après réflexion, les fichiers peuvent être concaténés en un seul.

--| file.dat |--
 0' -            1'   2
 1' Ford         3'   4
 2' Subaru       5'   5
 3' Truck        6'   7
 4' Sedan        8'   8
 5' SUV          9'  10
 6' F150        11'  14
 7' F250        15'  16
 8' Taurus      17'  19
 9' Forester    20'  21
10' Outback     22'  25
11' red          -'   -
12' blue         -'   -
13' black        -'   -
14' silver       -'   -
15' red          -'   -
16' green        -'   -
17' red          -'   -
18' green        -'   -
19' white        -'   -
20' blue         -'   -
21' red          -'   -
22' Black        -'   -
23' Green        -'   -
24' Blue         -'   -
25' Red          -'   -

Ceci est utilisé exactement comme la version à fichiers multiples, sauf que vous avez besoin de la première ligne factice pour contenir la première plage d'indices.

AI Breveleri
la source