Увеличение производительности при сравнении двух списков

Question

Какие параметры у меня есть, когда дело доходит до сравнения элементов в двух списках? У меня возникли некоторые проблемы с производительностью, и я хотел бы знать, если есть какие-либо более быстрые альтернативы:

int[] foo = { 1, 2, 3, 4, 5 }; 
int[] bar = { 6, 7, 8, 9, 1 }; 

var result = foo.Any(x => bar.Contains(x)); 

Независимо от того, если я использую методы лямбды или использовать foreach самостоятельно, я предполагаю, что потеря производительности будет все еще будет O(N^2). Могу ли я сделать что-нибудь, чтобы повлиять на это?

Answer 1

Вы можете использование Enumerable.Intersect:

var result = foo.Intersect(bar).Any(); 

Это создает Set<T> от bar элементов, а затем перечисляет foo, пока не будет найден первый матч. Внутренне, который выглядит как:

Set<int> set = new Set<int>(); 

foreach (int local in bar) // M times 
    set.Add(local); // O(1) 

foreach (int value in foo) // N times max 
{ 
    if (!set.Remove(value)) // O(1) 
     continue; 

    yield return value; 
} 

Как Patryk Ćwiek правильно указал, что дает вам O (N + M) вместо O (N * M)

Answer 2

Вы можете использовать HashSet:

int[] foo = { 1, 2, 3, 4, 5 }; 
int[] bar = { 6, 7, 8, 9, 1 }; 
var hashSet = new Hashset<int>(bar); 
var result = foo.Any(x => hashSet.Contains(x)); 

Или вы можете использовать Except с Любой как это:

var result = !foo.Except(bar).Any(); 

Держу пари, что гонка с Sergey's solution: р

Answer 3

Для полноты, вот тест программа для тестирования различных ответы в этой теме.

кажется, показывают, что HashSet подход незначительно быстро:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

namespace Demo 
{ 
    internal class Program 
    { 
     private void run() 
     { 
      var foo = Enumerable.Range( 0, 100000).ToArray(); 
      var bar = Enumerable.Range(100000, 100000).ToArray(); 

      int trials = 4; 

      Stopwatch sw = new Stopwatch(); 

      for (int i = 0; i < trials; ++i) 
      { 
       sw.Restart(); 
       method1(foo, bar); 
       Console.WriteLine("method1()  took " +sw.Elapsed); 

       sw.Restart(); 

       for (int j = 0; j < 100; ++j) 
        method2(foo, bar); 

       Console.WriteLine("method2()*100 took " +sw.Elapsed); 

       sw.Restart(); 

       for (int j = 0; j < 100; ++j) 
        method3(foo, bar); 

       Console.WriteLine("method3()*100 took " +sw.Elapsed); 

       Console.WriteLine(); 
      } 
     } 

     private static bool method1(int[] foo, int[] bar) 
     { 
      return foo.Any(bar.Contains); 
     } 

     private static bool method2(int[] foo, int[] bar) 
     { 
      var hashSet = new HashSet<int>(bar); 
      return foo.Any(hashSet.Contains); 
     } 

     private static bool method3(int[] foo, int[] bar) 
     { 
      return foo.Intersect(bar).Any(); 
     } 

     private static void Main() 
     { 
      new Program().run(); 
     } 
    } 
} 

Результаты (релиз сборки) на моем компьютере следующим образом. Обратите внимание, что я побежал method2() и method3() 100 раз каждый, потому что они намного быстрее, чем method1():

method1()  took 00:00:12.2781951 
method2()*100 took 00:00:00.4920760 
method3()*100 took 00:00:00.7045298 

method1()  took 00:00:11.9267980 
method2()*100 took 00:00:00.4688330 
method3()*100 took 00:00:00.6886865 

method1()  took 00:00:11.8959856 
method2()*100 took 00:00:00.4736563 
method3()*100 took 00:00:00.6875508 

method1()  took 00:00:11.9083229 
method2()*100 took 00:00:00.4572404 
method3()*100 took 00:00:00.6838919