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.

[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]

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.

[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

[Bousk]

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

Je vois pas bien par quelle noeud au cerveau tu finis avec une map comme clé ? Ou un vector<int> en valeurs ?
La clé c'est la structure de représentation. Et les valeurs sont bien entendus les mots...
Je l'ai pourtant écrit noir sur blanc

À terme, tu as une collection de map<représentation, mots anagrammes ayant cette représentation>.

Qui sera bien sûr de la forme std::map<representation, std::vector<std::string>>

Tu as un premier jet qui utilise un short pour chaque lettre : ok, mais on peut beaucoup mieux faire.
Déjà, une lettre sera jamais présente un nombre négatif de fois. Donc unsigned.
Ensuite, une lettre peut être présente... 10 fois au max dans un mot ? Mettons 10 pour simplifier.
La représentation ne sera rien de plus qu'un nombre à 26 chiffres. Les unités ? Ça s'appelle A. Les dizaines B, ... exactement de la même façon que tu comptes depuis toujours il me semble, ou juste comment fonctionne l'écriture d'un nombre en base 10. Et la base peut être adaptée.
Mais commençons avec cette base 10.
Un u64 max ça vaut 18,446,744,073,709,551,615. C'est 20 chiffres, donc on va en utiliser 19 pour être sûr (donc [a,s]).
Il en reste 8, que l'on peut rentrer dans un u32.
Et bien pour créer la représentation, il s'agit d'un bête parcours de la chaîne et d'opérations triviales.
À vue de nez :

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
struct Repr {
  uint64_t a{0};
  uint32_t b{0};
};
Repr Compute(const std::string& str)
{
  Repr ret;
  for (char c : str)
  {
    if (c < 't')
    {
      uint64_t index = pow(10, c - 'a');
      ret.a += index;
    }
    else
    {
      uint32_t index = pow(10, c - 't');
      ret.b += index;
    }
  }
  return ret;
}

Et personnellement je serais partisan de recréer un pow utilisant des entiers qui pourrait être plus performant et dont les résultats devrait être plus précis que celui du standard qui utilise des flottants.
Ou une fonction qui fait un gros switch pour chaque caractère et retourne directement le multiplier.