C++ - Différence de performance étrange !

En ajoutant 1 ligne de code (presque) anodine, mon programme devient beaucoup beaucoup plus lent...

a marqué ce sujet comme résolu.

Bonjour,

J'ai récemment lu le sujet sur 'Trichons au jeu des anagrammes vivants'. J'ai trouvé cela intéressant et j'ai donc décidé d'essayer de faire un petit programme qui résoudrait ces 'énigmes'.

J'ai réfléchi à la technologie à utiliser, à mon cahier des charges, aux algorithmes à utiliser… J'ai commencé le programme. Or, je suis maintenant confronté à une étrangeté que je n'avais encore jamais vue.

Voici les faits :

  • J'ai commencé le programme normalement et j'ai fait la première partie (c'est à dire la génération et l'enregistrement du graphe). Pour des raisons de performances, j'ai opté pour une solution plus compliquée.

  • J'ai donc recodé la quasi-totalité du code pour l'adapter à une autre solution qui serait plus performante (avec des tableaux d'int au lieu de QString et compagnie…).

  • Lors des tests de performances de la nouvelle version, j'ai été surpris par la lenteur de l'exécution. J'ai cherché ce qui pouvait être à l'origine de cela.

  • J'ai découvert que c'était une ligne de code qim[i].PossibilitesIndex.append(j); (ligne 237) qui posait, je pense, problème. Si je la supprime, le programme fonctionne beaucoup plus rapidement.

  • J'ai cherché des réponses à cette bizarrerie : mémoire registre, accès à un grand tableau, performances des QList… Je n'ai rien trouvé qui me répond à cela.

Voici un tableau des performances :

Test Temps Mots traités Temps pour un mot
Avec la ligne de code 24s 200 0.12s
Sans cette ligne de code 24s 336531 0.00007s

  • Si mes calcules sont bons, mon programme avec cette ligne est environ 1700 fois plus lent.

  • Je sollicite donc votre aide pour tout d'abord comprendre cette drôle de performance et pour pouvoir corriger mon programme.

Je suis disponible pour toute question ou pour tout renseignement complémentaire,

Merci d'avance pour votre aide,

Cordialement,

florian6973.

P. S. : Voici le code source (en C++) :

  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
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
#include <QCoreApplication>
#include <QString>
#include <QFile>
#include <QResource>
#include <QRegExp>
#include <QIODevice>
#include <QList>
#include <QVariant>
#include <QDataStream>
#include <QSettings>
#include <QChar>

#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <thread>

using namespace std;

int Alphabet[26] = { 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122 };

class InfoMot
{
public:
    int Mot[26] = { };
    QList<int> PossibilitesIndex = QList<int>();
    inline InfoMot() {}
};

QDataStream & operator << (QDataStream & out, const InfoMot & Valeur)
{
    for (int i = 0; i < 26; i++)
        out << Valeur.Mot[i];
    out << Valeur.PossibilitesIndex;
    return out;
}
QDataStream & operator >> (QDataStream & in, InfoMot & Valeur)
{
    for (int i = 0; i < 26; i++)
        in >> Valeur.Mot[i];
    in >> Valeur.PossibilitesIndex;
    return in;
}

QDataStream & operator << (QDataStream & out, const QList<InfoMot> & Valeur)
{
    for (int i = 0; i < Valeur.length(); i++)
        out << Valeur[i];
    return out;
}

QDataStream & operator >> (QDataStream & in, QList<InfoMot> & Valeur)
{
    for (int i = 0; i < Valeur.length(); i++)
    {
        InfoMot temp = InfoMot();
        in >> temp;
        Valeur.append(temp);
    }
    return in;
}

Q_DECLARE_METATYPE(InfoMot)
Q_DECLARE_METATYPE(QList<InfoMot>)

void __fastcall print(QString text, bool newline = true)
{
    cout << text.toLatin1().constData();
    if (newline)
        cout << endl;
}

void __fastcall SortQString(int mot[26], int mots[26])
{
    int mot2[25] = { };
    std::fill_n(mot2, 25, 200);
    for (int i = 0; i < mot[0]; i++)
        mot2[i] = mot[(i + 1)];
    std::sort(std::begin(mot2), std::end(mot2));
    mots[0] = mot[0];
    for (int i = 1; i <= mot[0]; i++)
        mots[i] = mot2[(i - 1)];
}

void QStringToAInt(QString mot, int wordc[26])
{
    wordc[0] = mot.length();
    for (int zk = 0; zk < mot.length(); zk++)
        wordc[(zk + 1)] = (int)(mot.at(zk).toLatin1());
}

void __fastcall AffectArray(int words[336531][26], int wc[26], int ib)
{
    for (int j = 0; j < 26; j++)
        words[ib][j] = wc[j];
}

void __fastcall CopierTab(int words[336531][26], int sort[26], int ib)
{
    for (int j = 0; j < 26; j++)
        sort[j] = words[ib][j];
}

bool __fastcall Equals(int taba[26], int tabb[26])
{
    if (taba[0] != tabb[0])
        return false;
    else
    {
        for (int i = 1; i <= taba[0]; i++)
            if (taba[i] != tabb[i])
                return false;
        return true;
    }
}

QString __fastcall ArrayToQString(int str[26])
{
    QString ret = "";
    for (int i = 1; i <= str[0]; i++)
        ret.append((char)str[i]);
    return ret;
}

static QList<InfoMot> qim2 = QList<InfoMot>();

void Queue(int i, int p, int j)
{
    while (qim2.length() < i)
        qim2.append(InfoMot());
    qim2[i].PossibilitesIndex[p] = j;
}

int main(int argc, char *argv[])
{
    qRegisterMetaTypeStreamOperators<InfoMot>("InfoMot");
    qMetaTypeId<InfoMot>();
    qRegisterMetaTypeStreamOperators<QList<InfoMot>>("QList<InfoMot>");
    qMetaTypeId<QList<InfoMot>>();
    print("Bonjour !\n");
    try
    {
        QString dep = "";
        QString arr = "";
        if (argc == 3)
        {
            dep = argv[1];
            arr = argv[2];
        }
        else
        {
            print("Entrer le mot de départ + ; + le mot d'arrivé : ", false);
            string ep = "";
            cin >> ep;
            int eps = ep.find(';');
            dep = ep.substr(0, eps).c_str();
            arr = ep.substr((eps + 1), ep.size()).c_str();
        }
        print("Mot de depart : " + dep + " ; Mot d'arrive : " + arr + " !\n");
        auto start = std::chrono::high_resolution_clock::now();
        start = std::chrono::high_resolution_clock::now();
        if (!QFile("dic.graph").exists())
        {
            print("Chargement du dictionnaire et suppression des accents !");
            QFile f(":/motsfr/words.txt");
            f.open(QIODevice::ReadOnly);
            QByteArray tba = f.readAll();
            f.close();
            QStringList textlines = ((QString)tba.constData()).split('\n');
            static QList<InfoMot> qim = QList<InfoMot>();
            static int qima[336531][26] = { };
            for (int i = 0; i < textlines.length(); i++)
            {
                textlines[i] = textlines[i].trimmed().replace("\r", "").replace(QRegExp("à|â|ä"), "a").replace(QRegExp("é|è|ê|ë"), "e").replace(QRegExp("ï|î"), "i").replace(QRegExp("ô|ö"), "o").replace(QRegExp("ù|û|ü"), "u").replace("ÿ", "y");
                InfoMot im = InfoMot();
                std::fill_n(im.Mot, 26, 200);
                QStringToAInt(textlines[i], im.Mot);
                int pa[26] = { };
                std::fill_n(pa, 26, 200);
                SortQString(im.Mot, pa);
                AffectArray(qima, pa, i);
                qim.append(im);
            }
            print("Creation du graphe et des anagrammes !");
            for (int i = 0; i < qim.length(); i++)
            {
                int anagrammesp[702][26] = { }; //1+26+25+25*26=702
                AffectArray(anagrammesp, qima[i], 0);
                int tt = 1;
                if (qima[i][0] < 25)
                    for (int j = 0; j < 26; j++)
                    {
                        int cop[26] = { };
                        std::fill_n(cop, 26, 200);
                        CopierTab(qima, cop, i);
                        cop[cop[0]] = Alphabet[j];
                        int pa[26] = { };
                        std::fill_n(pa, 26, 200);
                        SortQString(cop, pa);
                        AffectArray(anagrammesp, pa, tt);
                        tt++;
                    }
                if (qima[i][0] > 1)
                    for (int j = 1; j <= qima[i][0]; j++)
                    {
                        int cop[26] = { };
                        std::fill_n(cop, 26, 200);
                        CopierTab(qima, cop, i);
                        cop[j] = 200;
                        int pa[26] = { };
                        std::fill_n(pa, 26, 200);
                        SortQString(cop, pa);
                        AffectArray(anagrammesp, pa, tt);
                        tt++;
                    }
                for (int j = 1; j <= qima[i][0]; j++)
                    for (int k = 0; k < 26; k++)
                    {
                        int cop[26] = { };
                        std::fill_n(cop, 26, 200);
                        CopierTab(qima, cop, i);
                        cop[j] = Alphabet[k];
                        int pa[26] = { };
                        std::fill_n(pa, 26, 200);
                        SortQString(cop, pa);
                        AffectArray(anagrammesp, pa, tt);
                        tt++;
                    }
                for (int j = 0; j < 336531; j++)
                    if (j != i)
                    {
                        for (int k = 0; k < 702; k++)
                            if ((anagrammesp[k][0] != 0) && (anagrammesp[k][0] < 26))
                            {
                                if (Equals(qima[j], anagrammesp[k]))
                                    qim[i].PossibilitesIndex.append(j);
                            }
                            else
                                break;
                    }
            }
            QSettings graphef("dic.graph", QSettings::IniFormat);
            graphef.setValue("Graphe", qVariantFromValue(qim));
            graphef.sync();
        }
        print("Chargement du graphe !");
        QList<InfoMot> graphe = QList<InfoMot>();
        QSettings graphef("dic.graph", QSettings::IniFormat);
        graphe = graphef.value("Graphe", qVariantFromValue(QList<InfoMot>())).value<QList<InfoMot>>();
        print("Calcul...");
        //TODO (dijkstra's algorithme)
        std::cout << "Temps : " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start).count() << " ms !" << std::endl;
    }
    catch (...)
    {
        print("ERREUR inconnue !");
    }
    print("\nAu revoir !");
    return 0;
}

