A veces, los problemas de rendimiento de las aplicaciones, o determinadas funcionalidades de ellas, vienen derivados del uso de estructuras incorrectas para almacenar los datos, ya sea en memoria, base de datos o en cualquier tipo de almacén.
En este post vamos a centrarnos en un caso específico que me he encontrado demasiadas veces en código real: el uso indebido del tipo List<T>
cuando sólo nos interesa buscar en esta colección por una propiedad que actúa como identificador único del objeto T
.
Imaginad que tenemos una colección de objetos Friend
y queremos buscar aquél (en singular) cuyo identificador sea, por ejemplo, 1906. Esto podríamos implementarlo de la siguiente manera:
List<Friend> friends = ... // Obtenemos una colección de amigos desde donde sea
var friend = friends.FirstOfDefault(f=> f.Id == 1906);
El código es válido y funciona, pero tiene un problemilla que se pondrá especialmente de manifiesto si el número de elementos de la colección es alto, y más aún si realizamos continuamente búsquedas sobre la misma colección: el método FirstOrDefault()
, en el por de los casos, tendrá que recorrer obligatoriamente los N
elementos hasta encontrar el ítem que buscamos o retornar un nulo para indicar que no fue posible localizarlo. Y obviamente, el tiempo necesario para esto será proporcional al número de elementos, un O(N) en toda regla.
Por esta razón, si tenemos una lista de objetos a los que queremos acceder mediante una clave que los identifica de forma única, la estructura de datos deberíamos usar normalmente será un diccionario Dictionary<TKey, TItem>
, donde TKey
es el tipo de la clave de búsqueda y TItem
el tipo de objetos a guardar. Esta clase utiliza un algoritmo que asegura que el tiempo de respuesta será constante independientemente del número de elementos (O(1)), por lo que las consultas serán, la mayoría de veces, mucho más rápidas y eficientes.
Dictionary<int, Friend> friends = ... // Cargar el diccionario de amigos de donde sea
friends.TryGet(friends, out var friend);
Y para demostrarlo, nada como el amigo BenchmarkDotNet. Vamos a utilizarlo para realizar un becnhmarking probando la búsqueda por identificador de un elemento existente en:
- un lista
List<Friend>
deN
elementos, usando LINQ, - una lista
List<Friend>
deN
elementos, usando el buclefor
de toda la vida, - un diccionario
Dictionary<int, Friend>
deN
elementos
El código básico de las pruebas es el siguiente:
BenchmarkRunner.Run<ListVsDictBenchmarks>(); // Go!
public record Friend(int Id, string Name);
public class ListVsDictBenchmarks
{
static int N = 10; // Items de la colección
static int IdToFind = N / 2; // Identificador a buscar
static List<Friend> FriendList = Enumerable.Range(0, N)
.Select(id => new Friend(id, "Friend #" + id))
.ToList();
static Dictionary<int, Friend> FriendDict =
FriendList.ToDictionary(f => f.Id, f => f);
[Benchmark]
public Friend? FindInDictionary()
{
FriendDict.TryGetValue(IdToFind, out var friend);
return friend;
}
[Benchmark]
public Friend? FindInListUsingLinq()
{
return FriendList.FirstOrDefault(item => item.Id == IdToFind);
}
[Benchmark]
public Friend? FindInListUsingFor()
{
for (var i = 0; i < N; i++)
{
if (FriendList[i].Id == IdToFind)
return FriendList[i];
}
return null;
}
}
Primero, probamos con N=10
, para comprobar el rendimiento cuando el número de elementos es muy pequeño:
Method | Mean | Error | StdDev |
---|---|---|---|
FindInDictionary | 3.485 ns | 0.0470 ns | 0.0440 ns |
FindInListUsingFor | 7.497 ns | 0.0258 ns | 0.0229 ns |
FindInListUsingLinq | 66.175 ns | 0.2474 ns | 0.2193 ns |
En este caso, con tan solo diez elementos, ya vemos que el diccionario es el doble de rápido que la búsqueda en la lista mediante el bucle for
y veinte veces más rápido que la alternativa usando LINQ. Eso sí, tened en cuenta que hablamos de nanosegundos, por lo que aunque la diferencia sea grande, hay muchos escenarios en los que sería imperceptible para el usuario.
Vamos a subir la apuesta haciendo N=5000
. En este caso, el resultado pone de manifiesto claramente la superioridad del diccionario respecto a las listas para este tipo de búsquedas por identificador:
Method | Mean | Error | StdDev |
---|---|---|---|
FindInDictionary | 3.478 ns | 0.0317 ns | 0.0265 ns |
FindInListUsingFor | 3,245.731 ns | 33.0878 ns | 30.9504 ns |
FindInListUsingLinq | 21,278.690 ns | 115.3831 ns | 102.2841 ns |
Es decir, con 5.000 elementos, la búsqueda directa en el diccionario es 1.000 veces más rápido que usar el for
sobre la lista y siete mil veces mejor que el uso de LINQ.
Una última prueba: subiremos a 50.000 elementos, y esta vez buscaremos elementos que no existan en el diccionario para ponernos en el peor de los casos. El resultado se muestra en la siguiente tabla:
Method | Mean | Error | StdDev |
---|---|---|---|
FindInDictionary | 2.939 ns | 0.0476 ns | 0.0422 ns |
FindInListUsingFor | 141,258.966 ns | 2,544.6197 ns | 4,036.0365 ns |
FindInListUsingLinq | 483,093.548 ns | 7,052.4853 ns | 6,596.8991 ns |
¡Uau! Buscando sobre 50.000 elementos, en el peor de los casos el diccionario llegó a ser 50.000 veces más rápido que el bucle for
en la lista, y sobre 150.000 veces más rápido que el uso de LINQ. Vemos además que la promesa del O(1) es cierta: da igual cuántos elementos tengamos en la colección, el rendimiento va a ser muy similar.
Bueno, creo que a la vista de estas pruebas creo que, cuando queramos almacenar en memoria datos para buscarlos luego usando un identificador único, el uso un diccionario está más que justificado.
Fijaos que esto no quita que podamos contar o recorrer secuencialmente los elementos o las claves, por lo que el uso del diccionario no nos privará de ninguna de las ventajas de usar un tipo List<T>
. Para comprobar que no existe ningún tipo de penalización por realizar este tipo de operaciones, añadimos un par de benchmarks que recorren la lista completa en ambos casos:
[Benchmark]
public double GetAverageFromDictionary()
{
return FriendDict.Values.Average(f => f.Id);
}
[Benchmark]
public double GetAverageFromList()
{
return FriendList.Average(f => f.Id);
}
Realizando la prueba para 5.000 elementos, el resultado no deja lugar a dudas: podríamos utilizar la propiedad Values
del objeto diccionario para acceder a los valores de forma secuencial, sin apenas penalización:
Method | Mean | Error | StdDev |
---|---|---|---|
GetAverageFromDictionary | 44.69 us | 0.522 us | 0.462 us |
GetAverageFromList | 41.90 us | 0.372 us | 0.348 us |
Por otra parte, también es interesante saber qué diferencia de rendimiento existe a la hora de insertar elementos en la colección, porque, de forma intuitiva, podría pensarse que las estructuras internas y algoritmos de hashing del diccionario, así como la detección de duplicados, podría penalizar las inserciones. De nuevo, lo llevamos a BenchmarkDotNet, a ver qué opina:
[Benchmark]
public void AddToDictionary()
{
var d = new Dictionary<int, Friend>();
for (int i = 0; i < N; i++)
{
d.TryAdd(i, new Friend(i, "Friend #" + i));
}
}
[Benchmark]
public void AddToList()
{
var l = new List<Friend>();
for (int i = 0; i < N; i++)
{
l.Add(new Friend(i, "Friend #" + i));
}
}
Ejecutamos la prueba insertando 10.000 elementos y, a la vista de los resultados, resulta que la inserción de ítems en el diccionario es incluso más eficiente que en la lista
Method | Mean | Error | StdDev |
---|---|---|---|
AddToDictionary | 689.0 us | 6.69 us | 8.94 us |
AddToList | 1,579.3 us | 28.09 us | 39.37 us |
Por tanto, si tenemos una colección de elementos en la que queremos buscar repetidamente valor por algún tipo de identificador único, debemos considerar seriamente el uso de un diccionario sobre una lista.
Publicado en Variable not found.
2 Comentarios:
Felicidades por el blog. Soy uno de esos lectores que te sigue en silencio desde hace años y hoy he decidido dar el paso 😉
Sobre el post, estoy de acuerdo con lo que dices. List no deberia usarse para eso. Pero hay veces en las que tenemos que acceder a los elementos secuencialmente o usando claves distintas, y supongo que ahí nos puede la pereza.
Un saludo y a seguir así
Hola, Antonio! Un placer tenerte por aquí, y que te hayas decidido a comentar algo :D
Respecto a lo que comentas, totalmente de acuerdo, la pereza nos puede muchas veces. Pero concretamente con los puntos que comentas:
- usar un diccionario no quita que puedas acceder secuencialmente a los elementos (en el post lo vemos)
- si necesitas usar más de una clave, tienes alternativas como usar composición para gestionar más de un diccionario al mismo tiempo. Creo que escribiré algo al respecto una de estas semanas.
Saludos y, nuevo, muchas gracias!
Enviar un nuevo comentario