optimisation de boucle

Version imprimable

Bonjour à tous,

Je commence juste le C#, et j'aurai voulu savoir si il y avait des fonctions pour optimiser les boucles for.

Pour exemple j'ai 2 listes, l'une contient une liste de chiffre par exemple :

Code:

5, 8, 13, 35, 40

Et l'autre en contient d'autre :

Code:

2, 3, 15, 35, 60

Et j'aimerai savoir si la somme de 2 chiffres de la liste 2 est égal à un des chiffres de la liste 1. Donc un truc du genre :
Code:

1 2 3 4 5 6 7 8 for (int o = 0; o < Liste1.Count; o++){ for (int p = 0; p < Liste2.Count; p++) { int nb_soustrait1 = int.Parse(Liste2[p]) - int.Parse(Liste1[o]); if (Liste2.Contains(nb_soustrait1.ToString())){ MessageBox.Show("Trouvé : " + nb_soustrait1 +" "+Liste2[p]); } }
Si les listes sont trop importante, ça met beaucoup de temps...

Merci à vous

20/05/2015, 10h33
jopopmk

Salut,

tes listes ne contiennent que des entiers positifs ?
Si oui tu peux vérifier le signe de ta différence avant de lancer le Contains, ce sera toujours ça de gagner.

Petite remarque : s'il s'agit de liste de int alors le ToString n'a pas de sens,
s'il s'agit de liste de string alors il faut parser en int avant de faire ta différence.
20/05/2015, 11h41
Guignon

Merci jopo, j'ai fais ce que tu m'a dis, c'est déjà ça de gagné même si le temps reste encore très long... Je vais voir si il n'y a pas une méthode plus rapide

Bonjour.

Ce n'est pas un problème de langage mais d'algorithme. La bonne solution à ce prooblème est de d'abord trier les deux listes, puis de les comparer élément après élément avec un code suivant ce squelette :
Code:

1 2 3 4 5 6 7 8 9 10 11 while (i < list1.Count && j < list2.Count) { var x = list1[i]; var y = list2[j]; if (x < y) ... else if (x > y) ... else ... } while (i < list1.Count) ... while (j < list2.Count) ...
Edit : en fait j'aurais dû lire plus attentivement. Ici on peut simplement transformer la liste 1 en un HashSet (on parcourt les éléments et on les ajoute à un ensemble). Puis on utilisera ce HashSet à la place de la boucle intérieure.

Citation:

Et j'aimerai savoir si la somme de 2 chiffres de la liste 2 est égal à un des chiffres de la liste 1

En prenant en compte que tes listes sont triées (comme dans ton exemple)

Il te faut faire deux boucle for afin que tous tes chiffres de ta Liste 2 s'additionnes mutuellement

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
 
 
//Première boucle afin de parcourrir tous les nombres de la deuxième liste
for(int i = 0 ; i < Liste2.Count ; i++)
{
  //Deuxième boucle afin de parcourir tous les nombres de la deuxième liste
  //(en partant de i+1 car tous les nombre avant i ont déjà été additionné dans une itération précédente et afin de ne pas compter deux fois le même nombre)
  for(int j = i + 1 ; j < Liste2.Count ; j++)
  {
    //Afin de remplacer "Liste1.Contains" qui va a chaque fois regarder dans tous le tableau.
    //Il faut créer un index qui servira à indiquer l'index de l'itération précédente
    int Index = 0;
 
    //Il faut ensuite parcourir la liste 1 afin de voir si la somme de deux chiffre de la liste 2 est égale à un de ses chiffres:
    for(int k = Index ; k < Liste1.Count ; k++)
    {
      //Pour savoir si la somme de deux chiffres de la liste deux est égale à un chiffre de la liste un, il faut tout simplement faire :
      if(Liste2[i] + Liste2[j] == Liste1[k])
      {
        MessageBox.Show("Trouvé : " + Liste2[i].ToString() + " + " + Liste2[j].ToString() " = "  Liste1[k].ToString());
      }
 
      //Sinon si la somme est inférieur
      if(Liste2[i] + Liste2[j] < Liste1[k])
      {
        //On peut arrêter de regarder la liste 1 vu que les chiffres sont de plus en plus grand
        Index = k-1;
 
        //On vérifie que l'Index n'est pas négatif
        if(Index<0)
          Index =0;
 
        break;
 
      }
    }
  }
}

Cette solution est certes plus longue, mais te fera gagner du temps comparé à Contains avec des très grandes listes

20/05/2015, 13h46
DonQuiche

Citation:

Envoyé par MSL_INTERIM

Cette solution est certes plus longue, mais te fera gagner du temps comparé à Contains avec des très grandes listes

Pas vraiment, tout ce que tu as fait c'est simplement diviser par deux le nombre de recherches en présumant que list2 a été préalablement triée. Ca reste O(n² * m)

Avec un HashSet<> comme je l'ai proposé on a du O(n²) puisque HashSet<>.Contains a une complexité de O(1).

Et si les nombres sont compacts on peut même le remplacer par un simple tableau de booléens.
20/05/2015, 14h14
Guignon
Merci pour vos réponses.

Alors oui pourquoi pas revoir l'algorithme, et de disposer les nombres proprement pour après mieux les exploiter. Mais je n'ai pas trop compris le font de ta pensée, il faudrait faire :
1. Trier les listes du plus petit au plus grand
2. Comparaison des chiffres
3. Si le chiffre est trop grand on ne le stock pas
4. Si le chiffre est plus petit on le garde dans une nouvelle liste
Donc de continuer comme ça jusqu'à ne trouver que les bons chiffres ? (J'essai de chercher une solution ^^)

