更快的方式执行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() 的某种组合应该是可能的。

- J F

---

你为什么要做两次？第一次包含比较不是已经给出了所有匹配项吗？除非我理解错了。 - gcores

我需要保留大小写，这在两个列表之间可能（并且应该）不同。 基本上，这是为了一个自动目录比较程序，它可以同步路径和文件名的大小写，并忽略两侧不匹配的条目。 - J F

Answer 1

这个操作叫做对称差。

您需要一个不同的数据结构，比如哈希表。将两个集合的交集添加到其中，然后从每个集合中减去交集。

更新:

我抽出一点时间在代码中尝试了一下。我使用了一个拥有50,000个字符串的HashSet<T>集合，长度介于2到10个字符之间，结果如下：

原始时间: 79499 毫秒

哈希集合时间: 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;
    }
}

- codekaizen

Answer 2

使用交集操作，代码如下：

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

- gcores

---

哇，太棒了。处理两个列表，每个列表约有28,000个条目，只需要145毫秒而不是40秒，这真的很好。也许使用字典可以获得更多收益，但我对此非常满意！ - J F

“var matches = foo.Intersect(bar, StringComparer.InvariantCultureIgnoreCase);”有什么问题？不需要空的选择语句。 - Emperor XLII

Answer 3

如果每个列表中的元素都是唯一的，您应该考虑使用 HashSet。

HashSet(T)类提供高性能的集合操作。集合是一个不包含重复元素且元素没有特定顺序的集合。

- Luca Martinetti

Answer 4

使用排序列表，您可以使用二分查找。

- user79829

Answer 5

在列表中进行包含操作的时间复杂度为O(N)。如果使用不同的数据结构，比如排序列表或字典，可以大大减少时间。在排序列表中访问关键字通常需要O(log N)时间，在哈希表中通常只需要O(1)时间。

- Robert P