Tri le plus rapide d'une liste de nombres accompagnés des indices

Version imprimable

23/04/2012, 22h20
Kaluza

Tri le plus rapide d'une liste de nombres accompagnés des indices

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.

Citation:

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.
23/04/2012, 23h08
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.
23/04/2012, 23h20
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).
23/04/2012, 23h47
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 ?
24/04/2012, 00h08
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/
24/04/2012, 08h51
JolyLoic

Citation:

Envoyé par Rewpparo

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.
24/04/2012, 10h35
oodini

Citation:

Envoyé par JolyLoic

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 ?
24/04/2012, 11h08
JolyLoic

Ce n'était pas forcément clair en C++98, mais tout le monde le faisait. Et c'est clairement obligé désormais.
24/04/2012, 12h27
Obsidian

Citation:

Envoyé par JolyLoic

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.

La seule chose qui m'ennuie avec std::vector<> est que, sauf erreur de ma part (je ne pratique pas assez), on ne peut pas mapper les données en mémoire avec un mmap() ou assimilié et transtyper le tout en vecteur. Même si ses données sont contiguës en mémoire et qu'elle supportent l'arithmétique des pointeurs, il faut quand même l'initialiser et le charger, à moins de déclarer directement le vecteur comme étant large de la taille du fichier (divisée par celle d'un élément) mais, là encore, il faudra mapper de la mémoire sur un plan censé être déjà alloué.

Si on en est vraiment au point où « chaque cycle compte », je ferais probablement quand même un peu d'assembleur pour le principe, histoire d'utiliser quelques instructions dédiées, même si sur des choses aussi déterministes que les algos de tri, il est vraiment difficile de battre un compilo.

Ensuite, si on est vraiment dans la vitesse, il nous faudrait un algo que l'on puisse paralléliser sur les différents cœurs d'un processeur moderne. Je ne sais pas non plus si la STL est capable de faire cela.

Citation:

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

Comme il l'a dit, elles sont complètement aléatoires.
24/04/2012, 13h00
Rewpparo

Citation:

Envoyé par JolyLoic

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 ?
24/04/2012, 16h13
Trademark

En terme de complexité spatiale, vector est moins performant que list vu qu'il alloue par bloc (sauf si tu fais un resize ou que tu alloues tout dès le départ, tu auras pile poil la place qu'il te faut). Par contre en terme de complexité temporelle vector est plus rapide car tu ne fais pas d'allocation à chaque fois que tu ajoutes un élément. A contrario, dans la liste, c'est ce que tu fais et c'est ce qui est couteux en temps.
24/04/2012, 18h23
Klaim

Sans compter que les accès aux éléments de la liste sont des sauts dans la mémoire, autrement dit une tonne de cache-miss, ce qui sur le hardware actuel en général veut dire une perte de performance non-négligeable.

Le vector résoud ce problème, utilisez le. (si il peut tenir dans la mémoire...)
25/04/2012, 14h41
Kaluza

Rebonjour à tous.

Quelques précisions sur le problème pour peut être éclaircir un peu la situation.

- L'algo tournera très majoritairement sur des architectures 64 bits.

- Quand je disais 4Go en fait je voulais dire que l'algo doit être efficace pour le minimum entre la quantité maximale de mémoire contigüe qui peut être réservée et 4Go. Dans la pratique, disons que l'algo doit être efficace pour travailler dans la gamme "[100 millions - 1 milliard] d'éléments".

- Au niveau des données d'entrée on a : fichier ASCII -> algo assez tordu avec des cast et des bitshift dans tous les sens-> [100 millions - 1 milliard] d'entiers 64 à trier (au départ dans un ordre complètement aléatoire). Deux possibilités : soit j'applique d'abord l'algo tordu à tous les éléments puis je tri le résultat (ce qui est pour l'instant l'option envisagée), soit j'applique l'algo tordu et je classe au fur et à mesure de la lecture des éléments (moins pratique pour moi, mais si c'est plus efficace, alors je choisis cette option).

- Pas de parallélisation sur le chargement/tri parce que ... la couche de plus haut niveau est parallèle. L'algo dont il est question ici doit donc être le plus rapide possible sur 1 thread.

Voilà, voilà...
25/04/2012, 18h04
Obsidian

Une chose très importante encore : quel est le domaine des valeurs à trier ? Tu nous as dit qu'une valeur était stockée sur 64 bits mais peut-elle réllement, en elle-même, s'étendre de 0 à 2⁶⁴-1 ?

Citation:

Envoyé par Kaluza

- L'algo tournera très majoritairement sur des architectures 64 bits.

- Pas de parallélisation sur le chargement/tri parce que ... la couche de plus haut niveau est parallèle. L'algo dont il est question ici doit donc être le plus rapide possible sur 1 thread.

- Au niveau des données d'entrée on a : fichier ASCII -> algo assez tordu avec des cast et des bitshift dans tous les sens-> [100 millions - 1 milliard] d'entiers 64 à trier (au départ dans un ordre complètement aléatoire).

Ok, 64 bits, pas de thread, pas de mmap : donc vector<> et std::sort. Tout le monde a l'air d'être unanime. Si tant est que tu veuilles t'en tenir au C++. Il y a peut-être des choses à tester à côté.

Citation:

- Quand je disais 4Go en fait je voulais dire que l'algo doit être efficace pour le minimum entre la quantité maximale de mémoire contigüe qui peut être réservée et 4Go. Dans la pratique, disons que l'algo doit être efficace pour travailler dans la gamme "[100 millions - 1 milliard] d'éléments".

C'est-à-dire qu'un milliard d'éléments composés chacun d'un nombre et d'un indice, chacun sur 64 bits, ça fait 16 Go. Si un milliard d'éléments peut être considéré comme une limite supérieure, je te suggère de d'approvisionner généreusement en RAM histoire de faire un programme qui puisse tout charger en mémoire et ne faire aucun accès disque superflu.

Citation:

Deux possibilités : soit j'applique d'abord l'algo tordu à tous les éléments puis je tri le résultat (ce qui est pour l'instant l'option envisagée), soit j'applique l'algo tordu et je classe au fur et à mesure de la lecture des éléments (moins pratique pour moi, mais si c'est plus efficace, alors je choisis cette option).

En faisant abstraction du cas des lignes de cache et si j'avais 16 à 32 Gio de RAM devant moi, et en considérant que le domaine des valeurs (et non le nombre d'éléments) alors j'allouerais un grand segment contigü en mémoire, je l'initialiserai linéairement avec une valeur-sentinelle que saurais ne jamais rencontrer dans mes fichiers et je me servirais de la valeur à trier comme index pour aller directement la déposer en mémoire au bon endroit. Ensuite, je relirais en une passe la mémoire entière pour constituer le fichier de sortie. Ça donnerait une complexité en O(n) quelque soit le nombre d'éléments.

En tenant compte du cache, je pense que j'essaierais de maintenir ordonné en temps réel un segment de valeurs pas plus long que la longueur du cache. Une fois plein, je remplis le segment suivant avec les valeurs qui continuent d'arriver en le maintenant ordonné aussi mais indépendamment du premier. Et quand c'est fini, on fait des merge en cascade des segments ordonnées.