Sinon je vais tester aussi la solution de MSL_INTERIM, par contre les listes ne sont pas trié donc il faut les trier avant toutes ces boucles.

Merci bien en tout cas.
20/05/2015, 14h23
DonQuiche
Citation:
Envoyé par Guignon

Merci pour vos réponses.

Alors oui pourquoi pas revoir l'algorithme, et de disposer les nombres proprement pour après mieux les exploiter. Mais je n'ai pas trop compris le font de ta pensée, il faudrait faire :

Trier les listes du plus petit au plus grand
Comparaison des chiffres
Si le chiffre est trop grand on ne le stock pas
Si le chiffre est plus petit on le garde dans une nouvelle liste

Donc de continuer comme ça jusqu'à ne trouver que les bons chiffres ? (J'essai de chercher une solution ^^)

Sinon je vais tester aussi la solution de MSL_INTERIM, par contre les listes ne sont pas trié donc il faut les trier avant toutes ces boucles.

Merci bien en tout cas.
Non, la bonne solution c'est celle que j'ai donnée en second après relecture (utiliser un HashSet voire un tableau de booléens au lieu de list2), et c'est aussi la plus simple.

Ce n'est pas mon opinion, ce sont les maths qui le disent (complexité temporelle asymptomatique en O(n²)). ;)

DonQuiche a raison.

Effectivement je ne connaissais pas le HashSet et je trouve ca dingue que le Contains possède une complexité de O(1).

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
 
HashSet<int> hsListe1= new HashSet<int>();
 
//Pour tous les éléments de la liste 1
for(int i = 0 ; i < Liste1.Count; i++)
{
  //Ajout dans le HashSet
  hsListe1.add(Liste1[i]);
}
 
//Première boucle afin de parcourrir tous les nombres de la deuxième liste
for(int i = 0 ; i < Liste2.Count ; i++)
{
  //Deuxième boucle afin de parcourir tous les nombres de la deuxième liste
  //(en partant de i+1 car tous les nombre avant i ont déjà été additionné dans une itération précédente et afin de ne pas compter deux fois le même nombre)
  for(int j = i + 1 ; j < Liste2.Count ; j++)
  {
    //Il faut ensuite parcourir le HashSet
    for(int k = 0; k < hsListe1.Count ; k++)
    {
      //Pour savoir si la somme de deux chiffres de la liste deux est égale à un chiffre de la liste un, il faut tout simplement faire :
      if(hsListe1.Contains(Liste2[i] + Liste2[j]))
      {
        MessageBox.Show("Trouvé : " + Liste2[i].ToString() + " + " + Liste2[j].ToString() " = "  (Liste2[i] + Liste2[j]).ToString());
      }
 
    }
  }
}

20/05/2015, 15h25
DonQuiche

Citation:

Envoyé par MSL_INTERIM

Effectivement je ne connaissais pas le HashSet et je trouve ca dingue que le Contains possède une complexité de O(1).

C'est toute la beauté des tables de hachage (hashtable). :D
Le dictionnaire fonctionne d'ailleurs sur le même principe.
22/05/2015, 14h29
Guignon

Cela fait déjà pas mal de solution.
Hélas ça ne fait pas mes affaires.

Merci quand même de votre aide!

Bonne continuation
Gui