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

我在为我的工作写的一个程序中遇到了一堵砖墙。 你不需要具体了解上下文，但长话短说，我有两个约650k记录的集合。

我们假设集合A是我知道的正确的集合，集合B是我知道的不正确的集合。

集合B包含一个复杂的对象，它具有与集合A中的元素相同类型的属性（换句话说，它看起来有点像这样）：

// Where T : IComparable IEnumerable A = ...; // Collection of T elements IEnumerable B = ...; // Collection of complex elements. class Complex { public DateTime Time { get; set; } ..... } 

我的问题是我基本上需要按顺序枚举A并查看A的当前元素是否存在于B中的Complex对象中; 如果它不存在，那么我需要创建一个Complex对象，它将封装该元素（以及其他内容）。

当我意识到两个列表长度为650,000个元素时，问题就出现了。 我无法减少数据集; 我必须使用这些650,000。 现在我已经使用了ICollection.Contains() ，我尝试了一个（天真的）二进制搜索实现，但它只需要太长时间。

你有什么建议吗？

编辑：如果有帮助，T实现IComparable。 EDIT2：更多上下文：使用Linq To Objects从DataTable中检索IEnumerable。

  IEnumerable set = set.Tbl .Where(dbObject => dbObject.TS.CompareTo(default(DateTime)) != 0) .Select(Func) // Function that wraps the DataRow in a Complex object // Just done to make debugging a little easier so we still have a large sample but small enough that it doesn't make me grow a beard .Take(100000) .AsEnumerable(); 

为了完整性，如果这个问题被归档并且其他任何人需要解决这个问题，我当前的实现看起来有点像这样

  BDataSet bSet = new BDataSet(); B_LUTableAdapter adap = new B_LUTableAdapter(); adap.Fill(bSet.B_LU); IEnumerable w3 = bSet.B .Where(dbObject => dbObject.TS.CompareTo(default(DateTime)) != 0) // Function that just wraps datarow into a complex object .Select(Func) // Just for sake of debugging speed .Take(100000) .AsEnumerable(); List b = bSet.OrderBy(x => x.Time).ToList(); // Get last & first timestamps // Some of the timestamps in b are 01/01/1011 for some reason, // So we do this check. Complex start = b.Where(x => x.Time != default(DateTime)).First(); Complex end = b.Last(); List a = new List(); // RoundSeconds reduces seconds in a DateTime to 0. DateTime current = RoundSeconds(new DateTime(start.Time.Ticks)); while (current.CompareTo(RoundSeconds(end.Time)) <= 0) { a.Add(current); current = current.Add(TimeSpan.FromMinutes(1)); } IEnumerable times = b.Select(x => x.Time); var missing = a.Where(dt => times.Contains(dt)); foreach (var dt in missing) { adap.Insert(dt, 0, "", "", "", null, 0, 0); // This has since been changed to List.Add() } 

感谢Cosmin，此问题现已解决，完成的实现是：List expected = new List（）; DateTime current = RoundSeconds（new DateTime（start.Time.Ticks））;

  while (current.CompareTo(RoundSeconds(end.Time))  x.Time); if(!missing.Any()) return; Console.WriteLine("{0} missing intervals.", missing.Count()); foreach (var dt in missing) { b.Add(new Complex() { /* some values */ }); //Console.WriteLine("\t> Inserted new record at {0}", dt); } //..... public static IEnumerable FindAllMissing(this IEnumerable complexList, IEnumerable basicList, Func selector) { HashSet inComplexList = new HashSet(); foreach (Complex c in complexList) inComplexList.Add(selector(c)); List missing = new List(); foreach (Basic basic in basicList) if (!(inComplexList.Contains(basic))) missing.Add(basic); return missing; } 

Answer 1

一步步：

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

---

这是一个将该算法实现为通用扩展方法的类，以使其对LINQ更加友好。 将其作为IEnumerable的参数并返回IEnumerable ，不对类型（ T和Complex ）做出假设。 在我的测试中，我使用Tuple作为复杂类型，使用简单int作为简单类型。 控制台应用程序使用600000值填充List> ，然后将100000个值放入使用枚举器的简单List ，以计算List>中未找到的所有简单值List> ; 它是如此之快，你没有机会看到它正在做它的工作，当你点击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 FindAllThatNeedCreating(this IEnumerable list_of_complex, IEnumerable list_of_T, Func extract) { HashSet T_in_list_of_complex = new HashSet(); foreach (Complex c in list_of_complex) T_in_list_of_complex.Add(extract(c)); List answer = new List(); 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> complex = new List>(); List simple = new List(); // Fill in some random data Random rnd = new Random(); for (int i = 1; i < 600000; i++) complex.Add(new Tuple(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(); } } } 

Answer 2

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

或者，您可以在现有IEnumerable上调用.ToLookup（），并在lambda表达式中创建键和值。 返回的ILookup应该是完美的满足您的需求（即从A中查找值）。 这里的另一个好处是，如果你有多个包含A的复杂对象，当你使用Lookup时，你会得到它们的集合。

Answer 3

如果我理解了您的要求，那么我认为这段代码运作良好。 我已将它提升到650万条记录，并在11秒内完成。 将其减少到650k记录只需不到一秒钟。

 var rnd = new Random(); var xs = Enumerable .Range(0, 650000) .Select(x => new Complex() { 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() { MyComplex = y }); }); 

Answer 4

更新：首先，停止使用数据集。 我建议你使用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; 

Answer 5

如果列表都是按相同的键排序，则可以同时循环访问这两个列表。 这样做我能够把时间缩短到比我所看到的toLookup时间的contains或者except甚至更少的时间。

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

要生成测试数据，我执行了以下操作：

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