Discussion :

[ephleim]

Bonjour,

J'ai un problème un peu pointu que je dois résoudre en cherchant une solution performante en terme de vitesse. Pourriez vous me conseiller ?

J'ai une liste de string (le critère), et une collection de liste de string.

Je dois trouver dans ma collection la liste de string dont tout les éléments sont inclus dans mon critère, et si plusieurs listes répondent à cela, ne garder que celles qui ne sont pas incluse dans une autre

exemple :

Critère : {"A", "B", "D","E"}
Collection : {{"F"}, {"A"}, {"A","B"}, {"A","D","E"}}

l’algorithme devrais renvoyer :
{{"A","B"}, {"A","D","E"}}

Merci de votre aide !

[hussein47]

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
            var criteres = new List<string>() { "A", "B", "C" };
            var collections = new List<List<string>>
            { 
                new List<string>() { "F" } ,                
                new List<string>() { "A", "B" } , 
                new List<string>() { "A" },
                new List<string>() { "A", "C" } ,
                new List<string>() { "A", "C", "A", "B" } ,
            };
 
            var resultats = new List<List<string>>();
 
            // On recherche les liste valides
            foreach (var listeStr in collections)
            {
                var valide = true;
                foreach (var str in listeStr)
                {
                    if (!criteres.Contains(str))
                    {
                        valide = false;
                        break;
                    }
                }
 
                if (!valide)
                {
                    continue;
                }
 
                resultats.Add(listeStr);
            }
 
            /*
             * On met en ordre la liste par rapport a la longueur, car il est impossible qu'une grande liste             
             * soit contenue dans une plus petite.             * 
             */
            resultats = resultats.OrderBy(resultat => resultat.Count).ToList();
 
            var resultatsInvalide = new List<List<string>>();
 
            // On cherche les listes deja contenues dans d'autres
            for (int i = 0; i < resultats.Count - 1; i++)
            {
                for (int k = i + 1; k < resultats.Count; k++)
                {
                    var valide = false;
                    foreach (var str in resultats[i])
                    {
                        if (!resultats[k].Contains(str))
                        {
                            valide = true;
                            break;
                        }
                    }
 
                    if (!valide)
                    {
                        resultatsInvalide.Add(resultats[i]);
                        break;
                    }
                }               
            }
 
            // On retire les listes trouvées
            foreach (var invalide in resultatsInvalide)
            {
                resultats.Remove(invalide);
            }

En espérant que cela t'aide !

[tomlev]

A priori le plus simple est de le faire en deux temps :

- trouver toutes les collections qui correspondent :

Code :

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

1
2
3
4
5
6
7
List<string> criteres = ...
List<List<string>> collections = ...
 
var matches =
    (from c in collections
     where c.All(s => criteres.Contains(s))
     select c).ToList();

- éliminer les collections contenues dans une autre collection :

Code :

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

1
2
3
4
var results =
    from c in matches
    where !matches.Any(other => c != other && c.Count <= other.Count && c.All(s => other.Contains(s)))
    select c;

(je suppose que la solution de hussein47 fonctionne aussi, mais je trouve ça plus simple avec Linq...)

[ephleim]

Merci pour vos réponses, j'aurais au moins gagné quelques syntaxes plus pratiques pour ce problème.

Mais en fait je recherche plutôt un algorithme qui me permettrais de réduire la complexité. Actuellement j'ai quelque chose un peu comme vous qui commence par parcourir les critères n fois par élément de la collection, et qui continue en parcourant toutes les combinaisons des résultats deux par deux.
Si je ne me trompe pas, on a une complexité en O(2), donc des qu'il y a bcp d’éléments c'est à éviter...

Je me demande si ce ne serait pas possible de précalculer les résultats en quelque sorte, bien que cela risque de transformer le problème en un problème de grosse volumétrie

[hussein47]

Niveau perf ma méthode ira beaucoup plus vite que linq.

[tomlev]

Niveau perf ma méthode ira beaucoup plus vite que linq.

Je te trouve bien sûr de toi... tu as benchmarké les 2 solutions ?

Il se peut que tu aies raison sur ce cas précis (je n'ai pas examiné en détail ta façon de faire, ni mesuré les perfs), mais à moins d'avoir fait des tests précis il vaut mieux se garder de ce genre de supposition, car on a souvent des surprises.

Je sais pas pourquoi tout le monde suppose que Linq est moins performant... ça fait à peu près la même chose, sauf que les boucles que tu fais explicitement sont implicites en Linq. il y a un léger overhead à cause des delegates, mais en général c'est tellement insignifiant que c'est difficilement mesurable.