Discussion :

[CliffeCSTL]

Bonjour,

Je code un algo mémétique et j'ai besoin d'une fonction de croisement. J'utilise le LOX crossover et j'aimerais de l'aide pour optimiser cette fonction.

LOX : Deux points de croisement sont choisis au hasard dans le premier parent P1. Les clients entre ces deux points sont recopiés dans C1 à la même position et sont supprimés de P2. C1 est ensuite complété par les clients restants de P2 dans le même ordre de gauche à droite.

Code :

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

1
2
3
4
5
6
7
QList<int> LOX(const QList<int> & P1, const QList<int> P2) {
    QList<int> C1;
 
    [...]
 
    return C1;
}

J'ai déjà coder une fonction mais elle est trop lente et fait des parcourts inutiles.

Merci.

[skeud]

Beh si tu ne nous montres pas comment tu as fait, on risque pas de pouvoir te dire là où tu perds du temps ou ce qu'il ne va pas dans ton code

[CliffeCSTL]

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
35
36
37
38
QList<int> LOX(const QList<int> & P1, const QList<int> & P2) {
    unsigned int i, value, n1 = P1.size(), n2 = P2.size();
    qsrand(QTime::currentTime().msec());
 
    // Points de croisements
    unsigned int min = randInt(  0, n1 - 1);
    unsigned int max = randInt(min, n1 - 1);
 
    // On recopie les élements de P1 situer entre les points de croisements
    QList<int> C1;
    for (i = min; i < max; ++i)
        C1.push_back(P1[i]);
 
    // On recopie tous les éléments de P2 dans C2
    QList<int> C2;
    for (i = 0; i < n2; ++i)
        C2.push_back(P2[i]);
    // On supprime dans C2 les éléments de P1 qui sont situer entre les points de croisements
    foreach (value, C1) {
        i = 0; bool stop = false;
	while (i < C2.size() && stop != true) {
	    if (value == C2[i]) {
	        C2.removeAt(i); stop = true;
            }
	    ++i;
        }
    }
 
    // On insère les derniers éléments dans C1
    i = 0;
    foreach (value, C2) {
        if (i < min) C1.insert(i, value);
	else C1.push_back(value);
	++i;
    }
 
    return C1;
}

[skeud]

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
35
36
37
38
39
QList<int> LOX(const QList<int> & P1, const QList<int> & P2) {
    unsigned int i, value;
    qsrand(QTime::currentTime().msec());
 
    // Points de croisement
    unsigned int min = randInt(  0, n1 - 1);
    unsigned int max = randInt(min, n1 - 1);
 
    QList<int> C1;
    // On récupère dans C1 toute les valeur de P1 entre les points de croisements
    for (i = min; i < max; ++i)
        C1.push_back(P1[i]);
 
    // On retire de P2 toute les valeur de C1
    foreach (value, C1) {
       P2.removeAll(value);
    }
 
    if (min < P2.size())
      i = min-1;
    else
      i = P2.size()-1;
    unsigned int save = i;
    // On récupère les valeur de P2 entre 0 et min mais en ordre inverse pour utiliser le push_front
    while (i >= 0) {
       C1.push_front(P2[i]);
       i--;
    }
 
    // On complete par la droite C1 avec les valeur de P2 restante.
    i = save+1;
    while (i < P2.size)
    {
       C1.push_back(P2[i]);
       i++;
    }
 
    return C1;
}

Essaie avec ce code, je promet pas que ça fonctionne du premier coup, mais l'idée est là

[CliffeCSTL]

Tu remplace mon insert par un push_front. C'est la même chose au final

[skeud]

Nop les boucles seront moins longue car on ne parcoure qu'une seule liste a la fois, sinon je suis en train de reflechir a une meilleur boucle, mais pas sur que tu puisses mieux optimiser que sa et que sa reste lisible :/