benchmarkdotnet - c# vs c++ benchmark
Benchmarking de rendimiento de contiene, existe y cualquier (3)
He estado buscando un benchmarking de rendimiento entre los métodos Contains , Exists y Any disponibles en la List<T> . Quería descubrir esto solo por curiosidad ya que siempre estaba confundido entre estos. Muchas preguntas sobre SO describen definiciones de estos métodos, tales como:
- Anillo LINQ: Any () versus Contains () para enormes colecciones
- Linq. Cualquier VS. Exists - ¿Cuál es la diferencia?
- Métodos de extensión LINQ - Cualquier () vs. Dónde () versus Existe ()
Así que decidí hacerlo yo mismo. Lo estoy agregando como una respuesta. Cualquier idea más sobre los resultados es bienvenida. También hice este benchmarking para arreglos para ver los resultados
La forma más rápida es usar un HashSet . El Contains para un HashSet es O (1).
HashSet<int> código y agregué un punto de referencia para HashSet<int> El costo de rendimiento de HashSet<int> set = new HashSet<int>(list); es casi cero.
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);
}
RESULTADOS
***************************************
***** 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
Vale la pena mencionar que esta comparación es un poco injusta ya que la clase Array no posee el método Contains() , utiliza un método de extensión para IEnumerable<T> través de un Enumerator secuencial, por lo tanto no está optimizado para las instancias Array ; por otro lado, HashSet<T> tiene su propia implementación completamente optimizada para todos los tamaños.
Para comparar de manera justa, puede usar el método estático int Array.IndexOf() que se implementa para las instancias de Array aunque use un ciclo for algo más eficiente que un Enumerator .
Habiendo dicho eso, el rendimiento de HashSet<T>.Contains() es similar al Array.IndexOf() para conjuntos pequeños de, diría, hasta 5 elementos y mucho más eficiente para conjuntos grandes.
De acuerdo con la documentación:
List.Exists (método del objeto)
Determina si la Lista (T) contiene elementos que coinciden con las condiciones definidas por el predicado especificado.
IEnumerable.Any (Método de extensión)
Determina si algún elemento de una secuencia satisface una condición.
List.Contains (método del objeto)
Determina si un elemento está en la lista.
Benchmarking:
CÓDIGO:
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);
}
RESULTADOS
***************************************
***** 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