Benchmark delle prestazioni di Contiene, esiste e qualsiasi

Question

Sono stato alla ricerca di un'analisi comparativa delle prestazioni tra Contains, Exists e Any metodi disponibili nella List<T>. Volevo scoprirlo solo per curiosità dato che ero sempre confuso tra questi. Molte domande sulle definizioni SO descritti di questi metodi come:

1. LINQ Ring: Any() vs Contains() for Huge Collections
2. Linq .Any VS .Exists - Whats the difference?
3. LINQ extension methods - Any() vs. Where() vs. Exists()

Così ho deciso di farlo io stesso. Lo aggiungo come risposta. Qualsiasi altra visione dei risultati è molto gradita. Ho fatto anche questa analisi comparativa per le matrici di vedere i risultati

Answer 1

Secondo la documentazione:

List.Exists (metodo Object)

Determina se List (T) contiene elementi che corrispondono al condizioni definite dal predicato specificato.

IEnumerable.Any (metodo Extension)

Determina se ogni elemento di una sequenza soddisfa una condizione.

List.Contains (Metodo Object)

Determina se un elemento è nella lista.

Benchmarking:

CODICE:

static void Main(string[] args) 
    { 
     ContainsExistsAnyShort(); 

     ContainsExistsAny(); 
    } 

    private static void ContainsExistsAny() 
    { 
     Console.WriteLine("***************************************"); 
     Console.WriteLine("********* ContainsExistsAny ***********"); 
     Console.WriteLine("***************************************"); 

     List<int> list = new List<int>(6000000); 
     Random random = new Random(); 
     for (int i = 0; i < 6000000; i++) 
     { 
      list.Add(random.Next(6000000)); 
     } 
     int[] arr = list.ToArray(); 

     find(list, arr); 
    } 

    private static void ContainsExistsAnyShort() 
    { 
     Console.WriteLine("***************************************"); 
     Console.WriteLine("***** ContainsExistsAnyShortRange *****"); 
     Console.WriteLine("***************************************"); 

     List<int> list = new List<int>(2000); 
     Random random = new Random(); 
     for (int i = 0; i < 2000; i++) 
     { 
      list.Add(random.Next(6000000)); 
     } 
     int[] arr = list.ToArray(); 

     find(list, arr); 
    } 

    private static void find(List<int> list, int[] arr) 
    { 
     Random random = new Random(); 
     int[] find = new int[10000]; 
     for (int i = 0; i < 10000; i++) 
     { 
      find[i] = random.Next(6000000); 
     } 

     Stopwatch watch = Stopwatch.StartNew(); 
     for (int rpt = 0; rpt < 10000; rpt++) 
     { 
      list.Contains(find[rpt]); 
     } 
     watch.Stop(); 
     Console.WriteLine("List/Contains: {0:N0}ms", watch.ElapsedMilliseconds); 

     watch = Stopwatch.StartNew(); 
     for (int rpt = 0; rpt < 10000; rpt++) 
     { 
      list.Exists(a => a == find[rpt]); 
     } 
     watch.Stop(); 
     Console.WriteLine("List/Exists: {0:N0}ms", watch.ElapsedMilliseconds); 

     watch = Stopwatch.StartNew(); 
     for (int rpt = 0; rpt < 10000; rpt++) 
     { 
      list.Any(a => a == find[rpt]); 
     } 
     watch.Stop(); 
     Console.WriteLine("List/Any: {0:N0}ms", watch.ElapsedMilliseconds); 

     watch = Stopwatch.StartNew(); 
     for (int rpt = 0; rpt < 10000; rpt++) 
     { 
      arr.Contains(find[rpt]); 
     } 
     watch.Stop(); 
     Console.WriteLine("Array/Contains: {0:N0}ms", watch.ElapsedMilliseconds); 

     Console.WriteLine("Arrays do not have Exists"); 

     watch = Stopwatch.StartNew(); 
     for (int rpt = 0; rpt < 10000; rpt++) 
     { 
      arr.Any(a => a == find[rpt]); 
     } 
     watch.Stop(); 
     Console.WriteLine("Array/Any: {0:N0}ms", watch.ElapsedMilliseconds); 
    } 

RISULTATI

