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.

[hussein47]

Jusqu’à 100 000 liste j'ai un gain de 100% par rapport a linq, a partir d'un million je commence a réduire l’écart, le fait est que pour vérifier une liste je ne parcours que les listes plus grandes car elle ne peut pas être contenue dans une plus petite. Et je pense que mon code est pas très optimisé, il doit y avoir des meilleures façons de faire.

EDIT : Plus les listes contenues dans la collection sont longues, meilleure ma methode est, je monte jusque 350% de gain pour une collection de 100 000 listes de taille variante entre 1 et 100.

[tomlev]

le fait est que pour vérifier une liste je ne parcours que les listes plus grandes car elle ne peut pas être contenue dans une plus petite.

Effectivement... j'ai d'ailleurs rajouté cette optimisation dans mon code.

Jusqu’à 100 000 liste j'ai un gain de 100% par rapport a linq, a partir d'un million je commence a réduire l’écart,le fait est que pour vérifier une liste je ne parcours que les listes plus grandes car elle ne peut pas être contenue dans une plus petite. Et je pense que mon code est pas très optimisé, il doit y avoir des meilleures façons de faire.

EDIT : Plus les listes contenues dans la collection sont longues, meilleure ma methode est, je monte jusque 350% de gain pour une collection de 100 000 listes de taille variante entre 1 et 100.

On a pas du faire les mêmes tests alors... avec 1 million de listes entre 0 et 50 éléments, et une liste de 20 critères, ma solution est en moyenne 3 fois plus rapide.

J'ai fait varier différents paramètres, dans certaines situations ta technique est plus rapide, mais pas de beaucoup (5 à 10%)

Après on a sans doute pas testé exactement de la même manière... Ma méthodologie est la suivante :

- j'ai fait 2 méthodes avec la même signature, l'une avec mon implémentation, l'autre avec la tienne
- je fais un premier run de chaque méthode pour que le JIT ne vienne pas fausser les résultats
- j'exécute chaque méthode 100 fois pour avoir un temps moyen
- j'utilise un Stopwatch pour mesurer les temps (plus précis que DateTime)

[hussein47]

Je n'utilise pas autant de critères et mes listes varient de 1 a 100 strings, tu doit sans doute avoir raison par rapport aux situations dans lesquelles ma fonction ira plus vite, car en essayant avec plusieurs autres modifications il s'avère que linq va plus vite, autant pour moi ^^