Je poursuis mes tests. Le processeur passe apparement le plus clair du temps à gérer les conteneurs. J'essaye d'améliorer cet aspect.
Je trie la collection, j'itère, je clear le conteneur et je recommence... Je n'ai donc a priori pas besoin de recherche.
J'ai le sentiment (c'est ce que montrent les quelques tests que j'ai pu effectuer) que pour obtenir une liste ordonnée d'éléments, vector + sort est beaucoup plus efficace qu'un set (d'un facteur 10 environ sur des collections de quelques millions d'int). Et même, plus le nombre d'éléments augmente, plus le ratio est en faveur du vector + sort, ce qui est assez contre-intuitif je trouve...
Deux questions :
Est-ce normal ?
Y a-t-il encore plus performant (éventuellement dans des bibliothèques tierces) pour faire cela ?
Oui c'est normal. Contiguïté des éléments en mémoire oblige, alors que le set est un arbre. C'est les caches mémoire qui font ça. Pareil pour le fait que les vecteurs sont généralement beaucoup plus performants que les listes chaînées, même si algorithmiquement parlant on passe beaucoup de temps à ajouter et retirer au milieu -- sauf que le milieu on a parcouru des chaînons éparpillés pour le trouver.
Sinon, certaines libs fournissent des flat_map et des flat_set qui sont des maps et des sets, mais implémentés avec des vecteurs.
Si tu as un vecteur trié et que tu fais plus de recherches que de insertions / deletions, tu pourrais utiser la recherche dichotomique, si tu ne le fais pas déjà. Si je considère le nombre de comparaisons, par exemple pour 1000000: séquenciel: maximum = 1000000, moyenne = 500000 dichotomique: maximum = 20, moyenne = 18 (environ) Si le calcul t'intéresse, je peux te retrouver le code (c'est du C illisible, mais c'est petit)
Le Tout est souvent plus grand que la somme de ses parties.
Si vous voulez des performances je vous conseille de ne pas utiliser la STL. Évidemment que si on veut un ensemble d’entiers trié on se dit qu’on les met dans un Set, c’est exactement ce qu’on veut faire d’un point de vue conceptuel. Mais il faut choisir entre soit prendre le temps de trouver une solution optimale, soit réutiliser des trucs existants pas forcément optimaux.
Par rapport à votre problème, en général il est possible qu’il vaille mieux stocker les éléments dans un simple conteneur contigu et les trier juste au moment où on en a besoin, plutôt que d’avoir une structure qui maintient le tri en permanence, d’autant plus si c’est implémenté avec un arbre. En sachant aussi que vous voulez trier des entiers, je ne sais pas comment std::sort est implémenté, mais je vous recommande d’utiliser un radix sort, qui excelle à ce jeu là
@JadeSalina: Est-ce que le radix sort est efficace en mémoire si on a 10 millions d'entrées? Umbre37 ne nous a pas vraimen dit ce qu'il faisait: beaucoup d'insertions et peu de recherches vs peu d'insertions et beaucoup de recherches.
Le Tout est souvent plus grand que la somme de ses parties.
La STL est faite pour être générique. Forcément que ça fait des compromis, en particulier en ne proposant pas les milliers de structures et algos possibles qui sont utilisés que dans des contextes très particulier.
Pour le reste, il faut faire des benchs. C'est trop data dependant pour avoir une réponse générale.
Au cas où ce seraitutile, je donne ma version de la recherche dichotomique. Je l'appelle recherche dichotomique "avec point d'insertion": - // Recherche dichotomique avec point d'insertion. int search(std::vector<int> &vecteur, int valeur) { int debut = 0; int fin = vecteur.size(); while(debut < fin) { int milieu = (debut+fin) / 2; if(vecteur[milieu] == valeur) return milieu; if(vecteur[milieu] > valeur) fin = milieu; else debut = milieu+1; } return -(debut+1); // debut+1 au cas où debut == 0 } ... // Dans la fonction appelante. int retour = search(vecteur, valeur); if(retour < 0) { retour = -(retour+1); // Ramener la valeur positive. // Insérer avant la position retour }
Le Tout est souvent plus grand que la somme de ses parties.
Utilise const quand tu peux. Je sais pas si cela aura un impact ici, mais ca se peut que le compilateur puisse optimiser (pour vecteur en parametre, fin, milier, etc).
Avoir des valeurs négative à gérer est un peu étrange.
Pour ce genre de code, il suffit de regarder dans des répertoires de code. Par Rosetta Code, qui donne plein d'implementation dans plein de langages, exemple https://rosettacode.org/wiki/Binary_search#C.2B.2B
La position négative est retournée si la valeur n'est pas dans le tableau. Et comme indiqué, on peut savoir exactement où on pourrait l'insérer pour préserver l'ordre.
Crois-moi, ça marche. Je l'utilise depuis longtemps.
Je prend note de la remarque pour const
- Edité par PierrotLeFou 1 mai 2022 à 18:13:53
Le Tout est souvent plus grand que la somme de ses parties.
@PierretLeFou: std::lower_bound fait cela et une implémentation possible est visible sur cppreference
Pour std::set, on sait que par son implémentation (généralement un red-black tree) ses performances ne seront pas bonnes sur des petits objets. Ce sont les mêmes raisons que pour std::list, il faut que le type dedans soit gros en mémoire ou/et que son déplacement soit coûteux pour que le container soit efficace. Comme cette situation n'arrive que très rarement, ce container n'est pas efficace.
Après, une manière d'optimiser considérablement le container et de changer l'allocateur pour réduire la fragmentation mémoire (moins de perte de cache, meilleurs vitesse de parcours) et accélérer l'allocation des nœuds (moins de new/malloc qui sont très coûteux). La std fournit std::pmr::unsynchronized_pool_resource et std::pmr::set qui est un alias sur std::set.
Mais puisque tu vides tout le container à chaque fois, std::set sera dans tous les cas moins performant.
Il y a aussi std::priority_queue qui peut être intéressant dans certaines conditions.
Après, pour un tri optimal, il faut connaître les contraintes sur les valeurs. C'est pour ça qu'il n'existe pas d'algo meilleur dans toutes les situations. Tu peux comparer la vitesse du tri avec pdqsort ou les algos dans cpp-sort (counting_sort, spread_sort et ska_sort sont des algorithmes basés sur radix sort).
> Est-ce que le radix sort est efficace en mémoire si on a 10 millions d'entrées?
Tout dépend de ton implémentation et la plage de valeur. Pour un grand nombre d'élément et une petite plage de valeur couting sort et très efficace. Mais il est possible de faire une version qui travaille sur des grandes plages avec un tri sur le premier octet, puis le second et ainsi de suite. Niveau mémoire, on est à n*sizeof(T) pour la taille du cache et il existe plusieurs stratégies pour faire mieux.
En effet, les std::set comme d'autres font beaucoup d'allocations, et le nombre d'allocation est un goulot d'étranglement niveau performances. Il vaut mieux faire une grosse alloc que plein de petites.
Autre chose, le std::set t'assure une collection triée à tout moment, ce qui nécessite des tests à chaque insertion, alors qu'un vector + un sort ne la trie qu'à la fin.
Pour choisir le bon conteneur, il faut bien définir ce dont on a besoin.
Merci de t'intéresser ainsi au problème et merci pour ton code. Mais comme je l'écrivais dans mon premier message, je ne fais pas de recherche dans le conteneur, j'insère tout d'un coup, je trie et j'itère sur le conteneur. Donc les algos de recherche ne me servent pas pour le moment.
@JadeSalina
Merci pour le conseil, je vais aller voir du côté du radix sort, dans mon souvenir, c'est un tri multithread non? d'où les perfs...
@jo_link_noir
Les données entrées sont des int quelconques, impossible de savoir à l'avance où sont les choses dans le plan et combien il y en a.
Les valeurs sont des "unsigned", de taille choisie par l'utilisateur (le code est template). Ces int correspondent à des positions dans une grid multi-échelle (ou un arbre) pour situer les objets à collisionner dans le plan. L'ordre des int permet de collisionner facilement un secteur avec ses sous-secteurs, sous-sous secteurs, etc...Il suffit de parcourir le conteneur dans l'ordre. La complexité et la vitesse d'exécution sont considérablement réduites par rapport à un quad-tree classique (à cause de la contiguïté comme vous dites), et l'outil est beaucoup plus souple qu'une simple grid, il peut gérer des objets de toutes les tailles sans perte de perf.
J'ai inventé ce système qui m'a demandé pas mal de réflexion (sorte de compromis entre un quad-tree et une grid, en cumulant les avantages des deux). Mais visiblement je n'ai fait que réinventer la roue (Cf http://gamma.cs.unc.edu/PAPERS/WangEurographics2018.pdf - je ne fais pas exactement ça, mais il y a du commun). Ça m'a mis un coup au moral lorsque j'ai commencé à fouiner un peu sur ce qui se faisait déjà dans le monde universitaire, j'aurais dû regarder avant ! Le sujet est assez actif et ma solution ne sert à rien, à part à progresser personnellement. Je choisis tout de même d'aller au bout de mon idée, pour me distraire et pour ma satisfaction personnelle.
Je peux donner davantage de détails sur les algos et le projet si le sujet intéresse quelqu'un. Mais étant simple amateur, j'ai peur de ne pas vous apprendre grand chose
Mais visiblement je n'ai fait que réinventer la roue (Cf http://gamma.cs.unc.edu/PAPERS/WangEurographics2018.pdf ). Ça m'a mis un coup au moral lorsque j'ai commencé à fouiner un peu sur ce qui se faisait déjà dans le monde universitaire, j'aurais dû regarder avant ! Le sujet est assez actif et ma solution ne sert à rien
Au moins, si cela t'a permis d'apprendre cela, c'est déjà beaucoup. Certains continuent de penser que réinventer la roue est mieux, mais ils sont juste ignorant de toute la recherche qui est faite.
C'est pour cela qu'on conseille souvent (encore et encore) d'utiliser les outils existants, de faire du code de qualité (qui sera évolutif), de faire des tests et des benchs. Et une fois qu'on a tout cela, si c'est nécessaire, on va se taper le boulot d'optimisation, uniquement sur ce qui a un intérêt concret d'être optimisé.
Oui, mais il y a aussi du positif, j'ai trouvé quelque chose par moi-même, j'ai progressé, appris. Mais j'étais dans l'illusion de faire quelque chose d'original.
Oui, mais il y a aussi du positif, j'ai trouvé quelque chose par moi-même, j'ai progressé, appris. Mais j'étais dans l'illusion de faire quelque chose d'original.
Le coté positif aussi, c'est que "réinventer la roue" (ce qui est ici prononcé de manière si péjorative) n'est pas forcément quelque chose de mauvais, ça permet de se perfectionner en mécanique et avoir une certaine expérience.
ça ne veut pas dire qu'il ne faut pas utiliser des outils ensuite, mais en ayant fait ça, tu comprendras bien mieux les outils que tu utilises.
Merci beaucoup pour vos encouragements J'essayerai de poster de temps en temps sur le projet.
Bonne soirée à tous !
std::vector + sort VS std::set
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Discord NaN. Mon site.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html