Discussion :

[ABD-Z]

Bonjour les devs!
Aujourd'hui je suis confronté à un petit problème dont je n'ai pas assez de connaissance et de savoir pour le résoudre.
Pour résumer :
J'ai un algorithme qui utilise std::sort pour chaque mot parcouru dans une énorme liste. Avec std::sort, le programme tourne dans les 1675.2 millisecondes sur mon ordi très moyen. Sur un ordi doté d'un vrai processeur l'algo tourne en seulement 18 millisecondes!
J'ai changé std::sort en smoothsort (que j'ai implémenté, plutôt que j'ai trouvé sur Internet) et le résultat est meilleur sur ma machine : 1535.2 millisecondes. Cependant je ne l'ai pas fait tourner sur l'ordi doté de puissance (parce que ce n'est pas possible pour le moment).
Je me demandais si le temps d’exécution de l'algo avec smoothsort respecterait le tableau en croix : à savoir (18*1535.2)/1675.2 = 16.5 ms ; est-ce que c'est nécessairement vrai? Peut-être que ça dépend de comment l'algo smoothsort tourne sur la machine puissante.

Pour détailler :
Je fais en fait un algo qui prend en entrée une liste (de type vector) énorme de mots de la langue français (ou autre, peu importe), et qui pour chaque mot, le trie dans l'ordre alphabétique pour ainsi le stocker en tant que clef dans une unordered_map qui a pour valeur les indices des mots qui ont la même composition de lettres lorsqu'ils sont triés.
Clef = chaîne de caractères triée dans l'ordre alphabétique -> Valeur = liste d'indices des mots correspondant
Considérons N la taille de la liste (qui est très très grande) et k la taille moyennes d'un mot de la liste ; en utilisant std::sort la complexité moyenne est de k*log(k)*N ce qui correspond à 18 ms sur la machine puissante. Tandis qu'avec smoothsort la complexité est légèrement meilleur puisqu'elle est égale à la longueur du mot k lorsque les lettres sont déjà triées ; cependant je ne sais pas s'il y a une vraie différence lorsque le programme tourne sur l'ordi performant.
Mon but étant de trouver un algorithme rapide en moins de 11 ms!
Comme vous pouvez le remarquer, ce qui est assez coûteux en temps c'est le tri des lettres, puisque de toutes manières, nous sommes obligés de parcourir la liste de taille N au moins une fois.
Idéalement, la complexité doit être à peu près égal à N, mais les algo de tri ne sont pas les meilleurs pour atteindre cet idéal.

Ce que je voulais savoir c'est :
-Est-ce que le produit en croix s’applique au temps d’exécution de deux programmes sur deux processeurs : à savoir (18*1535.2)/1675.2 = 16.5 ms
-Qu'est-ce qui pourrait être plus efficace que de trier les lettres de chaque mot pour compter le nombre de mots qui ont le même nombre de lettres?

[koala01]

Salut,

Le fait est que le traitement des chaines de caractères est particulièrement lent "par nature".

Si tu veux gagner en performance, le plus efficace est donc... de ne jamais travailler avec la chaine de caractère en elle-même (surtout pas comme clé dans un arbre binaire) et, si possible, d'éviter au maximum les copies.

Pour éviter les copies et les allocations mémoires qui en découlent, tu peux déjà te tourner vers les std::string_view, qui sont apparues en C++17 (ca fait quand même déjà trois ans, il serait temps que les gens commencent à les utiliser ) "à chaque fois que c'est possible".

Mais, ceci dit, l'idée principale est surtout de sauvegarder bien précieusement le résultat du tri, car je présumes que tu vas rarement (pour ne pas dire jamais) ajouter un mot entre deux recherches: tu vas charger ta liste de mots au lancement de ton programme (c'est à ce moment ci qu'il faudra trier ta liste), et, pendant le reste du programme, tu vas surtout ... rechercher les mots qui t'intéressent.