P.S. 2 : Comment fais-tu pour mettre un secret sur tout le code ? Merci.

+0 -0

C'est bien la ligne 237 que tu supprimes ?

Si c'est le cas (et en n'analysant que très rapidement ton code), je parierais sur une optimisation du compilateur. En enlevant la ligne 237 (et évidemment la condition qui l'accompagne), la boucle de la ligne 230 n'a plus aucun effet de bord, et le compilateur détermine probablement qu'il peut l'éliminer entièrement.

Est-ce que tu observes la même différence si tu compiles sans optimisation ?

+1 -0

Oui, je me suis trompé de numéro. J'ai corrigé l'erreur. Merci :) ! Je vais essayer et j'éditerai la réponse ! Merci pour ces idées !

EDIT : Voici les résultats : En enlevant les optimisations ça donne les mêmes résultats à quelques secondes près.

EDIT 2 : Si je mets un bout de code dans la condition, genre int y = 5; cela donne le même résultat que sans la ligne.

+0 -0

Ton code me laisse dubitatif… mélange de bas niveau (fastcall) et haut niveau (Qt), de QList et tableau statique style C, quelques fonctions avec un main très gros, des variables static, utilisation de QSetting et des méta-objets Qt, etc. Ca me laisse le sentiment que tu essaies d'optimiser, mais n'importe comment

Sinon, pour ton problème, append produit une allocation donc contre-performant. Faut faire un reserve ou un resize avant. Et un tableau style vector sera plus performant (probablement) qu'une liste.

+5 -0

Si c'est le cas (et en n'analysant que très rapidement ton code), je parierais sur une optimisation du compilateur. En enlevant la ligne 237 (et évidemment la condition qui l'accompagne), la boucle de la ligne 230 n'a plus aucun effet de bord, et le compilateur détermine probablement qu'il peut l'éliminer entièrement.

SimSonic

En fait, je ne serais pas surpris que ce soit la boucle de la ligne 186 qui soit éliminée. Sans modification de qim, elle ne semble pas contenir d'effets de bord.

+0 -0

Merci pour ton retour et tes idées !

Effectivement, on peut dire que le code est un peu n'importe comment. Au départ, j’essayai de me concentrer sur les algorithmes et leurs complexités. Après, au vu des performances, je me suis lancé dans une optimisation partielle. De plus, je ne suis pas trop habitué à faire des optimisations avec le C++.

Je vais testé des idées et je te tiens au courant du résultat (soit par un nouveau poste, soit par une édition) ! Merci encore pour ton aide !

EDIT SimSonic : J'ai essayé de modifier qim dans la boucle for commençant ligne 186 en ajoutant juste un élément dans la liste à la fin de la boucle => les performances reste comme sans la ligne. Etrange…

EDIT gbdivers : Les resize/reserve ne changent rien aux performances. :( Je vais essayer avec un std::vector. (Je suis aussi preneur pour quelques conseils en optimisation :))

+0 -0

Je me suis permit d'éditer ton message, au niveau du code, pour :

  • préciser le langage et donc le colorer
  • le mettre dans un "secret".

Je te laisse regarder la source pour voir. Tu peux utiliser l'éditeur pour ça (élément tout à droite).

Concernant le prob, éliminer une ligne avec autant de conséquence qu'un append est, pour moi, une mauvaise idée. Cela change toute la logique et le comportement de l'algo. Tu ferais mieux de faire tourner un profiler pour voir où tu passes du temps.

+2 -0

Merci pour les balises Markdown et pour tes idées ! :)

