Discussion :

[Guignon]

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 :

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

5, 8, 13, 35, 40

Et l'autre en contient d'autre :

Code :

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

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 :

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

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

[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.

[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

[DonQuiche]

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 :

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

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.

[MSL_INTERIM]

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 :

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
 
 
//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

[DonQuiche]

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.