6

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

我正在使用以下代码：

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

对于 CPU 时间，VS Profiler 表示

  • 85.1%System.Linq.Enumerable.Count()
  • 0.3% 在System.Linq.Enumerable.Intersect()

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

如何更快地做到这一点？

4

5 回答 5

4

你可以HashSet使用arr2

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

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

于 2012-12-16T11:10:20.733 回答
1

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

我相信Intersect应该进行一些内部优化以使其相当快，但是您可以尝试使用 aHashSet<string>这样您就可以确定可以在不搜索每个元素的内部数组的情况下进行相交：

HashSet<string> set = new HashSet<string>(arr1);
set.IntersectWith(arr2);
int count = set.Count;
于 2012-12-16T10:53:29.843 回答
1

嗯，相交可能是 N^2

使其更快地对两个数组进行快速排序。而不是遍历两个数组。计算交叉点。

懒得测试它有多快，但应该 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<string> set = new HashSet<string>(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<string> set = new HashSet<string>(arr1);
                set.IntersectWith(arr2);
                int count = set.Count;
                Console.WriteLine("HashSet + new" + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp));
            }

            {
                var stamp = (System.Diagnostics.Stopwatch.GetTimestamp());
                SortedSet<string> set = new SortedSet<string>(arr1);
                set.IntersectWith(arr2);
                int count = set.Count;
                Console.WriteLine("SortedSet +new " + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp));
            }

            {

                SortedSet<string> set = new SortedSet<string>(arr1);
                var stamp = (System.Diagnostics.Stopwatch.GetTimestamp());
                set.IntersectWith(arr2);
                int count = set.Count;
                Console.WriteLine("SortedSet without new " + (System.Diagnostics.Stopwatch.GetTimestamp() - stamp));
            }
        }
    }
}

结果

数组 914,637

哈希集 816,119

HashSet +新 1,150,978

排序集 +新 16,173,836

SortedSet 没有新的 7,946,709

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

于 2012-12-16T11:00:03.773 回答
0

当您使用集合时，您的复杂性将是 O((n log n)*(m log m)) 左右，

我认为这里应该更快，但我不确定现在是否为 O((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();
于 2012-12-16T11:06:18.413 回答
0

Build a HashSet using the smaller array and then loop through the bigger one, incrementing a counter if the item it exists in the hashset.

于 2012-12-16T11:33:40.147 回答