Pour la suppression de ligne, tu as tout à fait raison, l'algo ne marche que si elle n'est pas supprimée ; c'est embêtant…

Je vais voir pour faire tourner un profiler.

+0 -0

Il n'y a pas besoin des optimisations du compilateur pour expliquer la différence de performances, àmha.

En effet, avec la ligne mystère, ta boucle est : « fais deux millions d'append ». Sans la ligne, ta boucle est : « compter de zéro à deux millions ». Dans ce deuxième cas, tu ne fais qu'une opération arithmétique sur un registre, ce qui est diablement rapide. Dans le premier, tu dois te payer quelques allocations mémoire pour augmenter la taille de ton tableau de temps en temps. Même si la bibliothèque standard est bien optimisée, ce n'est pas gratuit. Je pense que ta différence de performances vient simplement de là.

C'est typiquement le genre de choses qu'un profiler pourra te dire. Sinon, fais un programme très simple qui se contente de faire 15 allocations mémoire (et qui écrit quelque chose dans la mémoire allouée, sinon le compilateur risque d'optimiser ça en no-op) et mesure le temps que ça prend. Si c'est le même temps que la différence entre tes deux programmes, tu sais d'où elle vient.

Par ailleurs, cette ligne semble effectivement indispensable à ton algorithme, il vaut donc mieux éviter « d'optimiser » à tort et à travers. ;)

+2 -0

Lu'!

Avant d'avoir un code rapide, c'est bien d'avoir un code lisible (et qui fonctionne). Pour pouvoir optimiser, c'est bien aussi de découper les choses (ça permet de mieux identifier les éléments).

Il y a un certain nombre de choses qui peuvent être faites de ce côté. En soit, je trouve que l'utilisation des conteneurs de Qt est superflue (pareil pour la lecture du fichier qui ne fait rien de particulier).

Aussi, je verrais les éléments suivants :

  • les constantes en dur dans le code c'est cracra, les déclarer dans une variable const (même globale dans un namespace anonyme) serait salvateur.
  • les tableaux statiques du C, il vaut mieux les bannir au profit de std::array.
  • le main est 100 fois trop long, un découpage en fonction sauverait des vies (surtout qu'il est plein de copier/coller).

Une fois ces étapes faites, ton code devrait facilement diminuer de moitié. Dès lors, il sera largement plus facile à profiler pour l'optimiser.

+1 -0

J'ai lu vos réponses et j'ai testé les idées que vous avez proposées ! Merci !

Cependant, le problème n'est pas résolu…

  • J'ai tout d'abord essayé de remplacer la QList par un std::vector (j'ai aussi ajouté un resize). Les performances ont été trèsss légèrement améliorées (quelques secondes de moins pour 200 mots).

  • J'ai essayé l'idée de GuilOoo, avec un petit programme. A la vue des résultats, je pense que cela a un impact mais ce n'est pas la principale 'explication'. En effet, le programme est alors 30 fois moins rapide avec l'allocation d'une QList et 5 fois pour un vector.

  • Je pense faire tourner un profiler mais je le ferai sûrement après avoir réorganisé mon code, selon ce que m'a dit Ksass`Peuk. Merci à toi pour tes idées ! Effectivement, avant d'optimiser, je pensais comme toi. Cependant, le programme était trop lent pour le tester (environ 11 heures pour générer le graphe).

  • Je reposterai le code quand je l'aurai organisé/revu avec (sûrement) les analyses de gprof.

+0 -0

Voilà ! :) J'ai revu tout le code et je l'ai mieux organisé (selon vos conseils). Cependant, les performances ne se sont pas améliorées (22s sans la ligne pour tous les mots (336531) et 45s avec la ligne pour 200 mots).

Je ne comprends toujours pas cette lenteur. Comment l'expliquer et la corriger ? Je vous remercie d'avance pour vos idées et/ou vos réponses ! :)

Voici le code (que je peux encore revoir pour l'optimisation ou la clarté de lecture…) :

  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
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#include <QCoreApplication>
#include <QString>
#include <QFile>
#include <QResource>
#include <QRegExp>
#include <QIODevice>
#include <QList>
#include <QVariant>
#include <QDataStream>
#include <QSettings>
#include <QChar>

#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <thread>
#include <algorithm>
#include <array>

using namespace std;

typedef unsigned int uint;

enum TypeAnagramme { PlusLettre, MoinsLetttre, Modification };

namespace
{
    const int Alphabet[26] = { 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122 };
    const int TailleTableauLettre = 26;
    const int ValeurDefautLettre = 200;
    const int ValeurDefautLiens = 200;
    const int TailleMots = 336531;
    const int IndexTaille = 0;
    const int MaxTailleMot = 25;
    const int TailleAlphabet = 26;

    bool AfficherLesInfos = true;
    QString MotDeDepart = "";
    QString MotAAtteindre = "";
}

void print(QString text, bool newline = true)
{
    if (AfficherLesInfos)
    {
        cout << text.toLatin1().constData();
        if (newline)
            cout << endl;
    }
}

QString __fastcall ArrayToQString(array<int, TailleTableauLettre> str)
{
    QString ret = "";

    for (int i = 1; i <= str[IndexTaille]; i++)
        ret.append((char)str[i]);

    return ret;
}

class InfoMot
{
public:
    array<int, TailleTableauLettre> Mot;
    array<int, TailleTableauLettre> Anagramme;
    vector<int> PossibilitesIndex = vector<int>();

    inline InfoMot()
    {
        this->Mot.fill(ValeurDefautLettre);
        this->Anagramme.fill(ValeurDefautLettre);

        this->PossibilitesIndex.reserve(ValeurDefautLiens);
    }
};

class Graphe
{
public:
    inline static QStringList LireDictionnaire(QString dicochemin)
    {
        QFile filedico(dicochemin);
        filedico.open(QIODevice::ReadOnly);

        QByteArray bytes = filedico.readAll();

        filedico.close();
        return ((QString)bytes.constData()).split('\n');
    }

    inline Graphe(QStringList mots)
    {
        this->Mots.reserve(TailleMots);

        for (int i = 0; i < mots.length(); i++)
        {
            InfoMot tempmot = InfoMot();

            mots[i] = mots[i].trimmed().replace("\r", "").replace(QRegExp("à|â|ä"), "a").replace(QRegExp("é|è|ê|ë"), "e").replace(QRegExp("ï|î"), "i").replace(QRegExp("ô|ö"), "o").replace(QRegExp("ù|û|ü"), "u").replace("ÿ", "y");
            tempmot.Mot = this->QStringToAInt(mots[i]);
            tempmot.Anagramme = this->SortQString(tempmot.Mot);

            this->Mots.insert(this->Mots.end(), tempmot);
        }
    }

    inline void GenererGraphe()
    {
        for (uint i = 0; i < this->Mots.size(); i++)
        {
            print("Numero du mot : " + QString::number((i + 1)) + " ; mot : " + ArrayToQString(this->Mots[i].Mot) + " !");

            vector<array<int, TailleTableauLettre>> anagrammes = vector<array<int, TailleTableauLettre>>();
            anagrammes.insert(anagrammes.end(), this->Mots[i].Anagramme);

            this->FabriquerAnagrammes(i, anagrammes);

            this->ComparerAnagrammes(i, anagrammes);
        }
    }
private:
    vector<InfoMot> Mots = vector<InfoMot>();

    inline void __fastcall ComparerAnagrammes(uint i, vector<array<int, TailleTableauLettre>>& anagrammes)
    {
        for (uint j = 0; j < this->Mots.size(); j++)
            if (j != i)
                for (uint k = 0; k < anagrammes.size(); k++)
                    if ((anagrammes[k][IndexTaille] != 0) && (anagrammes[k][IndexTaille] <= MaxTailleMot))
                    {
                        if (this->Mots[j].Anagramme == anagrammes[k])
                            this->Mots[i].PossibilitesIndex.insert(this->Mots[i].PossibilitesIndex.end(), j);
                    }
                    else
                        break;
    }

    inline void __fastcall FabriquerAnagrammes(int i, vector<array<int, TailleTableauLettre>>& anagrammes)
    {
        if (this->Mots[i].Anagramme[IndexTaille] < MaxTailleMot)
            for (int j = 0; j < TailleAlphabet; j++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::PlusLettre, this->Mots[i].Anagramme, j));

        if (this->Mots[i].Anagramme[IndexTaille] > 1)
            for (int j = 1; j <= this->Mots[i].Anagramme[IndexTaille]; j++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::MoinsLetttre, this->Mots[i].Anagramme, j));

        for (int j = 1; j <= this->Mots[i].Anagramme[IndexTaille]; j++)
            for (int k = 0; k < TailleAlphabet; k++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::Modification, this->Mots[i].Anagramme, j, k));
    }

    inline array<int, TailleTableauLettre> __fastcall SortQString(array<int, TailleTableauLettre>& motatrier)
    {
        array<int, MaxTailleMot> mottemptri;
        mottemptri.fill(ValeurDefautLettre);

        for (int i = 0; i < motatrier[IndexTaille]; i++)
            mottemptri[i] = motatrier[(i + 1)];

        std::sort(std::begin(mottemptri), std::end(mottemptri));

        array<int, TailleTableauLettre> mottrie;
        mottrie.fill(ValeurDefautLettre);

        mottrie[IndexTaille] = motatrier[IndexTaille];
        for (int i = 1; i <= motatrier[IndexTaille]; i++)
            mottrie[i] = mottemptri[(i - 1)];

        return mottrie;
    }

    inline array<int, TailleTableauLettre> __fastcall QStringToAInt(QString& mot)
    {
        array<int, TailleTableauLettre> valinint;
        valinint.fill(ValeurDefautLettre);

        valinint[IndexTaille] = mot.length();
        for (int i = 0; i < mot.length(); i++)
            valinint[(i + 1)] = (int)(mot.at(i).toLatin1());

        return valinint;
    }

    inline array<int, TailleTableauLettre> CreateAnagramme(TypeAnagramme type, array<int, TailleTableauLettre>& mot, uint j, uint k = 0)
    {
        array<int, TailleTableauLettre> motmodifie = mot;

        switch (type)
        {
        case TypeAnagramme::PlusLettre:
            motmodifie[motmodifie[0]] = Alphabet[j];
            break;

        case TypeAnagramme::MoinsLetttre:
            motmodifie[j] = ValeurDefautLettre;
            break;

        case TypeAnagramme::Modification:
            motmodifie[j] = Alphabet[k];
            break;
        }

        motmodifie = this->SortQString(motmodifie);

        return motmodifie;
    }
};

