Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Performance et algorithmie en C++


Sujet :

C++

  1. #21
    Rédacteur/Modérateur

    Citation Envoyé par ABD-Z Voir le message
    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.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  2. #22
    Membre averti
    Effectivement, les structures en tant que clefs ne sont pas si triviales que ça.
    Ma structure contient 28 champs comprenant les lettres de l'alphabet plus deux signes (tirer et apostrophe).
    J'ai donc rajouté la fonction operator== dans la structure qui, comme son nom l'indique, teste si les champs de deux structures sont égals. J'ai testé deux méthodes : -une avec une boucle parcourant les champs et qui retourne FAUX lorsque une égalité n'est pas respectée et donc VRAI lorsque toutes les égalités le sont. -la deuxième étant de faire un retourne bourrin avec les 27 &&. Celles avec la boucle for m'a semblé un petit chouia meilleure, mais ce n'est pas perceptible que ça.
    J'ai dû aussi une classe/structure de hashage contenant la fonction operator(). J'ai optimisé la fonction de hashage en ne calculant uniquement les champs qui une valeur supérieure à 0.
    Donc, pour chaque champs qui a une valeur supérieur à 0, j'effectue un hash combine comme ceci
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    template <class T>
    inline void hash_combine(std::size_t & s, const T & v)
    {
    	std::hash<T> h;
    	s ^= h(v) + 0x9e3779b9 + (s << 6) + (s >> 2);
    }


    Bien sûr, dans la fonction qui parcourt la liste de mots, je ne fais pas de copie de chaînes de caractères, j'initialise à chaque fois ma structure, et fonction de la lettre rencontrée, j'incrémente le champ correspondant.
    Et bien devinez quoi!
    Ma technique de copie de string puis smoothsort n'a pas à rougir face aux structures! Malgré toutes mes optimisations, mettre une structure de 28 champs dans une unordered_map s'est avéré plus lent...
    Il ne me reste plus qu'à tester avec une map en tant que clef, il y a moyen que cela soit plus performant.

    Citation Envoyé par Bousk Voir le message
    ...
    C'est super intéressant comme optimisation. Merci pour la piste. Et en plus c'est assez facile pour tester l'égalité.
    J'avais bizarrement pas vu ton message quand j'ai posté le mien sur la structure en tant que clef.
    Je vous en donnerai des nouvelles

  3. #23
    Membre averti
    Performance correcte
    Bonjour,
    Je viens de faire à peu près ce que Bousk m'a dit de faire. Sauf que dans ma représentation, une structure, j'utilise deux champs de 64 bits. J'ai regardé les fréquences des lettres en français, pour optimiser le temps de calcul, et j'ai donc représenté deux champs de cette manière :
    champ0 'wjyfvgmdltnie
    champ1 -zhxqhbpcuorsa

    Comme on peut le voir, plus on est vers la droite plus les lettres sont fréquentes. J'ai donc codé une fonction pow, mais à la fin je me suis rendu compte que ça ne servait à rien puisque je peux en fonction de la lettre, attribuer une valeur (unité, dizaine, centaine etc).

    Cette méthode est nettement bien plus performante que celle avec smoothsort. Je gagne environ 400 ms de différence.
    Cependant, j'ai une dernière petite question concernant la méthode de hashage. En effet, notre structure contenant les deux champs de 64 bits qui comptent les lettres doivent être hashés.
    J'utilise la méthode de hashage de boost :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    template <class T>
    inline void hash_combine(std::size_t & s, const T & v)
    {
    	std::hash<T> h;
    	s ^= h(v) + 0x9e3779b9 + (s << 6) + (s >> 2);
    }


    Et donc dans la fonction operator(), j'appelle deux fois la fonction hash_combine car nous avons deux champs dans notre structure. Il n'y a pas moyen de réduire le nombre d'appel de hash_combine à 1?
    J'ai essayé en faisant hash_combine(hash_result, structure.champ0 + structure.champ1), ça marchait, mais je sais que c'est pas top car on peut risquer des collisions.

  4. #24
    Rédacteur/Modérateur

    Citation Envoyé par ABD-Z Voir le message
    Je gagne environ 400 ms de différence.
    Quasi 25%, pas mal.

    Si tu crains les collisions de hash, utilise une map et l'opérateur < plutôt qu'une unordered map ?
    Tu peux aussi certainement avoir un packing plus malin et faire tenir le tout sur 64 bits.
    L'exemple avec base 10 était là juste pour introduire le concept et te permettre de le comprendre pour te l'approprier et l'adapter.
    Avec 3 bits par lettre, il faut 84 bits pour les 26 lettres et 2 symboles. Il faut donc sauver 20 bits.
    3 bits ça permet d'avoir 7 occurrences d'une lettre ou symbole.
    Je pense que la plupart des mots n'auront jamais 7 fois une lettre donnée ?
    Je pense aussi que certaines lettres, et les symboles, ne se retrouvent jamais plus de 4 fois dans un mot, ce qui permet de les représenter sur 2 bits, voire 1 seule fois (l'apostrophe ?), et ils tiennent alors sur 1 bit.
    Et si tout rentre sur 64 bits, plus aucun problème de hashing ou autre.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  5. #25
    Membre averti
    Citation Envoyé par Bousk Voir le message

    Si tu crains les collisions de hash, utilise une map et l'opérateur < plutôt qu'une unordered map ?
    C'est une piste aussi à explorer. Mais map est apparemment plus lent. Corrigez-moi si j'ai tort.

    Citation Envoyé par Bousk Voir le message
    Quasi 25%, pas mal.
    Avec 3 bits par lettre, il faut 84 bits pour les 26 lettres et 2 symboles. Il faut donc sauver 20 bits.
    3 bits ça permet d'avoir 7 occurrences d'une lettre ou symbole.
    Je pense que la plupart des mots n'auront jamais 7 fois une lettre donnée ?
    Bien-sûr la plupart des mots n'auront pas 7 fois une lettre donnée quoique si pour le e et les autres lettres qui se répètent facilement. On peut vérifier grâce à ce site : https://www.forum.exionnaire.com/dic...re-dans-un-mot
    Mais, j'essaye en même temps de faire quelque chose de relativement absolu, c'est-à-dire de faire un programme qui peut fonctionner avec n'importe quel mot même inventé.

###raw>template_hook.ano_emploi###