更快的方式来做List <T> .Contains()

Question

我正在尝试做我认为是"去交叉"(我不确定这个名称是什么,但这就是EpicGames的Tim Sweeney在旧的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();

然后,我做另一件事,我从原件中减去结果,看看我删除了哪些元素.使用.Except()非常快,所以没有麻烦.

必须有一种更快的方法来执行此操作,因为这个方法非常糟糕,在列表中有大约30,000个元素(字符串).优选地,执行该步骤的方法以及稍后一次执行的方法将是很好的.我尝试使用.Exists()而不是.Contains(),但它稍慢.我感觉有点厚,但我认为应该可以使用.Except()和.Intersect()和/或.Union()的某种组合.

Answer 1

该操作可以称为对称差异.

您需要一个不同的数据结构,如哈希表.将两组的交集添加到它,然后将每组的交集差异.

更新:

我有点时间在代码中尝试这个.我使用HashSet<T>了一组50,000个字符串,长度为2到10个字符,结果如下:

原文:79499 ms

Hashset:33毫秒

顺便说一句,在HashSet上有一个方法SymmetricExceptWith,我认为它会为我做的工作,但它实际上将两个集合中的不同元素添加到调用该方法的集合中.也许这就是你想要的,而不是保留最初的两组未经修改,代码会更优雅.

这是代码:

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 2

如果使用相交，则可以这样完成：

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