namespace General
{
    void ChargerMot(int argc, char *argv[])
    {
        if (argc >= 3)
        {
            MotDeDepart = argv[1];
            MotAAtteindre = argv[2];

            if (argc == 4)
                if (((string)argv[3]) == "nocout")
                    AfficherLesInfos = false;
        }
        else
        {
            print("Entrer le mot de départ + ; + le mot d'arrivé : ", false);
            string ep = "";
            cin >> ep;

            int eps = ep.find(';');
            MotDeDepart = ep.substr(0, eps).c_str();
            MotAAtteindre = ep.substr((eps + 1), ep.size()).c_str();
        }
    }

    void VerifierEtCreerGraphe()
    {
        if (!QFile("dic.graph").exists())
        {
            print("Chargement du dictionnaire et suppression des accents !");
            Graphe graphe = Graphe(Graphe::LireDictionnaire(":/motsfr/words.txt"));

            print("Creation du graphe et des anagrammes !");
            graphe.GenererGraphe();

            //TODO (faire serialisation)
        }
        //TODO (else faire charger serialisation)
    }
}

int main(int argc, char *argv[])
{
    print("Bonjour !\n");
    try
    {
        General::ChargerMot(argc, argv);
        print("Mot de depart : " + MotDeDepart + " ; Mot d'arrive : " + MotAAtteindre + " !\n");

        auto start = std::chrono::high_resolution_clock::now();
        start = std::chrono::high_resolution_clock::now();

        General::VerifierEtCreerGraphe();

        print("Chargement du graphe ! TODO");
        //TODO (chargement du graphe sérialisé)

        print("Calcul... TODO");
        //TODO (dijkstra's algorithm)

        std::cout << "Temps : " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start).count() << " ms !" << std::endl;
    }
    catch (...)
    {
        print("ERREUR inconnue !");
        return -1;
    }
    print("\nAu revoir !");
    return 0;
}

J'ai aussi réalisé un profilage avec et sans la ligne du programme avec gprof. Pourriez-vous m'aider, s'il vous plait, à 'décoder' ces résultats ? Je poste les résultats.

Avec la ligne (pour 200 mots en 45s) : https://drive.google.com/file/d/0B5eGJmWOd6U2bkZMdWlSbEFYa2M/edit?usp=sharing

Sans la ligne (pour tous les mots 336531 en 22s) : https://drive.google.com/file/d/0B5eGJmWOd6U2WGRKdU5DdmZqTUE/edit?usp=sharing

+0 -0

En effet, le programme est alors 30 fois moins rapide avec l'allocation d'une QList et 5 fois pour un vector

