Comment soustraire une liste énorme de l'autre efficacement en C#

J'ai une très longue liste d'Id (entiers) qui représente tous les éléments qui sont actuellement dans ma base de données:

var idList = GetAllIds();

J'ai aussi un autre énorme liste générique avec les éléments à ajouter à la base de données:

List<T> itemsToAdd;

Maintenant, je voudrais supprimer tous les éléments de la liste générique dont l'Id est déjà dans le idList.
Actuellement idList est un simple tableau et je soustrais les listes comme ceci: 

itemsToAdd.RemoveAll(e => idList.Contains(e.Id));

Je suis assez sûr qu'elle pourrait être beaucoup plus rapide, de sorte que les types de données dois-je utiliser pour les deux collections et quelle est la plus efficace et pratique pour soustraire eux?

Merci!

  • Je voudrais savoir comment diffuser/énumérer ce ainsi, si possible...
InformationsquelleAutor Shackles | 2011-02-23
  1. 18

    Transformer temporairement idList à un HashSet<T> et d'utiliser la même méthode, à savoir:

    items.RemoveAll(e => idListHash.Contains(e.Id));

    il devrait être beaucoup plus rapide

    • Merci - qui effectue beaucoup plus rapidement, en effet, et c'est ce que j'ai fait!
    InformationsquelleAutor digEmAll
  2. 23

    LINQ pourrait aider:

    itemsToAdd.Except(idList)

    Votre code est lent parce que List<T>.Contains est O(n). Si votre coût total est O(itemsToAdd.Count*idList.Count).

    Vous pouvez faire idList dans un HashSet<T> qui a O(1) .Contains. Ou simplement l'utiliser Linq .Except méthode d'extension qui le fait pour vous.

    Noter que .Except allons également supprimer tous les doublons à partir de la gauche. c'est à dire de nouveaux int[]{1,1,2}.Except(new int[]{2}) donneront lieu à {1} et la deuxième 1 a été supprimé. Mais je suppose que ça ne pose aucun problème dans votre cas, parce que les Id sont généralement unique.

    • Notez qu'il sera également exclure tous les doublons de itemsToAdd. Si oui ou non c'est un problème est à l'OP (je pense que non, car ils sont déjà à l'aide de RemoveAll leur exemple).
    • +1 et merci pour l'excellente explication! J'ai maintenant construire idList comme Hashset<int>, mais ne peut pas l'utiliser .À l'exception de() car itemsToAdd est de type Liste/HashSet<T>, et idList est de type HashSet<int>. Il est beaucoup plus rapide bien et répond à mes besoins.
    InformationsquelleAutor CodesInChaos
  3. 5

    En supposant les prémisses suivantes sont remplies:

    • idList et itemsToAdd ne peut pas contenir de doublons
    • vous êtes en utilisant le .NET Framework 4.0

    vous pouvez utiliser un HashSet<T> de cette façon:

    var itemsToAddSet = new HashSet(itemsToAdd);
itemsToAddSet.ExceptWith(idList);

    Selon la documentation de la ISet<T>.ExceptWith méthode est assez efficace:

    Cette méthode est un O(n) opérations,
    où n est le nombre d'éléments dans
    le autres paramètre.

    Dans votre cas n est le nombre d'éléments dans idList.

    • Le problème est que itemsToAdd serait de type HashSet<T>, et idList est de type HashSet<int>. Donc je ne peux pas appeler ExceptWith sur ces deux et nécessaire à la transformation de idList dans un Hashset<T> qui n'en consomment beaucoup de mémoire.
    • idList n'a pas à être un HashSet<int>, il vous suffit de créer un HashSet de itemsToAdd. Vous pourrez ensuite passer idList à HashSet<T>.ExceptWith comme un IEnumerable<T>.
    InformationsquelleAutor Enrico Campidoglio
  4. 2

    Vous devez utiliser deux HashSet<int>s.

    Notez qu'ils sont uniques et non-ordonnées.

    InformationsquelleAutor SLaks