Discussion :

[bourinator]

Bonjour à tous,

Je vous explique mon problème...
J'ai créé un petit programme dont je vous expose rapidement l'algorithme, ce sera plus parlant qu'un long discours :

liste des solutions traitées <- Vide
Pour i de 1 à beaucoup
sol <- déterminer solution aléatoire
Si sol n'a pas déjà été traitée Alors
traiter sol
ajouter sol à la liste des solutions traitées
Finsi
Finpour

Ainsi, la liste des solutions traitées vide au début grandit rapidement jusqu'à devenir énorme, ce qui fait perdre beaucoup de temps lors de la recherche de sol dans la liste des solutions traitées.
Concrètement, en Matlab, j'avais modélisé cette liste en cell, à la fin de laquelle je concaténais chaque nouvelle solution. C'est pour rechercher si une solution avait déjà été traitée que je devais parcourir tout le cell jusqu'à cette éventuelle solution, ou jusqu'à la fin.
Ainsi, les premières occurrences de la boucle principale se faisaient très rapidement, mais ralentissait au fur et à mesure de l'exécution.

Du coup, j'ai eu l'idée de gérer cette liste en conservant un tri de ces solutions. On insère la nouvelle solution à la bonne place, et on recherche plus facilement une solution particulière dans une liste triée. Seulement, je n'ai pas trouvé les fonctions souhaitées de gestion de cell (insert, find). Je suis donc passé en matrice (une ligne étant une solution), ce qui me permet d'insérer facilement au rang n. Mais pour déterminer le rang n, je n'ai pas trouvé de fonction Matlab, j'ai donc du coder par dichotomie. Au final, cela fonctionne, mais est beaucoup plus lent que l'algo de recherche séquentielle.

Quelqu'un a-t-il une idée de la raison de ce ralentissement ? Est-ce algorithmique ou purement technique ?
A noter que la liste des solutions déjà traitées est gérée en variable globale, cela pourrait-il être la cause ?
Si mon explication manque d'information ou de clarté, n'hésitez pas à me demander.
Merci d'avance pour votre aide...

[bourinator]

Rebonjour,

J'ai inséré un petit compteur pour mes 2 nouvelles fonctions...
2.81s pour la recherche dans la liste,
145.56s pour l'insertion dans la liste (recherche de la bonne ligne + insertion).

J'en déduis donc que c'est l'insertion qui fait perdre tout ce temps.
Voici le code utilisé pour insérer la solution :

Code :

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

1
2
3
 
Num_ligne = recherche_num_ligne(Grille, Ligne);
New_grille = [Grille(1:Num_ligne-1,:) ; Ligne; Grille(Num_ligne :end, :)];

La grille pouvant être volumineuse, cette méthode n'est peut-être pas la plus optimisée...

[Invité]

Bonsoir,

Je pense que ton souci principal vient d'ici
Au fur et à mesure que tu avances dans ta boucle, ta variable Grille grandi et a besoin de blocs de plus en plus grands.
Une petite question: que fait la fonction recherche_num_ligne?

[bourinator]

Merci pour ta réponse rapide !
Effectivement, une préallocation de ma grille a l'air indispensable.
Le souci étant que je n'ai pas connaissance de la taille finale de ma grille, mais je préfère maximiser sa taille pour éviter cette perte de temps.

recherche_num_ligne donne le numéro de la ligne où insérer la nouvelle, par dichotomie :

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
function Num_ligne = recherche_num_ligne(Grille, Ligne)
    Nb_lignes = numel(Grille)/100;    %une solution est composée de 100 éléments
    if Nb_lignes == 0
        Num_ligne = 1;
    else
        Num_ligne = dicho(Grille, Ligne, 1, Nb_lignes);
    end
end
 
function res = dicho(Grille, Ligne, lemin, lemax)
    if lemax == lemin
        if Ligne < Grille(lemin, :)
            res = lemin;
        else
            res = lemin +1;
        end
    else
        Milieu = floor((lemin+lemax)/2);
        if Ligne < Grille(Milieu, :)
            res = dicho (Grille, Ligne, lemin, Milieu);
        else
            res = dicho(Grille, Ligne, Milieu+1, lemax);
        end
    end
end

[Invité]

Code :

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

if Ligne < Grille(Milieu, :)

Ici tu fais une comparaison de vecteurs, et tu as au final un vecteur de valeurs logique, or if requiert une seule valeur.
Quel est ton critère exact?
Connais-tu la fonction sort?

Remarque:

Code :

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

Nb_lignes = numel(Grille)/100;

Peut être remplacé par

Code :

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

Nb_lignes = size(Grille,1);

[bourinator]

Hmmm, finalement, la préallocation n'aide pas dans ce cas de figure, le temps d'exécution est même plus long...
Dans l'exemple de la FAQ, on affecte directement au rang n, donc la préallocation fait effectivement gagner du temps, mais là, il y a insertion de ligne, c'est-à-dire (et c'est sûrement ça le problème) que si l'on insère à la ième ligne, on conserve les (i-1) premières lignes, on ajoute la ligne à insérer, puis on décale la fin de la matrice.
Pour éviter la réallocation, avec une grille de 60000 lignes, j'ai codé :

Code :

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

    New_grille = [Grille(1:Num_ligne-1,:) ; Ligne; Grille(Num_ligne :60000-1, :)];

Ainsi, la grille fera toujours 60000 lignes.
Mais si on insère par exemple en 1ère ligne, il faut recopier toute la matrice un rang plus bas, ce qui prend en moyenne 0.16s.

J'aurais bien envie de changer de méthode de stockage de mes solutions, une plus adaptée aux insertions triées, comme un système de listes chaînées...

[Invité]

Non ce n'est pas exactement ce à quoi je pensais.
Je te demande ton critère exact car je penserai plutôt à remplir la grille dans la boucle comme ceci:
Grille = zeros(nb_lignes,100);

Code :

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

1
2
3
4
for i = 1:nb_lignes
    % obtention de Ligne
    Grille(i,:) = Ligne;
end

Et ensuite faire le tri de Grille par la suite de façon plus optimisée, mais cela dépend bien sur du critère, mais aussi si tu utilises Grille pour déterminer Ligne,...
Donc si tu pouvais montrer ta boucle, je pourrais t'en dire plus.