C'est logique, étant donné que le temps pris par une allocation mémoire dépend peu (ou pas du tout, à ce niveau) de la taille allouée. Par contre, un vecteur n'a besoin que de faire une allocation de temps en temps, étant donné qu'il double la taille du tableau à chaque fois ; à l'opposé, une liste doit allouer une cellule mémoire pour chaque élément que tu lui rajoutes, ce qui induit un coût en performances.

Cette ligne est essentielle à ton algorithme. Sans elle, ton programme ne fait absolument rien, il est donc normal que ce soit plus rapide. Je vais donc regarder le profiling de ta version avec la ligne… Et je constate que ton code passe 97% de son temps dans GenererGraphe. J'ai une question au sujet de cette fonction : pourquoi le vector est-il déclaré à l'intérieur de la boucle, plutôt qu'à l'extérieur ? C'est voulu, afin de réinitialiser son contenu à chaque tour de boucle ? Dans tous les cas, tu te paies une allocation mémoire par tour de boucle, ce qui coûte cher. Je te conseille de sortir la déclaration du vector de la boucle, quitte à faire un bidule.clear() (ou le nom approprié pour vider un talbeau en C++) au début du corps de la boucle.

EDIT : en outre, je ne vois aucune bonne raison de rendre cette fonction inline.

+0 -0

Je te conseille de sortir la déclaration du vector de la boucle, quitte à faire un bidule.clear() (ou le nom approprié pour vider un talbeau en C++) au début du corps de la boucle.

GuilOooo

et un gros reserve() lors de la création du vector, pour éviter les réallocations

EDIT : en outre, je ne vois aucune bonne raison de rendre cette fonction inline.

GuilOooo

Je ne suis pas expert avec les __fastcal, mais j'ai l'impression que les 2 sont utilisé sans vraiment savoir l'impact. Je serais curieux de connaître les performances sans ces inline et __fastcall.

+1 -0

Merci pour vos réponses et idées ! :)

Je les ai testées : les performances se sont pas améliorées : 52s pour 200 mots.

Voici le profiler que j'ai relancé avec les nouvelles modifications du code (anagramme.clear/reserve + suppression des inline et __fastcall) : https://drive.google.com/file/d/0B5eGJmWOd6U2NEVvSHdHbndhVjA/edit?usp=sharing.

Voici aussi le nouveau code :

  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
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <QCoreApplication>
#include <QString>
#include <QFile>
#include <QResource>
#include <QRegExp>
#include <QIODevice>
#include <QList>
#include <QVariant>
#include <QDataStream>
#include <QSettings>
#include <QChar>

#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <thread>
#include <algorithm>
#include <array>

using namespace std;

typedef unsigned int uint;

enum TypeAnagramme { PlusLettre, MoinsLetttre, Modification };

namespace
{
    const int Alphabet[26] = { 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122 };
    const int TailleTableauLettre = 26;
    const int ValeurDefautLettre = 200;
    const int ValeurDefautLiens = 200;
    const int TailleMots = 336531;
    const int IndexTaille = 0;
    const int MaxTailleMot = 25;
    const int TailleAlphabet = 26;

    bool AfficherLesInfos = true;
    QString MotDeDepart = "";
    QString MotAAtteindre = "";
}

void print(QString text, bool newline = true)
{
    if (AfficherLesInfos)
    {
        cout << text.toLatin1().constData();
        if (newline)
            cout << endl;
    }
}

QString ArrayToQString(array<int, TailleTableauLettre> str)
{
    QString ret = "";

    for (int i = 1; i <= str[IndexTaille]; i++)
        ret.append((char)str[i]);

    return ret;
}

class InfoMot
{
public:
    array<int, TailleTableauLettre> Mot;
    array<int, TailleTableauLettre> Anagramme;
    vector<int> PossibilitesIndex = vector<int>();

    InfoMot()
    {
        this->Mot.fill(ValeurDefautLettre);
        this->Anagramme.fill(ValeurDefautLettre);

        this->PossibilitesIndex.reserve(ValeurDefautLiens);
    }
};

class Graphe
{
public:
    static QStringList LireDictionnaire(QString dicochemin)
    {
        QFile filedico(dicochemin);
        filedico.open(QIODevice::ReadOnly);

        QByteArray bytes = filedico.readAll();

        filedico.close();
        return ((QString)bytes.constData()).split('\n');
    }

    Graphe(QStringList mots)
    {
        this->Mots.reserve(TailleMots);

        for (int i = 0; i < mots.length(); i++)
        {
            InfoMot tempmot = InfoMot();

            mots[i] = mots[i].trimmed().replace("\r", "").replace(QRegExp("à|â|ä"), "a").replace(QRegExp("é|è|ê|ë"), "e").replace(QRegExp("ï|î"), "i").replace(QRegExp("ô|ö"), "o").replace(QRegExp("ù|û|ü"), "u").replace("ÿ", "y");
            tempmot.Mot = this->QStringToAInt(mots[i]);
            tempmot.Anagramme = this->SortQString(tempmot.Mot);

            this->Mots.insert(this->Mots.end(), tempmot);
        }
    }

    void GenererGraphe()
    {
        vector<array<int, TailleTableauLettre>> anagrammes = vector<array<int, TailleTableauLettre>>();
        anagrammes.reserve(702);

        for (uint i = 0; i < /*this->Mots.size()*/200; i++)
        {
            print("Numero du mot : " + QString::number((i + 1)) + " ; mot : " + ArrayToQString(this->Mots[i].Mot) + " !");

            anagrammes.insert(anagrammes.end(), this->Mots[i].Anagramme);

            this->FabriquerAnagrammes(i, anagrammes);

            this->ComparerAnagrammes(i, anagrammes);

            anagrammes.clear();
        }
    }
private:
    vector<InfoMot> Mots = vector<InfoMot>();

    void ComparerAnagrammes(uint i, vector<array<int, TailleTableauLettre>>& anagrammes)
    {
        for (uint j = 0; j < this->Mots.size(); j++)
            if (j != i)
                for (uint k = 0; k < anagrammes.size(); k++)
                    if ((anagrammes[k][IndexTaille] != 0) && (anagrammes[k][IndexTaille] <= MaxTailleMot))
                    {
                        if (this->Mots[j].Anagramme == anagrammes[k])
                            this->Mots[i].PossibilitesIndex.insert(this->Mots[i].PossibilitesIndex.end(), j);
                    }
                    else
                        break;
    }

    void FabriquerAnagrammes(int i, vector<array<int, TailleTableauLettre>>& anagrammes)
    {
        if (this->Mots[i].Anagramme[IndexTaille] < MaxTailleMot)
            for (int j = 0; j < TailleAlphabet; j++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::PlusLettre, this->Mots[i].Anagramme, j));

