快速count（）两个字符串数组的交集

我需要计算对应于两个大字符串数组的交集的元素数量，并且非常快。

我使用以下代码： 

arr1[i].Intersect(arr2[j]).Count()

对于CPU时间，VS Profiler指示

  • System.Linq.Enumerable.Count() 85.1％
  • System.Linq.Enumerable.Intersect() 0.3％

不幸的是，完成所有工作可能需要数小时。

怎么做得更快？

您可以将HashSet与arr2 

 HashSet arr2Set = new HashSet(arr2); arr1.Where(x=>arr2Set.Contains(x)).Count(); ------------------ | |->HashSet's contains method executes quickly using hash-based lookup..

不考虑从arr2到arr2Set的转换，这应该是O(n)

我怀疑分析器显示在Count中消耗时间的原因是，这是实际枚举集合的位置（ Intersect是懒惰评估的，并且在您需要结果之前不会运行）。

我相信Intersect应该有一些内部优化来使这个速度相当快，但你可以尝试使用HashSet这样你就可以确保可以在不搜索每个元素的内部数组的情况下进行交叉： 

 HashSet set = new HashSet(arr1); set.IntersectWith(arr2); int count = set.Count;

嗯相交可能是N ^ 2

使它快速快速排序两个arrays。 而不是遍历两个数组。 计算交叉点。

太懒了测试它会有多快，但应该是O（nlogn + n） 

  using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Test { class Program { static void Main(string[] args) { const int arrsize = 1000000; Random rnd = new Random(42); string[] arr1 = new string[arrsize]; string[] arr2 = new string[arrsize]; for (int i = 0; i < arrsize; i++) { arr1[i] = rnd.Next().ToString(); arr2[i] = rnd.Next().ToString(); } { var stamp = (System.Diagnostics.Stopwatch.GetTimestamp()); arr1.Intersect(arr2).Count(); Console.WriteLine("array" + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp)); } { HashSet set = new HashSet(arr1); var stamp = (System.Diagnostics.Stopwatch.GetTimestamp()); set.IntersectWith(arr2); int count = set.Count; Console.WriteLine("HashSet" + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp)); } { var stamp = (System.Diagnostics.Stopwatch.GetTimestamp()); HashSet set = new HashSet(arr1); set.IntersectWith(arr2); int count = set.Count; Console.WriteLine("HashSet + new" + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp)); } { var stamp = (System.Diagnostics.Stopwatch.GetTimestamp()); SortedSet set = new SortedSet(arr1); set.IntersectWith(arr2); int count = set.Count; Console.WriteLine("SortedSet +new " + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp)); } { SortedSet set = new SortedSet(arr1); var stamp = (System.Diagnostics.Stopwatch.GetTimestamp()); set.IntersectWith(arr2); int count = set.Count; Console.WriteLine("SortedSet without new " + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp)); } } } }

结果

arrays914,637

哈希集816,119

HashSet +新增1,150,978

SortedSet + new 16,173,836

SortedSet没有新的7,946,709

所以似乎最好的方法是保持一个准备好的哈希集。

当你使用集合时，你的复杂性将是O（（n log n）*（m log m））左右，

我认为这里应该更快，但我不确定它现在是否是（（n log n）+（m log m）） 

 possible would be var Set1 = arr1[i].Distinct().ToArray(); // if necessary, if arr1 or arr2 could be not distinct var Set2 = arr2[j].Distinct().ToArray(); nCount = Set1.Count() + Set2.Count() - Set1.Append(Set2).Distinct().Count();

使用较小的数组构建HashSet ，然后循环遍历较大的数组，如果项目存在于hashset中，则递增计数器。

Interesting Posts