Производительность Бенчмаркинг содержит, существует и любой

Question

Я искал сравнительный анализ производительности между Contains, Exists и Any методами, доступными в List<T>. Я хотел найти это только из любопытства, так как меня всегда путали между ними. Многие вопросы, касающиеся SO описанных определений этих методов, таких как:

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()

Так что я решил сделать это сам. Я добавляю его в качестве ответа. Больше всего лучше понять результаты. Я также сделал это бенчмаркинг для массивов, чтобы увидеть результаты

Answer 1

Согласно документации:

List.Exists (метод объекта)

определяет, содержит ли List (T) элементы, которые соответствуют условий, определенных заданным предикатом.

IEnumerable.Any (метод расширения)

Определяет, удовлетворяет ли какой-либо элемент последовательности заданному условию.

List.Contains (метод объекта)

Определяет, принадлежит ли элемент в списке.

Бенчмаркинг:

КОД:

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); 
    } 

РЕЗУЛЬТАТЫ

*************************************** 
***** 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 тестовым способом является использование HashSet. Contains для HashSet - O (1).

Я принял вас код и добавил контрольную отметку для HashSet<int> Стоимость исполнения HashSet<int> set = new HashSet<int>(list); почти равна нулю.

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); 
} 

РЕЗУЛЬТАТЫ

*************************************** 
***** 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

Стоит отметить, что это сравнение немного несправедливо, так как класс Array не владеет методом Contains(), он использует метод расширения для IEnumerable<T> через последовательный Enumerator поэтому не оптимизирован для Array экземпляров; с другой стороны, HashSet<T> имеет собственную реализацию, полностью оптимизированную для всех размеров.

Для сравнения достаточно можно использовать статический метод int Array.IndexOf(), который реализуется для Array случаев, даже если он использует цикл for немного более эффективным, что в Enumerator.

Сказав, что производительность HashSet<T>.Contains() похожа на Array.IndexOf() для небольших наборов, я бы сказал, до 5 элементов и намного более эффективным для больших наборов.