        if (this->Mots[i].Anagramme[IndexTaille] > 1)
            for (int j = 1; j <= this->Mots[i].Anagramme[IndexTaille]; j++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::MoinsLetttre, this->Mots[i].Anagramme, j));

        for (int j = 1; j <= this->Mots[i].Anagramme[IndexTaille]; j++)
            for (int k = 0; k < TailleAlphabet; k++)
                anagrammes.insert(anagrammes.end(), this->CreateAnagramme(TypeAnagramme::Modification, this->Mots[i].Anagramme, j, k));
    }

    array<int, TailleTableauLettre> SortQString(array<int, TailleTableauLettre>& motatrier)
    {
        array<int, MaxTailleMot> mottemptri;
        mottemptri.fill(ValeurDefautLettre);

        for (int i = 0; i < motatrier[IndexTaille]; i++)
            mottemptri[i] = motatrier[(i + 1)];

        std::sort(std::begin(mottemptri), std::end(mottemptri));

        array<int, TailleTableauLettre> mottrie;
        mottrie.fill(ValeurDefautLettre);

        mottrie[IndexTaille] = motatrier[IndexTaille];
        for (int i = 1; i <= motatrier[IndexTaille]; i++)
            mottrie[i] = mottemptri[(i - 1)];

        return mottrie;
    }

    array<int, TailleTableauLettre> QStringToAInt(QString& mot)
    {
        array<int, TailleTableauLettre> valinint;
        valinint.fill(ValeurDefautLettre);

        valinint[IndexTaille] = mot.length();
        for (int i = 0; i < mot.length(); i++)
            valinint[(i + 1)] = (int)(mot.at(i).toLatin1());

        return valinint;
    }

    array<int, TailleTableauLettre> CreateAnagramme(TypeAnagramme type, array<int, TailleTableauLettre>& mot, uint j, uint k = 0)
    {
        array<int, TailleTableauLettre> motmodifie = mot;

        switch (type)
        {
        case TypeAnagramme::PlusLettre:
            motmodifie[motmodifie[0]] = Alphabet[j];
            break;

        case TypeAnagramme::MoinsLetttre:
            motmodifie[j] = ValeurDefautLettre;
            break;

        case TypeAnagramme::Modification:
            motmodifie[j] = Alphabet[k];
            break;
        }

        motmodifie = this->SortQString(motmodifie);

        return motmodifie;
    }
};

namespace General
{
    void ChargerMot(int argc, char *argv[])
    {
        if (argc >= 3)
        {
            MotDeDepart = argv[1];
            MotAAtteindre = argv[2];

            if (argc == 4)
                if (((string)argv[3]) == "nocout")
                    AfficherLesInfos = false;
        }
        else
        {
            print("Entrer le mot de départ + ; + le mot d'arrivé : ", false);
            string ep = "";
            cin >> ep;

            int eps = ep.find(';');
            MotDeDepart = ep.substr(0, eps).c_str();
            MotAAtteindre = ep.substr((eps + 1), ep.size()).c_str();
        }
    }

    void VerifierEtCreerGraphe()
    {
        if (!QFile("dic.graph").exists())
        {
            print("Chargement du dictionnaire et suppression des accents !");
            Graphe graphe = Graphe(Graphe::LireDictionnaire(":/motsfr/words.txt"));

            print("Creation du graphe et des anagrammes !");
            graphe.GenererGraphe();

            //TODO (faire serialisation)
        }
        //TODO (else faire charger serialisation)
    }
}

int main(int argc, char *argv[])
{
    print("Bonjour !\n");
    try
    {
        General::ChargerMot(argc, argv);
        print("Mot de depart : " + MotDeDepart + " ; Mot d'arrive : " + MotAAtteindre + " !\n");

        auto start = std::chrono::high_resolution_clock::now();
        start = std::chrono::high_resolution_clock::now();

        General::VerifierEtCreerGraphe();

        print("Chargement du graphe ! TODO");
        //TODO (chargement du graphe sérialisé)

        print("Calcul... TODO");
        //TODO (dijkstra's algorithm)

        std::cout << "Temps : " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start).count() << " ms !" << std::endl;
    }
    catch (...)
    {
        print("ERREUR inconnue !");
        return -1;
    }
    print("\nAu revoir !");
    return 0;
}

Je vous remercie encore pour le temps que vous passez à chercher et à rédiger les réponses. Je continue de chercher de mon côté aussi. :)

+0 -0

Tu passes toujours 96% du temps dans la fonction GenererGraphe, mon hypothèse sur l'allocation coûteuse était donc fausse.

Au passage, il est probable que le fait d'hardcoder 200 dans la condition de la boucle ne fasse pas gagner grand-chose. GCC et LLVM savent très bien optimiser ce genre de trucs (ça s'appelle du loop-invariant motion, si tu veux te renseigner).

Par contre, en regardant un peu le code des fonctions apppelées par GenererGraphe, je m'aperçois que tu as de très nombreuses boucles imbriquées (si on regarde à travers les appels de fonction). Il est possible que tu doives simplement revoir ton algorithme. Je n'ai pas le courage de me plonger dans les détails de ton code pour comprendre ce que tu cherches à faire, mais je ne vois rien qui induise des pertes de performances dans ton source. De ce fait, les pseudo-optimisations comme inline ou hardcoder des constantes ne te feront rien gagner.

Je pense donc que c'est simplement la tâche que tu essaies d'exécuter qui est intrinsèquement longue et qu'il faudrait réfléchir à une nouvelle manière de procéder.

+0 -0

J'ai commencé à regarder plus en détail ton code…

  • tu es un dev C à la base ? La conception objet est inutile/mauvaise, création d'un fonction print…
  • le try dans le main sert pas à grand chose
  • tu réinitialises inutilement start dans le main
  • constantes inutiles. TailleMots pour la taille du dictionnaire hardcodé, Alphabet[26], TailleTableauLettre, IndexTaille (=0 ?), TailleAlphabet
  • AfficherLesInfos pour ne pas afficher les print ? Ca serait pas mieux un #define (je sais que l'on recommande de ne pas utiliser les macros en C++, mais là, c'est peut être exagéré)
  • realAll dans LireDictionnaire, c'est bien pour éviter de lire ligne par ligne un fichier (optimisation du buffer). Par contre, faire un split('\n') derrière, qui va créer un QString pour chaque ligne, c'est pas top. Chez moi, la fonction LireDictionnaire prend 2ms sans le split et 143 ms avec le split.
  • encore pire, dans le constructeur de Graphe, tu utilises plusieurs regex pour retirer les accents. Je passe de 1s à 7s avec cette conversion. Aie

Pour ce genre de chose, évite de parcourir plusieurs fois tes données et évite les allocations dans les boucles.

  • vector<int> PossibilitesIndex = vector<int>(); ===> vector<int> PossibilitesIndex;
  • pourquoi des tableaux de taille fixe dans InfoMot ? Perte de mémoire, non optimisation des caches
  • Idem pour le tableau PossibilitesIndex avec un reserve(200). Cela veut dire que pour chaque mot, tu réserves ce tableau ? (donc 3365312004 = 256Mo réservé dès le début + le fait que tu fais 336531 allocations dans ta boucle)
  • utilité de la conversion faite par QStringToAInt ?
  • this->Mots.insert(this->Mots.end(), tempmot); ====> this->Mots.push_back(tempmot);