Du coup, tu te fous pas mal du temps que le tri peut prendre, du moins, dans une certaine mesure, car il est "en dehors" de la période d'utilisation réelle, pendant laquelle le temps devient critique. Ce qui importe, c'est que ta liste soit correctement triée la première fois que tu effectuera une recherche dessus, non?

Bien sur, on aimerait autant que l'initialisation du programme ne prenne pas dix minutes, pour éviter que l'utilisateur ait le temps d'aller boire un café, de le digérer et d'aller le pisser avant de pouvoir utiliser l'application, mais, si cette initialisation prend trois secondes au lieu de deux (ou même seulement d'une), ca ne va pas faire une très grosse différence

[ABD-Z]

Si tu veux gagner en performance, le plus efficace est donc... de ne jamais travailler avec la chaine de caractère en elle-même (surtout pas comme clé dans un arbre binaire) et, si possible, d'éviter au maximum les copies.

Effectivement, pour chaque mot de la liste, je passe par std::string clef = list[i]; puis je trie clef. Mais j'étais un peu obligé de faire une copie car je ne veux pas modifier le mot de la liste en effectuant le tri directement dessus.

Pour éviter les copies et les allocations mémoires qui en découlent, tu peux déjà te tourner vers les std::string_view, qui sont apparues en C++17 (ca fait quand même déjà trois ans, il serait temps que les gens commencent à les utiliser ) "à chaque fois que c'est possible".

Ah tiens! Mais qu'est-ce donc std::string_view?? Ça fait une copie de chaîne de caractères plus rapidement?

Ce qui importe, c'est que ta liste soit correctement triée la première fois que tu effectuera une recherche dessus, non?

Oui, ma liste de mots est déjà triée dans l'ordre alphabétique et ça ne compte pas dans le temps d'exécution.

En gros je dois pouvoir regrouper les anagrammes le plus rapidement possible ; le challenge étant en moins d'une dizaine de millisecondes.

Mais, ceci dit, l'idée principale est surtout de sauvegarder bien précieusement le résultat du tri, car je présumes que tu vas rarement (pour ne pas dire jamais) ajouter un mot entre deux recherches: tu vas charger ta liste de mots au lancement de ton programme (c'est à ce moment ci qu'il faudra trier ta liste), et, pendant le reste du programme, tu vas surtout ... rechercher les mots qui t'intéressent.

C'est exactement ça, ma liste de mots du dico je la charge en une seule fois puis elle subi un tri dans l'ordre alphabétique. Ensuite je dois trouver tous les anagrammes de la liste de N mots. Ce que je fais, comme tu l'as dit, je copie le mot, je trie ses lettres dans l'ordre puis je mets dans la hash map le mot trié en tant que clef et la valeur l'indice du mot (que je push back à chaque fois). Si la manipulation des petits strings est assez mauvaise, comment donc faire?

[koala01]

Ah tiens! Mais qu'est-ce donc std::string_view?? Ça fait une copie de chaîne de caractères plus rapidement?

Non, justement, ca ne fait aucune copie de la chaine de caractère: ca stocke uniquement l'adresse du premier caractère qui t'intéresse, et une taille.

Ca fait 0 allocation mémoire, 0 copie, mais ca te permet d'accéder au contenu de la chaine de caractères de manière "tout à fait naturelle".

Mieux encore, imaginons que tu ais une chaine de caractères qui contienne une phrase complete, par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

std::string laPhrase{"IMO, C++ is the best and the coolest programming language in the world"};

je peux, très facilement, récupérer tous les mots de la phrase, dans un tableau par exemple, et les transférer y compris par valeur sans que cela n'occasionne la moindre allocation mémoire.

