Algorithme optimiser C++

Version imprimable

19/12/2013, 13h14
CliffeCSTL

Algorithme optimiser C++
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.

http://img4.hostingpics.net/pics/248082Sanstitre.png

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:

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.
19/12/2013, 15h50
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 :mouarf:

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

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
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à :)

19/12/2013, 16h30
CliffeCSTL

Tu remplace mon insert par un push_front. C'est la même chose au final ;)
19/12/2013, 17h38
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 :/
26/12/2013, 17h24
white_tentacle

Citation:

Envoyé par 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 :/

Perso j’aurais plusieurs remarques :

- vu l’usage, pas sûr que QList soit pertinent. Un vector qui a moins d’overhead devrait être un peu plus performant (tant qu’on vire ces insertions en-tête, cf plus loin)

- pour la suppression des éléments de P2, il est probablement plus pertinent de créer un nouveau conteneur, d’y copier tous les éléments de P2 qui ne sont pas dans C1, puis ensuite de réaffecter P2 (avec la sémantique de mouvement, ça ne coûte pas cher). remove est en général une opération coûteuse (nécessité de déplacer en mémoire tout ce qui est après).

- penser à utiliser reserve (ou le constructeur prenant la capacité en paramètre) pour préallouer les conteneurs. Ça limitera le nombre d’allocations mémoire.

- plutôt que d’utiliser des insertions en tête, insérer directement les valeurs au bon index à l’étape précédente (il me semble que c’est possible, je ne suis pas rentré dans le détail pour vérifier). Bien entendu, dans ce cas, il faut avoir utilisé resize plutôt que reserve afin que la taille du vecteur soit bonne.

Faudrait savoir la taille de P1 et P2 (au moins un ordre de grandeur).

Aussi, à-t-on la garantie que C1.size() == P1.size() ?

Si oui, le code peut être de la forme
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 std::vector<int> lox(const std::vector<int>& p1, const std::vector<int>& p2) { const int p1_size = (int)p1.size(); std::vector<int> c1(p1_size); int min = 3; //rand() % p1_size; int max = 7; //(rand() % (p1_size - min)) + min; auto itMin = p1.begin() + min; auto itMax = p1.begin() + max; std::copy(itMin, itMax, c1.begin()+min); //std::unordered_set<int> blackList(itMin, itMax); int ind = 0; for(int v: p2) { // recherche directement dans p1 (si max-min petit) if(std::find(itMin, itMax, v) == itMax) { // utilisation d'un unordered_set (si max-min grand) //if(blackList.find(v) == blackList.end()) { c1[ind] = v; ++ind; if(ind >= min && ind <= max) { ind = max; } } } return c1; }
(Oui je suis pas à l'aise avec les types Qt, relou de devoir fouiller dans la doc à chaque fois à cause des fonctions qui ont des noms différents, et j'ai pas Qt sous la main non plus pour tester)