我需要比较两个可能缺少元素的非常大的集合

逐步：

• 使用O(1)通用集合之一创建已在第二个集合中的T的可快速搜索列表。我可以建议HashSet<T>
• 枚举第二个集合，并从第一步开始将所有T放入集合中。
• 枚举第一个集合，并检查每个项是否在步骤 1 中创建的集合中。由于该操作O(1)您现在得到了一个O(n)解决方案。
• 享受。

下面是一个将该算法实现为泛型扩展方法的类，以使其对 LINQ 更加友好。将它的参数作为IEnumerable<T>并返回IEnumerable<T>，对类型（T和Complex）没有做出任何假设。在我的测试中，我使用Tuple<int,int>列表作为复杂类型，使用简单int作为简单类型。控制台应用程序用 600000 个值填充List<Tuple<int,int>>，然后将 100000 个值放入简单List<int>中，该使用枚举器对List<Tuple<int,int>>中未找到的所有简单值进行计数;它是如此之快，你没有机会看到它的工作，当你点击F5它只是显示结果。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
    static class FixProblem
    {
        public static IEnumerable<T> FindAllThatNeedCreating<T, Complex>(this IEnumerable<Complex> list_of_complex, IEnumerable<T> list_of_T, Func<Complex, T> extract)
        {
            HashSet<T> T_in_list_of_complex = new HashSet<T>();
            foreach (Complex c in list_of_complex)
                T_in_list_of_complex.Add(extract(c));
            List<T> answer = new List<T>();
            foreach (T t in list_of_T)
                if (!T_in_list_of_complex.Contains(t))
                    answer.Add(t);
            return answer;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            // Test the code
            List<Tuple<int, int>> complex = new List<Tuple<int, int>>();
            List<int> simple = new List<int>();
            // Fill in some random data
            Random rnd = new Random();
            for (int i = 1; i < 600000; i++)
                complex.Add(new Tuple<int, int>(rnd.Next(), rnd.Next()));
            for (int i = 1; i < 100000; i++)
                simple.Add(rnd.Next());
            // This is the magic line of code:
            Console.WriteLine(complex.FindAllThatNeedCreating(simple, x => x.Item1).Count());
            Console.ReadKey();
        }
    }
}

我建议将复杂对象存储在字典中，使用 A 类型属性作为键。然后，您可以非常快速地查看字典中是否存在 A 中的任何元素。每个查找操作将为 O（1），整体性能应为 O（n）。

或者，您可以调用 。ToLookup（） 在现有的 IEnumerable 上，并在 lambda 表达式中创建键和值。返回的 ILookup 应该非常适合您的需求（即从 A 中查找值）。这里的另一个优点是，如果您有多个包含 A 的复杂对象，则在使用 Lookup 时将获得它们的集合。

如果我了解您的要求，那么我认为这段代码效果很好。我已经将两个集合的记录提高到 6.5m 记录，并在 11 秒内完成。将其减少到 650k 条记录只需不到一秒钟的时间。

var rnd = new Random();
var xs = Enumerable
    .Range(0, 650000)
    .Select(x => new Complex<int>()
    {
        MyComplex = rnd.Next(0, 100001)
    })
    .ToList();
var ys = Enumerable
    .Range(0, 650000)
    .Select(x => rnd.Next(0, 100001))
    .ToArray();
var xsLookup = xs.ToLookup(x => x.MyComplex);
var newYs = ys.Where(y => !xsLookup[y].Any()).ToArray();
newYs
    .ToList()
    .ForEach(y =>
    {
        xs.Add(new Complex<int>()
        {
            MyComplex = y
        });
    });

更新：首先，停止使用数据集。我建议你使用Linq to SQL或Entity Framework。

试试这个：

        var lookup = B.ToLookup(c => c.MyComplex);
        var noMatch = from a in A
                      where !lookup.Contains(a)
                      select a;

这应该更快，但要衡量。

然后尝试

        var lookup = B.AsParallel().ToLookup(c => c.MyComplex);
        var noMatch = from a in A.AsParallel()
                      where !lookup.Contains(a)
                      select a;

并再次测量。

显然，请确保 A 中的对象类型覆盖GetHashCode()，并且Equals(object)相关且高效。特别是GetHashCode()应该很有可能不同的对象具有不同的哈希代码，并且仍然很快。

更新：由于我们现在知道 A 中的对象类型是 DateTime，因此对 GetHashCode() 和 Equals(object) 的要求是可以的。

代码变为

        var lookup = B.ToLookup(c => c.Time);
        var noMatch = from a in A
                      where !lookup.Contains(a)
                      select a;

如果两个列表都按同一键排序，则可以同时遍历两者。这样做，我能够将时间缩短到比contains或except的时间更少，甚至比我看到的toLookup时间还要短。

var A = SimpleCollection; // source of truth
var B = GetComplexOnDemand().ToArray();
var missing = new List<Complex<DateTime>>();
int cpxIx = 0;
int simpleIx = 0;
while (simpleIx < A.Count)
{
    if (cpxIx >= B.Length)
    {
        missing.Add(new Complex<DateTime>() {InnerValue = A[simpleIx]});
        simpleIx++;
        continue;
    }
    if (A[simpleIx] != B[cpxIx].InnerValue)
    {
        missing.Add(new Complex<DateTime>() {InnerValue = A[simpleIx]});
        simpleIx++;
        continue;
    }
    cpxIx++;
    simpleIx++;
}

为了生成测试数据，我做了以下操作：

private static readonly List<DateTime> SimpleCollection = 
    Enumerable.Range(1, SimpleSize).Select(t => new DateTime(DateTime.Now.Ticks + t)).ToList();
public static IEnumerable<Complex<DateTime>> GetComplexOnDemand()
{
    for (int i = 1; i <= ComplexSize; i+=2)
    {
        yield return new Complex<DateTime>() { InnerValue = SimpleCollection[i] };
    }
}