Discussion :

[salseropom]

Bonjour, je travaille sur un algorithme de classification ascendente hiérarchique (CAH). L'algo est assez simple :

on a un ensemble de point. A chaque point est associé un numéro.

On calcule les distances 2 à 2 et on récupère les 2 points pour lesquels la distance est minimale. Puis on crée un nouveau point, barycentre des 2 points sélectionnés. Ensuite on efface toutes les combinaisons de paire de points faisant intervenir au moins 1 des points sélectionnés et on recalcule toutes les distances entre le nouveau point et les points restant.

Je dois donc récupérer les 2 points qui minimisent la distance. J'ai donc fait une

multimap<double, pair<int, int> >

ou double est la distance et les 2 int sont les numéros des 2 points.

Que vaut-il mieux faire : utilisez une multimap ou bien une bête liste chainées dans laquelle je fais moi-même l'insertion par ordre croissant ?

Car je dois aussi effacer toutes les paires inutiles (car je supprime des points) et je dois aussi en insérer (toutes les paires faisant intervenir le nouveau point créé).

J'ai entendu dire que le point d'entrée de l'arbre (des multimap) était recalculé à chaque fois que l'on fait une insertion / suppression.

Je cherche à gagner du temps de calcul...

Merci d'avance

[3DArchi]

Salut,
Pourquoi ne pas utiliser une matrice (enfin, seulement une moitie sans la diagonale) des tes points pour conserver tes distances. A chaque étape, tu choisis le min, tu calcul ce nouveau point et tu recalcules les lignes/colonnes du min.

[salseropom]

Salut 3DArchi,

j'ai déja fait la version matricielle. Pour 1000 éléments, cette méthode ou celle des map est aussi rapide. Mais pour 5000 éléments, les map vont 4 fois plus vite. Surtout que pour supprimer une colonne d'une matrice, ce n'est pas facile : il va falloir faire des recopies...

D'où ma question entre les maps et les list (sachant que j'ai 250000 éléments)...

[Goten]

Par curiosité, t'avais utilisé quoi pour tes matrices? (ublas, blitz++ ?) etc

[gbdivers]

Bonjour Salseropom

multimap::insert ajoute chacun nouveau élément dans la map en fonction du classement de la clé. La recherche de la position correcte est une complexité log donc pas possible d'avoir plus rapide je pense (ref: http://www.cplusplus.com/reference/stl/multimap/insert/).

De toute façon, la recherche de tous les éléments de la map qui ne sont plus utiles est forcement linéaire (obligation de tester tous les éléments). Ton insertion sera moins pénalisant que la suppression.

PS: 250000 éléments ! Moi qui me croyait pas chanceux avec mes dizaine de milliers d'individus a classer Dans un espace à combien de dimensions ?

Edit: en fait, il est peut être possible d'éviter l'étape de suppression des paires inutiles...
Puisse que tu t'intéresse à la distance minimale (c'est à dire la première paire de ta map), il te suffit simplement de vérifier que la première paire concernant 2 éléments qui n'ont pas encore été traités. Si c'est le cas, tu supprimes et tu passes à la paire suivante. Sinon tu calcules le barycentre de cette paire.
Pour conserver l'information des éléments déjà traités, tu peux utiliser un simple std::set<int>.

Re-edit: Après le café pour réveiller un peu les neurones...
complexité pour l'étape avec k éléments restant.

* méthode avec std:map
- recherche de la distance minimale : constant (premier de la map)
- ajout de k-1 éléments calculés à partir du barycentre (chaque insertion étant en log() ) : compexité n.log(n)

* méthode avec std:list
- recherche de la distance minimale (sur liste non trié) : complexité linéaire (regarder chaque distance 1 par 1)
- ajout de k-1 éléments (chaque insertion étant de compexité constante) : complexité linéaire.
La suppression des 2k éléments peut se faire à l'étape k-1 lors de la recherche de la distance minimale (complexité constance).

Donc au final, on a une complexité linéaire pour std::list vs une complexité n.log(n) pour std:multimap (pour chaque itération).

Pour l'algorithme complet, on doit faire n-1 itérations avec k éléments à chaque étape, donc un complexité de n², c'est à dire n³ pour std:list et n³.log(n) pour std:multimap... dans tous les cas, ça va être long

[salseropom]

Bonjour Salseropom

multimap::insert ajoute chacun nouveau élément dans la map en fonction du classement de la clé. La recherche de la position correcte est une complexité log donc pas possible d'avoir plus rapide je pense (ref: http://www.cplusplus.com/reference/stl/multimap/insert/).

De toute façon, la recherche de tous les éléments de la map qui ne sont plus utiles est forcement linéaire (obligation de tester tous les éléments). Ton insertion sera moins pénalisant que la suppression.

PS: 250000 éléments ! Moi qui me croyait pas chanceux avec mes dizaine de milliers d'individus a classer Dans un espace à combien de dimensions ?

Edit: en fait, il est peut être possible d'éviter l'étape de suppression des paires inutiles...
Puisse que tu t'intéresse à la distance minimale (c'est à dire la première paire de ta map), il te suffit simplement de vérifier que la première paire concernant 2 éléments qui n'ont pas encore été traités. Si c'est le cas, tu supprimes et tu passes à la paire suivante. Sinon tu calcules le barycentre de cette paire.
Pour conserver l'information des éléments déjà traités, tu peux utiliser un simple std::set<int>.

Re-edit: Après le café pour réveiller un peu les neurones...
complexité pour l'étape avec k éléments restant.

* méthode avec std:map
- recherche de la distance minimale : constant (premier de la map)
- ajout de k-1 éléments calculés à partir du barycentre (chaque insertion étant en log() ) : compexité n.log(n)

* méthode avec std:list
- recherche de la distance minimale (sur liste non trié) : complexité linéaire (regarder chaque distance 1 par 1)
- ajout de k-1 éléments (chaque insertion étant de compexité constante) : complexité linéaire.
La suppression des 2k éléments peut se faire à l'étape k-1 lors de la recherche de la distance minimale (complexité constance).

Donc au final, on a une complexité linéaire pour std::list vs une complexité n.log(n) pour std:multimap (pour chaque itération).

Pour l'algorithme complet, on doit faire n-1 itérations avec k éléments à chaque étape, donc un complexité de n², c'est à dire n³ pour std:list et n³.log(n) pour std:multimap... dans tous les cas, ça va être long

Salut, merci pour cette longue réponse. J'ai 250000 éléments dans R^4 à classer.

Pour la liste chaînée, je pense tout de même faire une liste triées (par ordre croissant des distances inter-classes)

Je pense qu'il faut que je teste mon code avec les listes.

[salseropom]

Par curiosité, t'avais utilisé quoi pour tes matrices? (ublas, blitz++ ?) etc

j'avais utilisé juste des std::vector<std::vector<double> > mais pour des problèmes mémoire, les listes sont mieux car je supprime à chaque itération des lignes (et colonnes) de ma matrice

[Goten]

j'avais utilisé juste des std::vector<std::vector<double> > mais pour des problèmes mémoire, les listes sont mieux car je supprime à chaque itération des lignes (et colonnes) de ma matrice

Alors ça m'étonne pas, vector est peu adapté à être imbriqué, surtout sur d'aussi grande quantité de donnée. Il serait intéressant de tester avec un vraie container matricielle. (boost.ublas par exemple)