Voici un exemple pour t'en convaincre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
void printWord(std::string_view word){ // on tansfert un pointeur et une taille !!!
    static size_t count{1}; // pour garder le nombre de mot affichés ..
    std::cout<<"word "<<count<<" '"<<word<<"'\n";
    ++count;
}
int main(){
    std::string laPhrase{"IMO, C++ is the best and the coolest programming language in the world"};
    std::vector<std::string_view> words;
    size_t lastEnd{0};
    while(lastEnd <std::string::npos ){
        size_t pos=laPhrase.find(" ", lastEnd);
        // il faudra appliquer un traitement spécial au dernier mot
        // de la phrase :P
        if(pos!= std::string::npos){
            words.emplace_back(laPhrase.data()+lastEnd,pos-lastEnd);
            lastEnd = pos+1;
        }else{
            words.emplace_back(laPhrase.data()+lastEnd);
            lastEnd = pos;
        }
    }    
    for(auto const & it : words){
        printWord(it);
    }
}

Cadeau: un peu de lecture concernant std::string_view

Oui, ma liste de mots est déjà triée dans l'ordre alphabétique et ça ne compte pas dans le temps d'exécution.

Je ne suis pas sur d'avoir bien compris, mais, dans le doute: fais hyper attention au fait que, quel que soit l'algorithme de tri envisagé, essayer de trier une collection qui est déjà triée est une action qui, assez bizarrement, prendra toujours un maximum de temps parce que l'on se trouve, généralement, face à l'un des pires cas auxquels nous pourrions être confrontés

En gros je dois pouvoir regrouper les anagrammes le plus rapidement possible ; le challenge étant en moins d'une dizaine de millisecondes.

Encore une fois, qu'est ce qui t'empêche de calculer tous les anagrammes possibles pour l'ensemble des mots ... une bonne fois pour toutes

