7

我正在尝试做我认为是“反相交”的事情（我不确定正确的名称是什么，但这就是 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() 的某种组合应该是可能的。

4

5 回答 5

6

这种操作可以称为对称差分。

您需要不同的数据结构，例如哈希表。将两个集合的交集添加到它，然后将每个集合的交集区分开。

更新：

我有一些时间在代码中尝试这个。我使用HashSet<T>了一组 50,000 个字符串，长度为 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;
    }
}
于 2009-03-12T23:44:58.207 回答
3

使用 intersect 可以这样完成：

var matches = ((from f in foo 
                select f)
              .Intersect(
                  from b in bar 
                  select b, StringComparer.InvariantCultureIgnoreCase))
于 2009-03-12T23:52:02.773 回答
1

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

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

于 2009-03-12T23:47:06.313 回答
1

使用排序列表，您可以使用二进制搜索。

于 2009-03-19T02:15:10.467 回答
0

包含在列表中是 O(N) 操作。如果您有不同的数据结构，例如排序列表或字典，您将大大减少您的时间。访问排序列表中的键通常是 O(log N) 时间，而在哈希中通常是 O(1) 时间。

于 2009-03-12T23:45:25.990 回答