Un moyen plus rapide de faire une liste < T > .Contains ()

Question

J'essaie de faire ce que je pense être un "désintersection" (Je ne suis pas sûr du nom exact, mais c'est ainsi que Tim Sweeney de EpicGames l'a appelé dans le vieil UnrealEd.)

// foo and bar have some identical elements (given a case-insensitive match)
List‹string› foo = GetFoo();
List‹string› bar = GetBar();

// remove non matches
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();

Ensuite, je fais une autre chose en soustrayant le résultat de l'original pour voir les éléments que j'ai supprimés. C'est très rapide avec .Except (), donc pas de problèmes là-bas.

Il doit y avoir un moyen plus rapide de le faire, car celui-ci est assez peu performant avec environ 30 000 éléments (de chaîne) dans l'une ou l'autre liste. De préférence, une méthode pour faire cette étape et celle plus tard d'un seul coup serait bien. J'ai essayé d'utiliser .Exists () au lieu de .Contains (), mais c'est un peu plus lent. Je me sens un peu épais, mais je pense que cela devrait être possible avec une combinaison de .Except () et .Intersect () et / ou .Union ().

Answer 1

Avec intersecter cela se ferait comme ceci:

var matches = ((from f in foo 
                select f)
              .Intersect(
                  from b in bar 
                  select b, StringComparer.InvariantCultureIgnoreCase))

Answer 2

Cette opération peut s'appeler une différence symétrique.

Vous avez besoin d'une structure de données différente, telle qu'une table de hachage. Ajoutez-y l'intersection des deux ensembles, puis faites la différence entre chaque ensemble.

UPDATE:

J'ai eu un peu de temps pour essayer ceci dans le code. J'ai utilisé HashSet < T > avec un jeu de 50 000 chaînes, d'une longueur de 2 à 10 caractères, avec les résultats suivants:

  

Original : 79499 ms

     

Hashset : 33 ms

BTW, il y a une méthode sur HashSet appelée SymmetricExceptWith qui, selon moi, ferait le travail à ma place, mais ajoute en fait les différents éléments des deux ensembles à l'ensemble sur lequel la méthode est appelée. C’est peut-être ce que vous voulez, au lieu de laisser les deux jeux initiaux inchangés et le code serait plus élégant.

Voici le code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // foo and bar have some identical elements (given a case-insensitive match)
        var foo = getRandomStrings();
        var bar = getRandomStrings();

        var timer = new Stopwatch();

        timer.Start();
        // remove non matches
        var f = foo.Where(x => !bar.Contains(x)).ToList();
        var b = bar.Where(x => !foo.Contains(x)).ToList();
        timer.Stop();

        Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds));

        timer.Reset();

        timer.Start();
        var intersect = new HashSet<String>(foo);
        intersect.IntersectWith(bar);

        var fSet = new HashSet<String>(foo);
        var bSet = new HashSet<String>(bar);

        fSet.ExceptWith(intersect);
        bSet.ExceptWith(intersect);
        timer.Stop();

        var fCheck = new HashSet<String>(f);
        var bCheck = new HashSet<String>(b);

        Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds));

        Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set));
        Console.ReadKey();
    }

    static Random _rnd = new Random();

    private const int Count = 50000;

    private static List<string> getRandomStrings() 
    {
        var strings = new List<String>(Count);

        var chars = new Char[10];

        for (var i = 0; i < Count; i++)
        {
            var len = _rnd.Next(2, 10);

            for (var j = 0; j < len; j++)
            {
                var c = (Char)_rnd.Next('a', 'z');
                chars[j] = c;
            }

            strings.Add(new String(chars, 0, len));
        }

        return strings;
    }
}

Answer 3

Si les éléments sont uniques dans chaque liste, vous devez envisager d'utiliser un HashSet

  

La classe HashSet (T) fournit une haute   les performances de l'ensemble des opérations. Un ensemble est un   collection qui ne contient pas de doublon   éléments, et dont les éléments ne sont en aucun   ordre particulier.

Answer 4

Avec la liste triée, vous pouvez utiliser la recherche binaire.

Answer 5

La liste contient une opération O (N). Si vous aviez une structure de données différente, telle qu'une liste triée ou un dictionnaire, vous réduiriez considérablement votre temps. L'accès à une clé dans une liste triée est généralement le temps O (journal N) et dans un hachage est généralement le temps O (1).