temps d'accès : map ou list ?

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

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.

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

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

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

Citation:

---

Envoyé par Goten

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

Citation:

---

Envoyé par 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

---

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.

Tu me bats pour le nombre d'éléments mais je gagne pour les dimensions (je suis dans R³⁰⁰⁻⁴⁰⁰ et j'ai une étude en cous où je serais surement dans R¹⁰⁰⁰⁻²⁰⁰⁰) :)

Pour le trie, il est possible que cela "coute" plus que ça apporte. Si tu as un peu de temps, je te conseil de créer les 3 méthodes et de les comparer sur des données réelles.

Quand tu auras comparé, tu pourras peut être mettre ici le résultat. Ca pourrait intéresser d'autres personnes (dont moi).

Bon courage.

Citation:

---

Envoyé par salseropom

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)

Je viens de réaliser que tu auras un petit (gros ?) problème...

250 000 éléments x 250 000 éléments x 32 bits ~ 232 Go pour une matrice (sauf erreur de ma part).

Pour une liste (1 foat/double + 2 integer), ça sera encore pire.

Bref, tout ça ne passe pas dans la RAM.

Faire le calcul sur les 250 000 en même temps en utilisant le disque, ça prendra énormément de temps (et dans ce cas, tu n'as pas a t'embête à optimiser ton algorithme. vecteur, list ou map, ça sera pareil).

Et a priori, ton algorithme est difficilement divisable en morceau (pour faire par exemple des paquets de 10 000 éléments, les traiter et passer au paquet suivant).

Peut être en passant par une fragmentation de l'espace : tu divises chaque dimension en 10 (ce qui te donnera 10 000 sous-espace) et tu appliques ton CAH dans chaque sous-espace. Par contre, je ne sais pas comment régler l'effet de bord.

En fait, je suis pas sur que ce soit possible de faire un CAH sur autant de données. Voir d'autres algorithme de clustering