C'est une affaire de psychologie
Le développeur C++ aime la performance et il déteste tout ce qui l'oblige à créer une structure de données intermédiaire, à allouer de la mémoire. Même copier un entier lui est désagréable. L'état d'esprit du développeur Python est différent: si je peux créer, pense-t-il, en 20 minutes, un programme qui s'exécute en 1 seconde, je fais un meilleur marché que si je mets 20 heures à créer le même programme qui s'exécute en 1 ms. Le développeur Python prend un plaisir particulier à écrire en deux lignes ce qui en prendrait 20 en C++. Pour cette raison, l'interface compte moins.
Reprenons le fil de notre algorithme: l'argument de la fonction buildTree est std::vector<std::vector<Item>>; en python cela équivaut à une liste de listes: [[]]. Pour convertir en liste de listes un fichier où les transactions sont séparées par des retours à la ligne et les éléments des transactions par des espaces, il suffit d'écrire:
| Code Python : | Sélectionner tout |
[[item for item in line.strip().split( )] for line in open("myfile.csv")]
Pourquoi c'est mal, tentacule et csv
En écrivant cette petite ligne de code, on a démontré la concision de Python, certes. On a aussi copié tout le fichier en mémoire, et on s'apprête à copier tous les objets en mémoire une seconde fois dans l'arbre des associations fréquentes. Quel développeur C++ digne de ce nom accepterait une chose pareille?
Je vous conseille la lecture d'un excellent article de white_tentacle qui porte sur la lecture d'un ficher csv en C++ et illustre bien cette exigence: pour travailler sur un fichier csv, il n'est pas toujours nécessaire de le charger entièrement en mémoire, loin de là; il faut toujours charger le minimum possible: peut-être une ligne, peut-être même simplement une cellule. Le parseur de csv que white_tentacle propose demande de fournir deux fonctions de call back: une appelée lorsqu'une cellule a été lue, une lorsqu'une ligne a été lue. S'il s'agit simplement d'afficher le fichier, par exemple, vous pourrez fournir une fonction qui affiche un élément comme call_back de cellule, et une fonction qui affiche un retour à la ligne comme call_back de ligne. Empreinte mémoire? quasi-nulle.
Vous pouvez raisonner de la même façon pour une base de données: vous n'allez pas charger en mémoire tous les enregistrements qui correspondent à votre requête avant de travailler dessus, sauf si cela est tout à fait nécessaire; vous préfèrerez de travailler enregistrement par enregistrement, voire champ par champ, si cela est possible.
Une interface pour plaire à deux développeurs C++
Vous devez donc proposer comme interface des fonctions primitives: celles qui donneront le plus de liberté au développeur client pour conserver une performance maximale. Mais ce n'est pas tout: vous devez également choisir une interface qui vous donnera suffisamment de liberté pour améliorer la performance de votre algorithme sans casser le code client. Il vous faut donc trouver le niveau de granularité adéquat: d'assez bas niveau pour laisser au client faire ses choix, d'assez haut niveau pour que vous puissiez modifier les vôtres. L'interface de départ, c'est tout le contraire:
| Code C++ : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | // une mauvaise interface // les fonctions pour construire la fp-tree bool buildTree(const std::vector<std::vector<Item>>& input); bool buildTree(const std::vector<std::pair<std::vector<Item>, int>>& input); void scanSequenceForFrequency(const std::vector<Item>& input, int freq = 1); void deleteInfrequentItems(); void scanSequenceIntoTree(std::vector<Item>& input, int freq = 1); //les fonctions pour chercher les associations fréquentes void mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& prefix); std::vector<Item> ascendTree(fpnode<Item>* bottom); std::vector<std::pair<std::vector<Item>, int>> getConditionalPatterns(const Item& i); |
Quelle interface pour la construction du frequent pattern tree?
Construire un arbre des associations fréquentes, c'est 1) parcourir la liste des transactions pour connaître la fréquence de chaque élément et 2) parcourir à nouveau la liste des transactions pour intégrer chacune des transactions à l'arbre. Contrairement à ce que laissait penser l'interface initiale, ce sont deux étapes hétérogènes: dans un cas c'est l'élément qui nous intéresse, dans le deuxième la séquence.
La signature de scanFrequency doit donc se rapporter à un élément, plus à une séquence:
| Code C++ : | Sélectionner tout |
1 2 | void scanFrequency(const Item& i, int freq=1); |
La signature de scanPattern ne peut pas non plus rester telle qu'elle était: elle prenait comme argument non pas une séquence mais une structure de données qui la représentait (le std::vector<Item>). Le moyen à privilégier pour représenter une séquence en C++, c'est l'itérateur:
| Code C++ : | Sélectionner tout |
1 2 | template <class RandomIterator> void scanPattern(RandomIterator b, RandomIterator e, int freq=1); |
Il vaut mieux préciser dans la signature quel type d'itérateur est nécessaire. Ici, comme l'algorithme de tri de la STL est utilisé, vous avez besoin d'un itérateur permettant un accès aléatoire. Le nom du paramètre en template n'est qu'une indication -précieuse- pour le client. Vous pouvez néanmoins ajouter une assertion statique au début de la définition de la fonction pour générer un message d'erreur lisible lors de la compilation:
| Code C++ : | Sélectionner tout |
1 2 3 4 5 6 7 8 | template <class Item> // dans la définition d'une fonction template d'une classe template template <class RandomIterator> // le template de la classe vient en premier void fptree<Item>::scanPattern(RandomIterator b, RandomIterator e, int freq) { static_assert(std::is_same< std::random_access_iterator_tag, typename std::iterator_traits<RandomIterator>::iterator_category >::value, "Bad pattern iterator: access must be random in scanPattern(Iterator, Iterator)"); (...) |
Quelle interface pour extraire les frequent patterns?
La signature de mineTree présente le même problème que celle de scanPattern: elle utilise une structure de données (passablement compliquée en plus) pour représenter la séquence des résultats.
| Code : | Sélectionner tout |
void mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& prefix);
Vous me direz ce que vous en pensez: la solution la meilleure, à mon avis, est de demander à l'utilisateur de fournir quoique ce soit qui puisse être appelé comme une fonction: un foncteur, une fonction lambda, une simple fonction (ne les oublions pas!). J'ai donné à ce "fonction-like" le nom de Processor:
| Code : | Sélectionner tout |
1 2 | template <class PatternProcessor> void mineTree(PatternProcessor& processor, const Prefix& prefix = Prefix()); |
results.push_back(std::make_pair(last_transaction, last_transaction_frequency));vous écrivez:
processor(std::make_pair(last_transaction, last_transaction_frequency));et c'est le seul changement.
Quelques exemples d'appel:
| Code C++ : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 | // pour affiche simplement le résultat à l'écran using Transaction = std::vector<std::string>; using FrequentPattern = std::pair<Transaction, int>; auto processor = [](const FrequentPattern& pat) { // avec une lambda for (auto& i : pat.first) std::cout << i << ' '; std::cout << " : " << pat.second << std::endl; }; fpt.mineTree(processor); |
ou bien:
| Code C++ : | Sélectionner tout |
1 2 3 4 5 6 7 | // pour remplir un vecteur using Transaction = std::vector<std::string>; using FrequentPattern = std::pair<Transaction, int>; std::vector<FrequentPattern> rc; auto processor = [&](const FrequentPattern& pat) { rc.push_back(pat); } fpt.mineTree(processor); |
En résumé
L'interface de la classe fptree ressemble désormais à ça:
| Code C++ : | Sélectionner tout |
1 2 3 4 5 6 7 8 | public: void scanFrequency(const Item& i, int freq=1); template <class RandomIterator> void scanPattern(RandomIterator b, RandomIterator e, int freq=1); template <class PatternProcessor> void mineTree(PatternProcessor& processor, const Prefix& prefix = Prefix()) const; void show(); |
J'ai glissé sans le dire un const à la fin de la déclaration de mineTree. Un autre aspect important d'une interface C++ est de toujours préciser si une méthode modifie ou non la classe sur laquelle elle est appelée. Le respect de cette convention nommée const-correctness permet au compilateur de faire du travail à notre place et, parfois, d'optimiser le code généré.
Seulement une étape
Tout cela n'est bien sûr qu'une étape dans le processus de raffinement de notre classe. Mais nous pouvons désormais continuer ce travail à l'abri d'une interface qui n'énervera pas le développeur client et qui nous laisse une grande liberté pour modifier notre code.
Dans le prochain épisode, vous mettrez vos mains dans le cambouis de la gestion mémoire...