Discussion :

[Kaluza]

Bonjour.

Experts avides de perfs en C++ j'ai une question pour vous.

Voilà mon problème :
Au départ j'ai une liste d'entiers 64 "unsigned long long int" qui peut être très longue (genre peser 4Go en mémoire). Ces nombres sont au départ dans un ordre aléatoire. En sortie je voudrais obtenir ces nombres classés du plus petit au plus grand (ou du plus grand au plus petit, peu importe) accompagnés de leurs indices avant classement.

Exemple :
Avant
Nombres : 32 91 11 72
Indices : 0 1 2 3
Après
Nombres : 11 32 72 91
Indices : 2 0 3 1

Ma question est la suivante : quelle est la solution permettant de produire le code le plus rapide (ceci sera au coeur d'un algo plus conséquent donc pour cette partie chaque tick d'horloge compte) ?

Par "solution" je veux dire : quels conteneurs utiliser ? Comment classer également les indices lors du processus (structure, std::pair, std::map...) ? Quel algorithme utiliser (std::sort, qsort ou peut être autre chose) ? Etc...

La question peut paraître très naïve, mais dans un contexte où "chaque tick d'horloge compte", cela n'est pas si évident que ça pour moi...

Merci beaucoup.

[Obsidian]

Bonjour,

Dans une telle situation, la solution optimale dépendra essentiellement de l'état de départ de tes nombres. Par exemple, sont-ils partiellement triés au départ, au moins par petits groupes, ou vraiment complètement aléatoires ?

D'autre part, d'où proviennent tes nombres et comment sont-ils acquis ? Car s'ils arrivent progressivement (par exemple depuis un instrument de mesure), il peut être intéressant d'opter pour un tri par insertion en utilisant les temps morts pour maintenir ordonnée la liste en temps réel.

[Kaluza]

Bonjour.

Ces nombres sont lus dans un fichier. Je pense (mais peut-être ai-je tort) qu'il est plus rapide de lire tout d'un bloc et ensuite de faire des opérations sur les nombres une fois tous chargés en mémoire. L'ordre de départ est complètement aléatoire (pas la moindre sous-séquence triée si ce n'est par le fruit du hasard).

[Rewpparo]

Tu as std::set qui trie les nombres quand ils entrent dans la liste.

Mais je pense en effet que dans ton cas il vaut mieux un std::list qui dispose d'une méthode sort() qui te permet de les trier la liste une fois tous les nombres insérés.

Tu peux trouver la performance comparée des différentes opérations des différents containers ici.

Mais je ne suis pas un expert, j'attends avec avidité les explications. Notamment sur les histoires de sous séquences, quel conteneur utiliser qui serait plus performant ?

[JolyLoic]

Mais je pense en effet que dans ton cas il vaut mieux un std::list qui dispose d'une méthode sort() qui te permet de les trier la liste une fois tous les nombres insérés.

std::list sera probablement bien moins performant que std::vector : overhead lié aux pointeurs suivant et précédents (ses 4Gio vont probablement devenir 8 Gio sur une std::list...), mémoire fragmentée (donc mauvaise utilisation du cache)... Le cas où on peut éventuellement gagner avec une list est si les objets sont très gros et très lourds à copier, ce qui n'est clairement pas le cas ici.

Le principal problème de vector (et son avantage...) est qu'il requiert de la mémoire contigüe, ce qui avec ces quantités peut ne pas être aisé à trouver, selon la mémoire disponible sur la machine.

Après, un std::sort tout bête n'est peut-être pas l'idéal pour ces quantités de données. Si une grosse machine est disponible, il est probable qu'un algorithme parallèle pourra être significativement plus rapide, et std::sort n'est classiquement pas implémenté ainsi (et je ne crois pas qu'il ait le droit de l'être, c'est faire trop de suppositions sur les objets à trier).

Ensuite, entre utiliser un vector<pair<>> ou une pair<vector<>>, je ne sais pas trop. Je pense que je ferais les deux pour comparer les résultats.

Et effectivement, avoir une idée de la nature des données (sont-elles presque triées au départ) me semble important.

[oodini]

Le principal problème de vector (et son avantage...) est qu'il requiert de la mémoire contigüe, ce qui avec ces quantités peut ne pas être aisé à trouver, selon la mémoire disponible sur la machine.

Je croyais que les specs du C++ n'avaient pas cette exigence ?

[Rewpparo]

std::list sera probablement bien moins performant que std::vector

Tiens bizarre. Le problème que je voyais avec Vector c'est s'il ne connait pas le nombre d'objets a mettre dedans et qu'il ne peut donc pas faire de allocate, il va régulièrement devoir réalouer un buffer, demandant le double de mémoire pendant le transfert.
maintenant c'est vrai que s'il a une estimée approximative de la taille de son fichier, il peut déja allocate ca et du coup il aura besoin du double de mémoire uniquement s'il a vu trop juste.
Je raisonne bien la ou il y a des trucs que j'ai pas vu ?

[Obsidian]

Dans un premier temps, si tu dois trier 4 Gio de données ou plus, je ne saurais trop te recommander d'utiliser une architecture 64 bits si ce n'est pas déjà le cas. Ce sont les ordres de grandeur où la différence entre les deux architectures va commencer à se faire sentir. Sinon, tu ne pourras pas charger tout ton fichier en mémoire et, donc, tu ne pourras pas directement comparer n'importe quel élément avec n'importe quel autre.

Ensuite, mapper le fichier en mémoire peut effectivement être très efficace. Mais pour cela, nous avons besoin de savoir encore trois choses :

• Tes données sont-elles enregistrées en binaire et de manière régulière dans ton fichier ou s'agit-il d'un fichier texte ?
• As-tu besoin d'un tri stable ? C'est-à-dire : les indices doivent-ils conserver leur ordre d'apparition initial si les nombres sont identiques ?
• Dois-tu trier le fichier lui-même « in place » ou dois-tu produire un second fichier en conservant le fichier initial intact ?

Pour le premier point, cela va nous permettre de savoir si cela vaut le coup de mapper le fichier en mémoire ou pas. Si c'est en texte, il faudra procéder autrement.

Pour le second point, à te lire, je pense que cela n'a aucune importance pour toi. Mais si ça en a, cela va influer sur le choix de ton algo et restreindre les performances. Cette page tend à dire que « std::sort » va tâcher de faire le meilleur choix : http://warp.povusers.org/SortComparison/