Car, a priori, le nombre d'anagrammes possible pour une chaine de caractères évolue de manière factorielle (ou peu s'en faut) par rapport au nombre de caractères de la chaine en question, si bien que trouver tous les anagrammes d'une chaine de quatre caractères ne devrait pas prendre énormément de temps. Par contre, trouver tous les anagrammes possibles d'une chaine de dix caractères risque de prendre une plombe (surtout si tu acceptes le fait que les anagrammes risquent de ne rien vouloir dire, voire même d'être totalement imprononçables )

Par contre, si tu peux avoir, pour chaque chaine de caractères de ton dictionnaire, une liste de l'ensemble des anagrammes que cette chaine de caractères autorise, le parcoure de cette liste -- et la recherche éventuelle d'un anagramme donné -- restera ** relativement ** rapide.

Et donc, quitte à ce que cela prenne, effectivement, un temps bête lors de l'initialisation de l'application, pourquoi ne pas créer ces listes d'anagrammes (une par mot) dés le départ

[Bousk]

Je vais p-e dire une connerie, parce que tu écris beaucoup mais ne montres absolument aucun code.
Les performances vont dépendre en grande partie de tes structures de données. Et malgré toute ta prose, je ne me l'imagine pas.
Si tu as vraiment une collection immense, alors une des meilleures optimisation pourrait être dans les cache miss.
Alors voilà ce que je ferai pour ma part.
Comparer des chaînes c'est le mal absolu.
Mais un ordinateur est assez puissant pour comparer des nombres.
Il faut ramener les chaînes à un nombre.
Pour cela, et puisque c'est la notion d'anagramme qui nous intéresse, j'utiliserai une structure de X entiers qui permette de stocker la représentation d'un mot.
Ça pourrait être 26 entiers et chaque indique combien de a, b, ... sont dans ce mot.
Très vite, on peut diminuer le nombre de nombres pour tirer partie des types plus grands que le processeur sait gérer.
Si l'on sait qu'une lettre ne peut au maximum apparaître que Y fois dans un mot, alors on peut encore améliorer cette représentation.
Le but est de faire tenir la représentation sur quelques u64 que le processeur saura comparer en une poignée de cycles.
À terme, tu as une collection de map<représentation, mots anagrammes ayant cette représentation>.
À partir de là, tu peux très simplement créer la représentation de n'importe quel mot, puis trouver tous ses anagrammes.

Enfin, je vois pas pourquoi le sort serait le problème : le sort est fait une unique fois, et la liste peut très bien être enregistrée après ce sort; elle n'aura donc plus à être triée à son chargement.

[ABD-Z]

Non, justement, ca ne fait aucune copie de la chaine de caractère: ca stocke uniquement l'adresse du premier caractère qui t'intéresse, et une taille.

Ca fait 0 allocation mémoire, 0 copie, mais ca te permet d'accéder au contenu de la chaine de caractères de manière "tout à fait naturelle".

Du coup je peux pas appliquer de modifications dessus. Je viens de tester ton code avec string_view et on peut pas les trier.

j'utiliserai une structure de X entiers qui permette de stocker la représentation d'un mot.
Ça pourrait être 26 entiers et chaque indique combien de a, b, ... sont dans ce mot.

Voilà, j'ai pensé à faire ça hier : je fais une map (oredered de préférence) qui compte les lettres. Cette map là est la clef et puis voilà. Comme ça on parcourt le mot en une seul fois.

À terme, tu as une collection de map<représentation, mots anagrammes ayant cette représentation>.
À partir de là, tu peux très simplement créer la représentation de n'importe quel mot, puis trouver tous ses anagrammes.

Exactement, c'est ça!

Enfin, je vois pas pourquoi le sort serait le problème : le sort est fait une unique fois, et la liste peut très bien être enregistrée après ce sort; elle n'aura donc plus à être triée à son chargement.

En fait le sort je le fais pour chaque mot que j'envoie en tant que clef.
Imaginons nous sommes dans l'index XXX de la liste et on a le mot "marre". Je le trie, donc "marre" devient "aemrr", et ainsi je fais map["aemrr"].push_back(XXX).
Mais bon je crois que cette méthode est nul, même avec smoothsort... Je vais comme ce que tu m'as compter les lettres que je stocke dans une map que je stocke en tant que clef dans une autre map. Donc, lieu d'avoir unordered_map<string, vector<int>>, j'aurais unordered_map<map<char,int>, vector<int>>
Bon, je vais essayer ça et je vous redirai.

[LittleWhite]

Merci Bousk !
Cela fait un moment que j'ai dans ma tête l'idée de transformer le mot en nombre et vous avez mis le doigt sur une solution possible. Merci !

[ABD-Z]

Merci Bousk !
Cela fait un moment que j'ai dans ma tête l'idée de transformer le mot en nombre et vous avez mis le doigt sur une solution possible. Merci !

Attendez, transformer le mot en nombre? Du coup ce n'est plus compter les lettres...

J'avais pensé à cette technique, mais il m'a semblé que ce n'était pas adapté.
Imaginons que la lettre A vaut 1 et B vaut 2. Si on transforme AA en un nombre ça fait 2 et B 2 aussi.... Donc ça n'est pas viable.
Après avec les valeurs en ASCII c'est différent.
En tout cas je sais pas si c'est de cette manière qu'il faudrait transformer le mot en un nombre.

[LittleWhite]

Oui, évidemment que la somme ne fonctionne pas. Mais Bousk a apporté une autre idée, qui n'est pas la somme et qui permet de "réduire" la chaine en un nombre unique.

[ABD-Z]

Effectivement, il a parlé de structure de 26 entiers qui comptent les lettres. Employer une structure pourrait être plus performante qu'une map. Seulement, il a plus de conditions à faire car il faut tester la condition de chaque lettre du style :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
if(mot[i] == 'A'){
    ++struct.a;
}
if(mot[i] == 'B'){
    ++struct.b;
}
if(mot[i] == 'C'){
    ++struct.c;
}
if(mot[i] == 'D'){
    ++struct.d;
}

Ce qui est assez long pour 26 lettres.

[LittleWhite]

Oui, en théorie. En pratique, on peut faire plus immédiat. On partira dans ce cas, du principe que tout est en majuscules (ou en minuscule, mais le code est à adapter)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
index = mot[i] - 'A';
*(&myStruct.a + index)++;

L'idée est d'obtenir l'adresse du premier élément de la structure afin de déplacer le pointeur, vers l'élément voulu. Il faut alors faire attention à avoir une structure paquée.

[ABD-Z]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
index = mot[i] - 'A';
*(&myStruct.a + index)++;

L'idée est d'obtenir l'adresse du premier élément de la structure afin de déplacer le pointeur, vers l'élément voulu. Il faut alors faire attention à avoir une structure paquée.

Bien vu l'ancien!
Mais tu veux dire quoi par structure paquée?
Une structure comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct alphabet{
short a;
short b;
short c;
short d;
short e;
short f;
short g;
.
.
.
.
};

[LittleWhite]

En utilisant les short, il peut y avoir un problème, car le compilateur pourrait vouloir aligner les champs sur 4 octets.
En forçant le compilateur a rassembler les donnés, vous pouvez alors assurer que les champs sont mis les uns derrière les autres.
Voici une explication : https://carlosvin.github.io/posts/cpp-pragma-pack/en/

[ABD-Z]

Je viens de tester avec les int et les short. Ça marche plutôt bien, même avec les char!
https://onlinegdb.com/Byp8njagv
Après, ça peut changer d'un compilateur à un autre. En tout cas, dans mon cas de figure, tous les champs de ma structure auront le même type.

[Mat.M]

Voilà, j'ai pensé à faire ça hier : je fais une map (oredered de préférence) qui compte les lettres.

bonsoir si on veut des performances je ne pense pas que des conteneurs de la STL comme std::map ou autres soient vraiment appropriés.
Il faut utiliser carrément des pointeurs sur des structures de style C comme des listes chainées...et là on aura des performances.
L'inconvénient est qu'il faut faire du code pour effectuer un tri sur les chaînes de caractère.
Mais avec des pointeurs là on adresse directement la mémoire.
Avec les conteneurs de la STL comme std::map il y a des tas de séquence de code qui s'exécute avant de pouvoir adresser le moindre élément sans compter la gestion des exceptions derrière

[koala01]

bonsoir si on veut des performances je ne pense pas que des conteneurs de la STL comme std::map ou autres soient vraiment appropriés.
Il faut utiliser carrément des pointeurs sur des structures de style C comme des listes chainées...et là on aura des performances.

Si tu pars sur une structure de liste chainée perso, tu n'y gagnera absolument rien... autant utiliser std::list alors

Quant à std::map, c'est simplement un arbre binaire de recherche (un arbre rouge noir, pour être précis) capable de maintenir ensemble une clé pour le tri et une valeur. Et il sera aussi efficace que n'importe quel arbre rouge noir que tu pourrais envisager de développer par toi-même

Après, il se peut que, selon l'usage que tu fais des données, un arbre binaire ne soit -- effectivement -- pas la structure la plus adaptée, parce que tu passerais, par exemple, plus de temps à parcourir l'ensemble des éléments qu'autre chose.

Mais, si tu passes, effectivement, plus de temps à rechercher un élément particulier parmi tous ceux qui existent, std::set et std::map sont les collections qu'il te faut, surtout si tu dois rechercher un élément particulier parmi un grand nombre de possibilités

Et plus le nombre de possibilités augmentera, plus tu auras intérêt à utiliser ce genre de structures

L'inconvénient est qu'il faut faire du code pour effectuer un tri sur les chaînes de caractère.
Mais avec des pointeurs là on adresse directement la mémoire.

Et, dis moi, que crois tu que font std::list et std::map, si ce n'est accéder "aussi directement" à la mémoire que possible (ou, du moins, aussi directement ce que ce toi tu serais capable de le faire en implémentant tes propres structures)

Bien sur, elles "t'enrobent" les accès mémoire à coup de begin, end, search, clear et autres, mais, si tu veux éviter au maximum à l'utilisateur de faire des conneries, tu y viendras aussi, non

Avec les conteneurs de la STL comme std::map il y a des tas de séquence de code qui s'exécute avant de pouvoir adresser le moindre élément

Beaucoup moins que tu ne semble le croire

Et, en tout état de cause, vraiment pas grand chose que tu n'aurais du faire par toi-même pour assurer un minimum la sécurité des données que tu veux manipuler

L'un dans l'autre, ce qui "coute" réellement en performance, c'est l'utilisation des itérateur, qui imposent une indirection supplémentaire... Et, le jour où une indirection, même multipliée par des milliers d'accès posera réellement à elle seule des problèmes de performances, j'aimerais quand même être présent pour y assister

sans compter la gestion des exceptions derrière

Ah, de fait, tu pourrais complètement "zapper" les vérifications d'intégrité en tous genres, et peut-être gagnerais tu quelques précieuses micro secondes. As tu seulement la moindre idée des problèmes auxquels tu sera confronté le jour où tu te rendra compte que tu n'est pas au pays des bisounours

[Mat.M]

Bien sur, elles "t'enrobent" les accès mémoire à coup de begin, end, search, clear et autres, mais, si tu veux éviter au maximum à l'utilisateur de faire des conneries, tu y viendras aussi, non

je suis d'accord n'empêche que le code intermédiaire cela peut représenter un coût à l'exécution.
Pour cela on peut peut-être utiliser un profiler et tracer le code de la STL

modif de mon message : 29/07/2020

Si je fais un find dans une std::multimap pour mon noyau de jeu 3d,voilà ce qui se passe en traçant dans la STL

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
std::multimap<std::wstring  ,LPDIRECT3DTEXTURE9> m_mpTextures;
std::map<std::wstring,LPDIRECT3DTEXTURE9>::iterator it;
std::wstring strTextureName(L"");
 
it=m_mpTextures.find(strTextureName);
//....
 
iterator find(const key_type& _Keyval)
		{	// find an element in mutable sequence that matches _Keyval
		iterator _Where = lower_bound(_Keyval);
		return (_Where == end()
			|| _DEBUG_LT_PRED(this->_Getcomp(),
				_Keyval, this->_Key(_Where._Mynode()))
					? end() : _Where);
		}
 
///....         
_Nodeptr _Lbound(const key_type& _Keyval)
		{	// find leftmost node not less than _Keyval
		_Nodeptr _Pnode = _Root();
		_Nodeptr _Wherenode = this->_Myhead;	// end() if search fails
 
		while (!this->_Isnil(_Pnode))
			if (_DEBUG_LT_PRED(this->_Getcomp(), this->_Key(_Pnode), _Keyval))
				_Pnode = this->_Right(_Pnode);	// descend right subtree
			else
				{	// _Pnode not less than _Keyval, remember it
				_Wherenode = _Pnode;
				_Pnode = this->_Left(_Pnode);	// descend left subtree
				}
 
		return (_Wherenode);	// return best remembered candidate
		}

donc dans la méthode _Lbound le système c'est également des listes chaînées ce qui revient un peu au même

Moi je dis faut voir

[ABD-Z]

Là j'ai un problème qui n'est pas traité sur Internet : j'ai l'impression qu'on ne peut pas mettre une map en tant que clef dans une unordered_map, j'ai l'erreur C2064 qui dit que le terme ne correspond pas à une fonction qui prend 1 arguments. Bon je crois que je vais utiliser que la structure puis tant pis pour la map.

[ABD-Z]

Bah tiens, j'ai le même problème bizarrement quand je veux insérer en tant que clef ma structure dans mon unordered map.
Le problème vient de cette ligne unorderedmap[struct_clef].push_back(indice_mot)
Quand je commente cette ligne, il n'y a plus de problèmes de compilations..

[koala01]

Le fait est que la clé d'une (unordered_)map doit, au minimum, être comparable par "plus petit que" pour que le tri puisse s'effectuer...

C'est automatique pour les valeurs numériques de tous genres, mais, pour les structures personnelles (y compris celles qui sont fournies par la bibliothèque standard), il faut fournir l'opérateur <