Cela fait déjà beaucoup d'allocations pour chaque mot du dictionnaire. Du coup, les reserve() ne sont plus critique, tu perds déjà beaucoup de temps, pas étonnant que le fait d'avoir ajouté des reserve() n'améliore pas beaucoup les performances

  • vector<array<int, TailleTableauLettre>> anagrammes = vector<array<int, TailleTableauLettre>>(); ====> vector<array<int, TailleTableauLettre>> anagrammes; Pourquoi cette manie d'appeler explicitement le constructeur de vector ?
  • anagrammes.insert(anagrammes.end(), this->Mots[i].Anagramme); ====> anagrammes.push_back(this->Mots[i].Anagramme);
  • la grosse clac niveau performance, c'est ComparerAnagrammes. Tu es en O(n²) sur le nombre de mots dans le dictionnaire, donc 336531². Aie aie.

Je m'arrête là, pas besoin d'aller plus loin. Les bidouilles comme fastcall, inline, reserve, etc. sont de la micro-optimisation par rapport à ton problème d'algorithmique. Si tu veux des performances correctes, faut déjà corriger ça.

Je ne sais pas à quoi sert ton Graphe et ce que tu veux en faire, mais il faut simplifier la fonction de comparaison. Par exemple, utiliser un conteneur associatif (map, hash, etc), pour ne comparer que petite partie des mots

Problématiques de la conception objet : pourquoi Graphe a la responsabilité de lire le dictionnaire ? Pourquoi Graphe a la responsabilité de nettoyer les accents ?

+2 -0

Merci pour toutes ces corrections :) ! Je vais corriger le code !

  • Je ne suis pas un développeur C à la base (j'ai commencé l'informatique en apprenant le Java).
  • C'est vrai, le try ne sert pas à grand chose, mais il ne gêne pas pour autant.
  • Pour start, je n'avais pas vu cette erreur d’étourderie.
  • Pour les constantes, je ne les avais pas mises au début. Je les ai ensuite crées pour la lisibilité du code. Je peux les enlever, mais je ne pense pas que cela soit responsable de la lenteur du code. Je ne vois pas trop comment utiliser un define pour AfficherLesInfos…
  • Pour la lecture du fichier, je vais corriger tout cela : split, regex. Et donc améliorer les performances sur ce point-là.
  • Merci pour ces conseils ! Je peux ainsi m'améliorer ! :)
  • Dans InfoMot, je vais voir pour utiliser des tableaux de taille dynamique. Pour PossibilitesIndex, tu as tout à fait raison. Je vais corriger cela aussi.
  • La conversion est indispensable pour passer de QString à Int.
  • Encore merci pour push_back.
  • J'ai tendance à l’appeler explicitement, c'est juste une habitude…
  • Effectivement, la complexité de l'algorithme de comparaison est quadratique, et ce n'est pas bon pour les performances…

Je vais donc corriger tout cela, je reposterai le code quand cela sera fait :). Je vais aussi réfléchir pour simplifier la fonction de comparaison.

C'est vrai, j'ai mal pensé Graphe pour la lecture du dico et le nettoyage des accents. Je vais peut-être faire une classe pour seulement cette tâche.

+0 -0

Voilà ! :) J'ai donc selon les conseils de gbdivers modifié le code. Le voici (j'espère que la conception objet commence à être mieux utilisée) :

  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
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <QCoreApplication>
#include <QString>
#include <QStringBuilder>
#include <QFile>
#include <QResource>
#include <QRegExp>
#include <QIODevice>
#include <QList>
#include <QVariant>
#include <QDataStream>
#include <QSettings>
#include <QChar>

#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <thread>
#include <algorithm>
#include <array>

using namespace std;

typedef unsigned int uint;

enum TypeAnagramme { PlusLettre, MoinsLetttre, Modification };

namespace
{
const int Alphabet[26] = { 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122 };
const int TailleMots = 336531;
const int MaxTailleMot = 25;
const int TailleAlphabet = 26;
const int TailleReserveAna = 351;

const QChar Ar = 'a';
const QString Aa = "âàä";
const QChar Er = 'e';
const QString Ea = "éèêë";
const QChar Ir = 'i';
const QString Ia = "îï";
const QChar Or = 'o';
const QString Oa = "ôö";
const QChar Ur = 'u';
const QString Ua = "ùûü";
const QChar Yr = 'y';
const QString Ya = "ÿ";

const QChar RetourLigne = '\n';

const string OptionSansTexte = "nocout";

bool AfficherLesInfos = true;
QString MotDeDepart = "";
QString MotAAtteindre = "";
}

void print(QString text, bool newline = true)
{
    if (AfficherLesInfos)
    {
        cout << text.toLatin1().constData();
        if (newline)
            cout << endl;
    }
}

QString ArrayToQString(vector<int>& str)
{
    QString ret = "";
    ret.reserve(str.size());

    for (uint i = 0; i < str.size(); i++)
        ret.append((char)str[i]);

    return ret;
}

class InfoMot
{
public:
    vector<int> Mot;
    vector<int> Anagramme;
    vector<int> PossibilitesIndex;
};

class Dictionnaire
{
public:
    static QString LireDictionnaire(QString dicochemin)
    {
        QFile filedico(dicochemin);
        filedico.open(QIODevice::ReadOnly);

        QByteArray bytes = filedico.readAll();

        filedico.close();
        return ((QString)bytes.constData());
    }

    static vector<InfoMot> TraiterMots(QString& mots)
    {
        vector<InfoMot> Mots;
        Mots.reserve(TailleMots);

        QString tempmotqs;
        tempmotqs.reserve(MaxTailleMot);

        int itempmot = 0;
        QChar lettert;

        for (int i = 0; i < TailleMots; i++)
        {
            do
            {
                if (itempmot < mots.length())
                {
                    lettert = mots.at(itempmot);
                    itempmot++;

                    DeleteAccents(Aa, Ar, lettert);
                    DeleteAccents(Ea, Er, lettert);
                    DeleteAccents(Ia, Ir, lettert);
                    DeleteAccents(Oa, Or, lettert);
                    DeleteAccents(Ua, Ur, lettert);
                    DeleteAccents(Ya, Yr, lettert);

                    tempmotqs.append(lettert);
                }
                else
                    break;
            }
            while ((itempmot < mots.length()) && (mots.at(itempmot) != RetourLigne));
            itempmot++;

            InfoMot tempmot = InfoMot();
            tempmot.Mot = QStringToAInt(tempmotqs);

            tempmot.Anagramme = tempmot.Mot;
            sort(tempmot.Anagramme.begin(), tempmot.Anagramme.end());

            Mots.push_back(tempmot);

            tempmotqs.clear();
        }
        return Mots;
    }
private:
    static void DeleteAccents(const QString& acc, const QChar& remp, QChar& letter)
    {
        for (int i = 0; i < acc.size(); i++)
            if (acc.at(i) == letter)
                letter = remp;
    }

