2
votes

Utiliser LINQ pour trouver des lacunes dans une liste triée d'objets?

Problème: J'ai un wpf DataGrid , qui est lié à une liste d'objets de ma classe de modèle personnalisée. Je dois remplir les conditions suivantes:

Il n'y a qu'un certain nombre de modèles dans cette liste (pensez à un jeu vidéo en ligne à 8 joueurs par exemple)
Chaque modèle a son propre identifiant unique
Des modèles peuvent être ajoutés et supprimés de la liste lors de l'exécution
Lors de l'initialisation, chaque modèle doit obtenir l'ID gratuit le plus bas de la liste
Je ne souhaite pas parcourir la liste à chaque fois qu'un nouveau modèle est ajouté
Tout cela doit se produire en back-end, je ne peux donc pas utiliser de code xaml (c'est aussi pourquoi je n'ai pas défini la balise wpf)

Je recherche quelque chose de similaire à cette question , mais j'ai du mal à convertir ma liste en quelque chose qui serait compatible avec la méthode Enumerable.Except .

Voici un petit exemple:

Modèle:

  List<MyModel> list = new List<MyModel>();
  list.Add(new MyModel(0, "Rodney", "189"));
  list.Add(new MyModel(1, "Janet", "169"));
  list.Add(new MyModel(2, "John", "110"));
  list.Add(new MyModel(3, "Samantha", "160"));
  list.Add(new MyModel(4, "Daniel", "156"));
  list.Add(new MyModel(5, "Jack", "89"));

  list.RemoveAll(x => x.ID == 1);
  var result = Enumerable.Range(list.Min(m => m.ID), list.Count).Except(list).First();
  list.Add(new MyModel(result, "Carolyn", "159")); //Should be 1

Essayer d'ajouter un nouveau modèle avec l'ID gratuit le plus bas à ma liste

public class MyModel
{
    public MyModel(int mID, string mName, string mScore)
    {
      ID = mID;
      Name = mName;
      Score = mScore;
    }
    public int ID;
    public string Name;
    public string Score;
  }

Je dois probablement utiliser une sorte d'expressions lambda, comme je devais le faire pour la méthode list.Min () , mais il m'a déjà fallu du temps pour l'obtenir ce droit.

c# linq

3 commentaires

Vous voudrez peut-être jeter un œil sur Collection SortedList

Une réponse générale à votre question peut être intéressante, mais il y a des indices que vous y réfléchissez peut-être trop. Pourquoi ne voulez-vous pas parcourir une petite liste à chaque fois qu'elle change? À quelle fréquence change-t-il? Itérer sur de petites collections (<100 éléments) est souvent plus rapide que des approches plus intelligentes. Et même si ce n'est pas le cas, vous devez vous demander si le fait d'être intelligent en vaut la peine.

@TKK la petite liste n'est qu'un exemple. Je ne sais pas quelle sera la taille des listes (en fait, la liste actuelle contient déjà plus de quelques centaines d'entrées), mais je suis chargé de créer une méthode générale à utiliser pour remplir toutes les listes de notre application.

4 Réponses :

2
votes

Le problème est que vous comparez deux types d'objets différents. Enumerable.Range (list.Min (m => m.ID), list.Count) est une énumération d'entiers entre 0 et 5, et lorsque vous utilisez Sauf (liste) code>, la liste est constituée d'objets MyModel .

Vous souhaitez probablement extraire les identifiants:

 var result = Enumerable.Range(list.Min(m => m.ID), list.Count).Except(list.Select(m => m.ID)).First();

1 commentaires

Il est probablement préférable d'utiliser .FirstOrDefault () pour éviter l'exception lorsque l'élément avec x.ID == 0 se trouve être celui qui a été supprimé. Une manipulation est également nécessaire au cas où il n'y aurait pas d'espace (le résultat sera 0).

2
votes

Pourquoi créer du code compliqué? Vous voulez que le nombre soit supérieur à l'élément le plus bas qui n'existe pas dans la liste

 var result = list.Min(m => m.ID);
 while (list.Any(m => m.ID == result))
   result++;

Ce n'est peut-être pas le code le plus rapide, mais au moins il est clair.

0 commentaires

0
votes

Pour développer ce qu'un commentateur a publié, utilisez un SortedList , que vous pouvez utiliser pour suivre les identifiants gratuits. De cette façon, vous n'avez pas à rechercher de lacunes. Lorsque vous ajoutez quelque chose à la liste principale, supprimez le premier entier de la liste libre et utilisez cette valeur comme ID de votre modèle. Lorsque vous supprimez le modèle de la liste principale, ajoutez son identifiant à la liste gratuite.

0 commentaires

1
votes

Je ne veux pas parcourir la liste à chaque fois qu'un nouveau modèle est ajouté

En fait, cela signifie que vous ne pouvez pas utiliser les méthodes Linq comme Min , Max et Sauf car elles parcourent votre collection sous le capot.

Une autre chose que vous devez garder à l'esprit est que RemoveAll parcourt également tous les éléments de la liste. Vous devez donc changer deux choses: la première (déjà mentionnée dans le commentaire Fabjan et dans la réponse du Kit) est de suivre tous les identifiants supprimés dans SortedList et la seconde est d'utiliser un Dictionary pour supprimer votre modèle par clé, ce qui est de complexité O (1) au lieu de O (N) dans le cas de List .

Vous pouvez encapsuler cette logique avec la classe Container suivante:
public class Container
{
    private readonly Dictionary<int, MyModel> items = new Dictionary<int, MyModel>();
    private readonly SortedList removedIds = new SortedList();
    private int maxId = 0;

    public int Add(MyModel model)
    {
        int id;
        if (removedIds.Count > 0)
        {
            id = (int) removedIds.GetByIndex(0);
            removedIds.RemoveAt(0);
        }
        else
        {
            id = maxId++;
        }

        model.ID = id;
        items.Add(id, model);
        return id;
    }

    public void RemoveById(int id)
    {
        if (!items.ContainsKey(id))
            throw new ArgumentException(); // or just return

        items.Remove(id);
        removedIds.Add(id, id);
    }
}

0 commentaires