*************************************** 
***** ContainsExistsAnyShortRange ***** 
*************************************** 
List/Contains: 96ms 
List/Exists: 146ms 
List/Any: 381ms 
Array/Contains: 34ms 
Arrays do not have Exists 
Array/Any: 410ms 
*************************************** 
********* ContainsExistsAny *********** 
*************************************** 
List/Contains: 257,996ms 
List/Exists: 379,951ms 
List/Any: 884,853ms 
Array/Contains: 72,486ms 
Arrays do not have Exists 
Array/Any: 1,013,303ms 

Answer 2

FAS modo di prova è quello di utilizzare un HashSet. Il Contains per un HashSet è O (1).

Ho preso il codice e aggiunto un benchmark per HashSet<int> Il costo delle prestazioni di HashSet<int> set = new HashSet<int>(list); è quasi zero.

void Main() 
{ 
    ContainsExistsAnyShort(); 

    ContainsExistsAny(); 
} 

private static void ContainsExistsAny() 
{ 
    Console.WriteLine("***************************************"); 
    Console.WriteLine("********* ContainsExistsAny ***********"); 
    Console.WriteLine("***************************************"); 

    List<int> list = new List<int>(6000000); 
    Random random = new Random(); 
    for (int i = 0; i < 6000000; i++) 
    { 
     list.Add(random.Next(6000000)); 
    } 
    int[] arr = list.ToArray(); 
    HashSet<int> set = new HashSet<int>(list); 

    find(list, arr, set); 

} 

private static void ContainsExistsAnyShort() 
{ 
    Console.WriteLine("***************************************"); 
    Console.WriteLine("***** ContainsExistsAnyShortRange *****"); 
    Console.WriteLine("***************************************"); 

    List<int> list = new List<int>(2000); 
    Random random = new Random(); 
    for (int i = 0; i < 2000; i++) 
    { 
     list.Add(random.Next(6000000)); 
    } 
    int[] arr = list.ToArray(); 
    HashSet<int> set = new HashSet<int>(list); 

    find(list, arr, set); 

} 

private static void find(List<int> list, int[] arr, HashSet<int> set) 
{ 
    Random random = new Random(); 
    int[] find = new int[10000]; 
    for (int i = 0; i < 10000; i++) 
    { 
     find[i] = random.Next(6000000); 
    } 

    Stopwatch watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     list.Contains(find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("List/Contains: {0}ms", watch.ElapsedMilliseconds); 

    watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     list.Exists(a => a == find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("List/Exists: {0}ms", watch.ElapsedMilliseconds); 

    watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     list.Any(a => a == find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("List/Any: {0}ms", watch.ElapsedMilliseconds); 

    watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     arr.Contains(find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("Array/Contains: {0}ms", watch.ElapsedMilliseconds); 

    Console.WriteLine("Arrays do not have Exists"); 

    watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     arr.Any(a => a == find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("Array/Any: {0}ms", watch.ElapsedMilliseconds); 

    watch = Stopwatch.StartNew(); 
    for (int rpt = 0; rpt < 10000; rpt++) 
    { 
     set.Contains(find[rpt]); 
    } 
    watch.Stop(); 
    Console.WriteLine("HashSet/Contains: {0}ms", watch.ElapsedMilliseconds); 
} 

RISULTATI

*************************************** 
***** ContainsExistsAnyShortRange ***** 
*************************************** 
List/Contains: 65ms 
List/Exists: 106ms 
List/Any: 222ms 
Array/Contains: 20ms 
Arrays do not have Exists 
Array/Any: 281ms 
HashSet/Contains: 0ms 
*************************************** 
********* ContainsExistsAny *********** 
*************************************** 
List/Contains: 120522ms 
List/Exists: 250445ms 
List/Any: 653530ms 
Array/Contains: 40801ms 
Arrays do not have Exists 
Array/Any: 522371ms 
HashSet/Contains: 3ms 

Answer 3

Vale la pena ricordare che questo confronto è un po 'ingiusto poiché la classe Array non possiede il metodo Contains(), utilizza un metodo di estensione per IEnumerable<T> tramite sequenziale Enumerator quindi non ottimizzato per Array istanze; dall'altra parte, HashSet<T> ha una propria implementazione completamente ottimizzata per tutte le taglie.

Per confrontare abbastanza è possibile utilizzare il metodo statico int Array.IndexOf() che viene realizzato per Array casi anche se si utilizza un ciclo for leggermente più efficiente che un Enumerator.

Detto questo, le prestazioni di HashSet<T>.Contains() analogo al Array.IndexOf() per piccoli insiemi di, direi, fino a 5 elementi e molto più efficiente per grandi insiemi.