En el anterior post veíamos qué tipos de colección exponer a través de APIs públicas y lo analizábamos desde un punto de vista bastante funcional: operaciones permitidas, invariantes a mantener y flexibilidad a la hora de evolucionar el diseño.

En las conclusiones del post decía que había que tener en cuenta también la eficiencia que presentaban los distintos tipos de colección para las distintas operaciones que se podían realizar con ella, porque elegir correctamente el tipo de colección podía tener un gran impacto en el rendimiento.

En este post vamos a centrarnos en ver las características, desde el punto de vista de eficiencia, de algunos de los tipos de colecciones más comunes en .NET.

Mini introducción a complejidad computacional

Para poder analizar el rendimiento de un algoritmo (y el acceso a una estructura de datos no es más que eso, un algoritmo concreto que se ejecuta sobre esa estructura), se suele utilizar el concepto de compejidad computacional. Este tema daría para muchos posts por si sólo, pero vamos a ver lo justo para poder entender el resto del post.

La complejidad algorítmica «mide» la eficiencia de un algoritmo con respecto al tamaño de los datos de entrada. Lo más habitual es medir el consumo de memoria o el tiempo que tarda en ejecutarse. En nuestro caso nos centraremos en el tiempo que tarda en ejecutarse.

En realidad, no podemos predecir exactamente el tiempo que tardará en ejecutarse un algoritmo porque depende de muchos factores externos, pero sí podemos llegar a saber cómo crece el tiempo de ejecución dependiendo del tamaño de los datos de entrada.

Se suele representar con la notación O(expresión), donde expresión es una expresión matemática en función del tamaño de datos de entrada (que suele denotarse como n). Por ejemplo:

• O(1): representa un algoritmo que no depende del tamaño de los datos de entrada. Su tiempo de ejecución es constante independientemente de que le pasemos 10 valores o 10 millones de valores.
• O(n): representa un algoritmo cuyo tiempo de ejecución crece linealmente con respecto al tamaño de la entrada. Si le pasamos 1000 valores tardará 100 veces más si le pasamos 10.
• O(n²): representa un algoritmo cuyo tiempo de ejecución crece cuadráticamente con respecto al tamaño de la entrada. Si le pasamos 1000 valores tardará 10000 veces más si le pasamos 10.

Como ya he dicho, es todo un poco más complicado que esto y entran en juego distintos escenarios (caso peor, caso mejor, promedio, coste amortizado), pero con lo que tenemos nos sirve por ahora.

Está claro que cuanto más despacio crezca la expresión que aparece al lado de la O, mejor se comportará el algoritmo cuando crezca el volumen de datos.

Aprovechar las caracteríscas de cada colección

La complejidad de las operaciones depende de la forma en que estén implementadas, así que me voy a centrar en las implementación de algunas estructuras de datos que existen en System.Collections.Generic. En la MSDN puedes encontrar detalles sobre el coste de cada operación de cada estructura de datos en distintos escenarios.

No todas las colecciones exponen las mismas operaciones, por ejemplo una lista no permite buscar por clave (aunque sí por índice) y un conjunto no permite buscar ni por una cosa ni por otra. Sin embargo, gracias a LINQ es muy fácil realizar casi cualquier cosa con casi cualquier colección, pero esa facilidad puede hacer que no pensemos a la hora de elegir la colección y luego tengamos problemas de rendimiento.

Vamos a ver las características de algunas de las colecciones más habituales.

List<T>

En una lista es muy rápido, O(1), acceder a un elemento a partir de su posición y añadir o eliminar elementos al final.

A cambio, si queremos buscar un elemento o insertar o eliminar un elemento en medio de la lista, el coste se incrementa a O(n).

Dictionary<TKey, TValue>

Un diccionario permite insertar elementos en tiempo constante O(1) y recuperarlos o eliminarlos a partir de la clave también en tiempo constante.

Viendo esto, parecería que siempre es mejor usar un diccionario que una lista, pero hay que tener en cuenta que el comportamiento no es el mismo, y si necesitamos mantener el orden relativo entre los elementos, un diccionario no nos servirá.

Otras colecciones

Hay muchos más tipos de estructuras de datos con sus peculiaridades y sus casos de uso concretos.

Por ejemplo, una lista ordenada (SortedList) nos permite buscar en ella elementos con coste logarítmico, O(log n), o recorrer sus elementos por orden en tiempo lineal O(n), a costa de tener peor rendimiento al insertar o eliminar elementos.

Las lista enlazadas nos permiten concatenar listas o insertar/eliminar elementos en cualquier posición de la lista en tiempo constante, O(1), pero si queremos acceder al elemento i-ésimo tendremos un coste O(N).

Listas vs Diccionarios

Pese a la disparidad de estructuras de datos existentes, en la vida real muchas veces la elección se reduce a listas frente a diccionarios.

A la hora de elegir entre uno u otro, piensa un momento (30 segundos, no hace falta más) en el uso que le vas a dar y el coste computacional que tienen las operaciones que vas a realizar sobre él. Ya he dicho que con LINQ es fácil hacer lo que quieras con cualquier colección e incluso convertir de una a otra, pero el rendimiento no es el mismo.

Si tienes un diccionary y acabas recorriéndolo siempre con un foreach, probablemente lo que necesitas es una lista. Si tienes una lista y estas continuamente haciendo un FirstOrDefault o SingleOrDefault para localizar elementos concretos, seguramente te vendría mucho mejor usar un diccionario.

Si vas a realizar un cálculo intensivo sobre un conjunto grande de datos, a veces compensa asumir el coste de convertir una estructura de datos en otra para que luego el grueso del algoritmo se ejecute sobre una estructura de datos con mejor rendimiento para ese caso de uso, como veíamos en este post.

Cuidado con el mundo real

Aunque el análisis de algoritmos es importante, no hay que olvidar que esto es un cálculo teórico. En el mundo real hay más factores a tener en cuenta, como es la forma en que usa la memoria una estructura de datos concreta, o la forma en se almacena en disco.

Si los datos son tan grandes como para tener que cargarlos desde disco, puede ser mejor usar una estructura de datos «un poco peor» pero que los almacene seguidos en disco (por ejemplo un B-Tree), que una estructura de datos que obligue a realizar lecturas aleatorias por distintas partes de disco.

Si necesitas llegar a un nivel extremo de microoptimización (algo sumamente extraño), puede que te interese aprovechar la localidad espacial en memoria para evitar fallos de cache y que la CPU tenga que ir al a RAM.

La mayoría de las veces estos factores no van a ser críticos, pero no está mal saberlo por si acaso.

Conclusiones

Después de estos dos posts, parece que elegir qué tipo de colección utilizar es una cosa complicadísima con mil factores a tener en cuenta, pero la realidad es que una vez que has pensado sobre esto una vez, acabas interiorizando bastante la forma de elegir una colección y no tienes que darle muchas vueltas.

No obstante, es bueno de vez en cuando replantearse la forma en que uno hace las cosas y entender por qué se deben o no hacer así.