par , 04/01/2016 à 05h20 (2493 Affichages)
Après avoir introduit l'algorithme de détection, j'en ai proposé une implémentation naïve (1, 2). En partant de si bas, beaucoup d'améliorations sont possibles avant d'en faire une implémentation de qualité. Nous commencerons par proposer une interface compatible avec les exigences d'un développeur C++ client.
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:
[[item for item in line.strip().split( )] for line in open("myfile.csv")]
Et je me sens intelligent, moderne. J'ai une pensée entre amusement et pitié pour le développeur C++.
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:
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:
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:
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:
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.
void mineTree(std::vector<std::pair<std::vector<Item>, int>>& patterns, const std::vector<Item>& prefix);
Néanmoins, la solution est moins évidente dans ce cas-là, car il n'y a pas d'itérateur qui soit à la fois assez général et d'usage assez fréquent pour représenter efficacement ce que la fonction attend de l'utilisateur. Mettons que l'on choisisse de nommer notre itérateur InserterIterator, l'utilisateur pourrait penser que std::back_inserter, std::front_inserter et std::inserter, indifféremment, vont fonctionner, ou bien il se demandera lequel est compatible. Il ne pensera pas nécessairement à un std::ostream_iterator qui pourrait pourtant être un candidat valable. Enfin, réaliser son propre itérateur est une tâche qui, sans être bien compliquée, ne doit pas être imposée à un client si elle n'est pas nécessaire.
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:
1
2
| template <class PatternProcessor>
void mineTree(PatternProcessor& processor, const Prefix& prefix = Prefix()); |
Dans le corps de la fonction, au-lieu d'écrire:
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:
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:
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:
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...
Consulter le profil
Marquer ce blog comme lu