    static vector<int> QStringToAInt(QString& mot)
    {
        vector<int> valinint;
        valinint.reserve(mot.length());

        for (int i = 0; i < mot.length(); i++)
            valinint.push_back((int)(mot.at(i).toLatin1()));

        return valinint;
    }
};

class Graphe
{
public:
    Graphe(vector<InfoMot>& motstraites)
    {
        this->Mots = motstraites;
    }

    void GenererGraphe()
    {
        vector<vector<int>> anagrammes;
        anagrammes.reserve(TailleReserveAna);

        for (uint i = 0; i < /*this->Mots.size()*/200; i++)
        {
            print("Numero du mot : " + QString::number((i + 1)) + " ; mot : " + ArrayToQString(this->Mots[i].Mot) + " !");

            anagrammes.push_back(this->Mots[i].Anagramme);

            this->FabriquerAnagrammes(i, anagrammes);

            this->ComparerAnagrammes(i, anagrammes);

            anagrammes.clear();
        }
    }
private:
    vector<InfoMot> Mots;

    void ComparerAnagrammes(uint i, vector<vector<int>>& anagrammes)
    {
        for (uint j = 0; j < this->Mots.size(); j++)
            if (j != i)
                for (uint k = 0; k < anagrammes.size(); k++)
                    if (this->Mots[j].Anagramme == anagrammes[k])
                        this->Mots[i].PossibilitesIndex.push_back(j);
    }

    void FabriquerAnagrammes(int i, vector<vector<int>>& anagrammes)
    {
        if (this->Mots[i].Anagramme.size() < MaxTailleMot)
            for (int j = 0; j < TailleAlphabet; j++)
                anagrammes.push_back(this->CreateAnagramme(TypeAnagramme::PlusLettre, this->Mots[i].Anagramme, j));

        if (this->Mots[i].Anagramme.size() > 1)
            for (uint j = 0; j < this->Mots[i].Anagramme.size(); j++)
                anagrammes.push_back(this->CreateAnagramme(TypeAnagramme::MoinsLetttre, this->Mots[i].Anagramme, j));

        for (uint j = 0; j < this->Mots[i].Anagramme.size(); j++)
            for (int k = 0; k < TailleAlphabet; k++)
                anagrammes.push_back(this->CreateAnagramme(TypeAnagramme::Modification, this->Mots[i].Anagramme, j, k));
    }

    vector<int> CreateAnagramme(TypeAnagramme type, vector<int>& mot, uint j, uint k = 0)
    {
        vector<int> motmodifie = mot;

        switch (type)
        {
        case TypeAnagramme::PlusLettre:
            motmodifie.push_back(Alphabet[j]);
            break;

        case TypeAnagramme::MoinsLetttre:
            motmodifie.erase(motmodifie.begin() + j);
            break;

        case TypeAnagramme::Modification:
            motmodifie[j] = Alphabet[k];
            break;
        }

        sort(motmodifie.begin(), motmodifie.end());

        return motmodifie;
    }
};

namespace General
{
void ChargerMot(int argc, char *argv[])
{
    if (argc >= 3)
    {
        MotDeDepart = argv[1];
        MotAAtteindre = argv[2];

        if (argc == 4)
            if (((string)argv[3]) == OptionSansTexte)
                AfficherLesInfos = false;
    }
    else
    {
        print("Entrer le mot de départ + ; + le mot d'arrivé : ", false);
        string ep = "";
        cin >> ep;

        int eps = ep.find(';');
        MotDeDepart = ep.substr(0, eps).c_str();
        MotAAtteindre = ep.substr((eps + 1), ep.size()).c_str();
    }
}

void VerifierEtCreerGraphe()
{
    if (!QFile("dic.graph").exists())
    {
        print("Chargement du dictionnaire et suppression des accents !");

        QString mots = Dictionnaire::LireDictionnaire(":/motsfr/words.txt");
        vector<InfoMot> motstraites = Dictionnaire::TraiterMots(mots);

        Graphe graphe = Graphe(motstraites);

        print("Creation du graphe et des anagrammes !");
        graphe.GenererGraphe();

        //TODO (faire serialisation)
    }
}
}

int main(int argc, char *argv[])
{
    print("Bonjour !\n");
    try
    {
        General::ChargerMot(argc, argv);
        print("Mot de depart : " + MotDeDepart + " ; Mot d'arrive : " + MotAAtteindre + " !\n");

        auto start = std::chrono::high_resolution_clock::now();

        General::VerifierEtCreerGraphe();

        print("Chargement du graphe ! TODO");
        //TODO (chargement du graphe sérialisé)

        print("Calcul... TODO");
        //TODO (dijkstra's algorithm)

        std::cout << "Temps : " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start).count() << " ms !" << std::endl;
    }
    catch (...)
    {
        print("ERREUR inconnue !");
        return -1;
    }
    print("\nAu revoir !");
    return 0;
}

Voici aussi un nouveau profiler avec la nouvelle version (pour 200 mots) : https://drive.google.com/file/d/0B5eGJmWOd6U2bzFXNVJJMFNCSkk/edit?usp=sharing

Les performances ont été légèrement améliorées (37s pour 200 mots au lieu de 50s). Cependant, il va de soit qu'il va falloir modifier la fonction ComparerAnagrammes. Tu avais parler des conteneurs associatifs. Peux-tu préciser et expliquer, s'il te plaît ?

Merci encore pour toutes vos réponses. :)

+0 -0

Tu avais parler des conteneurs associatifs. Peux-tu préciser et expliquer, s'il te plaît ?

florian6973

C'était une idée comme ça. Je n'ai pas trop réfléchi comment améliorer ton algo. Mais si je comprend bien, tu parcours tous les mots pour trouver ceux qui ont une "correspondance" avec un mot donné. Or, la plus part des mots ne correspondent pas. Si j'ai bien compris le problème, un mot peut correspondre s'il a moins d'une lettre de différence. Déjà avec ça, tu fais une map<int, mot> pour trier selon le nombre de lettre et tu simplifies pas mal ta boucle. Ou encore mieux, faire un set<string> avec string correspondant à un mot avec ses lettres triées. Ensuite, tu recherches les mots avec 1 lettre en plus (26 itérations), 1 lettre en moins (1 itération par lettre du mot) et 1 lettre changé (26 * nombre lettre du mot itérations)

Bref, il y a surement des choses à faire pour améliorer le temps d'analyse

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte