GQ08 X: encore des ensembles


En voici un un peu plus dur. J’ai un ensemble de villes ‘cities’ et une liste de groupes de villes. J’aimerai afficher l’ensemble du contenu de ‘cities’ mais en faisant apparaître les groupes à la place des villes si ceux-ci y sont présents. Les villes isolées apparaissent seules.

var cities = new string[] { "Paris", "Londres", "Berlin", "Madrid", "Bruxelles", "New York", "Seattle", "Tokyo" }; var groups = CreateList( new { Id = "Europe", Cities = new string[] { "Paris", "Londres", "Berlin", "Madrid", "Bruxelles" } }, new { Id = "US", Cities = new string[] { "New York", "Seattle" } } ); var result = new List<string>(); ? foreach (var s in result) Console.WriteLine(s);

Le code de CreateList est ici: http://blogs.msdn.com/mitsufu/archive/2008/08/26/gq08-viii-initialisation-de-collections.aspx


image

Bien évidemment si on enlève “Madrid” de ‘cities’ l’ensemble ‘Europe’ disparaît et les villes sont affichées seules.

image

Personnellement je n’ai pas résolu la question en une seule requête Linq.

A vous de jouer.

Comments (9)

  1. C’est probablement pas la meilleure solution mais je propose ça :

    var q =

       from g in groups

       where g.Cities.All(c => cities.Contains(c))

       select new { g.Id, g.Cities };

    var result = q.Select(g => g.Id).Union(cities.Except(q.SelectMany(g => g.Cities)));

  2. Olivier says:

    J’ai une solution qui marche bien mais qui est très décomposée (maintenabilité ok) mais optimisable (assurément !). Faute de temps pour l’optimisation je donne ce que j’ai… (le client est content, ça répond au cahier des charges, je peux facturer, c’est l’essentiel :-) ).

    La logique :

    Requête q : sélectionne tous les groupes qui sont "complets" c’est à dire dont toutes les villes existent dans Cities.

    Requête qq : sélectionne toutes les villes "orphelines" c’est à dire n’appartenant à aucun des groupes de la requête q.

    Requête qqq : finale. Créée une liste qui contient soit le nom des villes orphelines, soit le nom du groupe pour les villes non orphelines. Le distinct élimine les groupes en double.

    var q = from g in groups

                       where

                           (

                             (

                               (from c in g.Cities join cc in cities on c equals cc select c).Count()

                              )

                              ==

                              g.Cities.Count()

                           )

                       select g;

    var qq = from c in cities

                        where (

                                  !((from g in q where g.Cities.Contains(c) select g).Count() > 0)

                              )

                        select c;

    var qqq = (from c in cities

                         select new

                                    {

                                        name = qq.Contains(c) ? c : (from g in groups from cc in g.Cities where cc==c select g.Id).FirstOrDefault()

                                    }).Distinct();

    foreach (var s in qqq) Console.WriteLine(s.name);

  3. Steph says:

    Olivier, il était écrit dans le cahier des charges : "en une seule requête Linq". Tu ne peux donc pas facturer 😉

  4. Simon says:

    Allez, une seule requète mais c’est bien pourri niveau perf ^^ :

    var q = (from city in cities

                        let matchingGroups = (from g in groups

                                              where g.Cities.All(c => cities.Contains(c))

                                              select g)

                        select matchingGroups.SelectMany(g => g.Cities).Contains(city) ?

                               matchingGroups.Where(g => g.Cities.Contains(city)).First().Id :

                               city).Distinct();

  5. Tetranos says:

    Je propose çà…mais j’ai pas bien pris le temps de tester différent cas :

    var result =

                   from c in cities.Concat((from g in groups where (!g.Cities.Except(cities).Any()) select g.Id))

                   let groupsid = (from g in groups where (!g.Cities.Except(cities).Any()) select g.Id)

                   where (groups.Find(g => groupsid.Contains(g.Id) && g.Cities.Contains(c)) == null)

                   select c;

  6. Tetranos says:

    Voici une variante qui garde le même esprit mais qui me paraît être plus compréhensible :

    var result =

     from name in cities.Concat(groups.Select(g => g.Id))

     let groupsid = (from g in groups where (!g.Cities.Any(c => !cities.Contains(c))) select g.Id)

     where

       (groupsid.Contains(name)) ||

       ((cities.Contains(name)) && (!groups.Any(g => groupsid.Contains(g.Id) && g.Cities.Contains(name))))

     orderby name

     select name;

    – le from concatène les noms de villes et les  identifiants de groupes

    – le let extrait les groupes dont toutes les villes sont dans "cities"

    – la première condition conserve les noms des groupes dont toutes les villes sont dans "cities"

    – la seconde condition conserve les villes qui n’appartiennent pas aux groupes dont toutes les villes sont dans "cities"

    Je pense qu’il peut y avoir un pb avec cette requête si un identifiant de groupe est égal à un nom de ville.

  7. mitsu says:

    Bon on arrive aux limites de Linq en une seule requête. Tout ceux qui ont résolu en une seule requête, réitèrent N fois sur les mêmes ensembles de données que ce soit en utilisant All(), Contains() en en réimbriquant des requêtes elles-même.

    Même si les perfs en prennent un coup, bravo à tous pour votre maîtrise de la syntaxe.

    Ma solution est très proche de celle de Matthieu sauf que: ‘select new { g.Id, g.Cities }’ est un peu équivalent à ‘select g’.

    Je me suis inspiré pour ce quizz d’un algo intéressant qui est l’optimisation de l’affichage d’un enum. En effet, en définissant les valeurs binaires manuellement, on peut définir des groupes dans un enum (ex: WeekEnd = Samedi & Dimanche).

    On peut alors préférer faire afficher les groupes lors d’un .ToString() plutôt que les valeurs unitaires.

    Le code ci-dessous est un tout petit peu différent dans le sens où je refuse que les groupes se chevauchent. Il est intéressant de regarder comment .Intersect() et .Except() jouent le même rôle que les ‘and’ et ‘or’ binaires.

    foreach (var g in groups.OrderByDescending(g => g.Cities.Count()))

    {

       var tmp = remainingCities.Intersect(g.Cities).ToArray();

       if (tmp.Length == g.Cities.Length)

       {

           result.Add(g.Id);

           remainingCities = remainingCities.Except(g.Cities);

       }

    }

    result.AddRange(remainingCities);

  8. Tetranos says:

    Remarque : prendre les groupes dont toutes les villes sont dans "cities" est une division relationnelle.

    En SQL, il existe (à ma connaissance) deux méthodes pour répondre à cette question :

    – le SELECT…WHERE HAVING COUNT

    – le double NOT EXISTS

    Ces deux méthodes utilisant plusieurs SELECT, la requête SQL aurait, comme ici, itérée plusieurs fois sur les mêmes données.