Estructuras de datos .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary: ¿velocidad, memoria y cuándo usar cada uno?

.NET tiene muchas estructuras de datos complejas. Desafortunadamente, algunos de ellos son bastante similares, y no siempre estoy seguro de cuándo usar uno y cuándo usar otro. La mayoría de mis libros de C # y Visual Basic hablan de ellos hasta cierto punto, pero nunca entran en detalles reales.

¿Cuál es la diferencia entre Array, ArrayList, List, Hashtable, Dictionary, SortedList y SortedDictionary?

¿Cuáles son enumerables (IList - puede hacer bucles 'foreach')? ¿Cuáles usan pares clave / valor (IDict)?

¿Qué pasa con la huella de memoria? Velocidad de inserción? Velocidad de recuperación?

¿Hay alguna otra estructura de datos que valga la pena mencionar?

Todavía estoy buscando más detalles sobre el uso de la memoria y la velocidad (notación Big-O).

La parte superior de mi cabeza:

• Array*: representa una matriz de memoria de la vieja escuela, como un alias para una type[]matriz normal . Puede enumerar. No puede crecer automáticamente. Asumiría una velocidad de inserción y recuperación muy rápida.

• ArrayList- Crecimiento automático de matriz. Agrega más gastos generales. Puede enumerar, probablemente más lento que una matriz normal pero aún bastante rápido. Estos se usan mucho en .NET

• List- uno de mis favoritos - se puede usar con genéricos, por lo que puede tener una matriz fuertemente tipada, por ejemplo List<string>. Aparte de eso, actúa mucho comoArrayList

• Hashtable- simple tabla hash vieja. O (1) a O (n) peor de los casos. Puede enumerar el valor y las propiedades de las claves, y hacer pares clave / val

• Dictionary - Igual que el anterior solo fuertemente tipado a través de genéricos, como Dictionary<string, string>

• SortedList- Una lista genérica ordenada. Disminuyó la velocidad de inserción ya que tiene que averiguar dónde colocar las cosas. Puede enumerar, probablemente lo mismo en la recuperación, ya que no tiene que recurrir, pero la eliminación será más lenta que una lista simple.

Tiendo a usar List y Dictionarytodo el tiempo - una vez que empezar a usarlas de tipo firme con los genéricos, es realmente difícil volver a los no genéricos estándar.

También hay muchas otras estructuras de datos: hay KeyValuePairalgunas que puedes usar para hacer algunas cosas interesantes, hay otras SortedDictionaryque también pueden ser útiles.

Si es posible, use genéricos. Esto incluye:

• Lista en lugar de ArrayList
• Diccionario en lugar de HashTable

Primero, todas las colecciones en .NET implementan IEnumerable.

En segundo lugar, muchas de las colecciones son duplicados porque se agregaron genéricos en la versión 2.0 del marco.

Entonces, aunque las colecciones genéricas probablemente agreguen características, en su mayor parte:

• List es una implementación genérica de ArrayList.
• Dictionary es una implementación genérica de Hashtable

Las matrices son una colección de tamaño fijo en la que puede cambiar el valor almacenado en un índice dado.

SortedDictionary es un IDictionary que se ordena según las claves. SortedList es un IDictionary que se ordena según un IComparer requerido.

Entonces, las implementaciones de IDictionary (las que admiten KeyValuePairs) son: * Hashtable * Dictionary * SortedList * SortedDictionary

Otra colección que se agregó en .NET 3.5 es el Hashset. Es una colección que admite operaciones de conjuntos.

Además, LinkedList es una implementación estándar de lista enlazada (la Lista es una lista de matriz para una recuperación más rápida).

Aquí hay algunos consejos generales para usted:

• Puede usar foreachen tipos que implementan IEnumerable. IListes esencialmente una propiedad IEnumberablecon County Item(acceso a elementos utilizando un índice basado en cero). IDictionarypor otro lado significa que puede acceder a los elementos por cualquier índice que se pueda compartir.

• Array, ArrayListy Listtodos implementan IList. Dictionary, SortedDictionaryY Hashtableponer en práctica IDictionary.

• Si está utilizando .NET 2.0 o superior, se recomienda utilizar contrapartes genéricas de los tipos mencionados.

• Para la complejidad de tiempo y espacio de varias operaciones en estos tipos, debe consultar su documentación.

• Las estructuras de datos .NET están en el System.Collectionsespacio de nombres. Hay bibliotecas de tipos como PowerCollections que ofrecen estructuras de datos adicionales.

• Para obtener una comprensión profunda de las estructuras de datos, consulte recursos como CLRS .

Estructuras de datos .NET:

Más información sobre por qué ArrayList y List son realmente diferentes

Matrices

Como dice un usuario, las matrices son la colección de la "vieja escuela" (sí, las matrices se consideran una colección, aunque no forman parte de System.Collections ). Pero, ¿qué es la "vieja escuela" acerca de las matrices en comparación con otras colecciones, es decir, las que ha enumerado en su título (aquí, ArrayList y List (Of T))? Comencemos con lo básico mirando Arrays.

Para empezar, matrices en Microsoft .NET son "mecanismos que le permiten tratar varios elementos [relacionados lógicamente] como una sola colección" (consulte el artículo vinculado). Qué significa eso? Las matrices almacenan miembros individuales (elementos) secuencialmente, uno tras otro en la memoria con una dirección inicial. Al usar la matriz, podemos acceder fácilmente a los elementos almacenados secuencialmente que comienzan en esa dirección.

Más allá de eso y contrario a la programación de 101 conceptos comunes, las matrices realmente pueden ser bastante complejas:

Las matrices pueden ser de una sola dimensión, multidimensionales o ajustadas (vale la pena leer sobre las matrices irregulares). Las matrices en sí mismas no son dinámicas: una vez inicializadas, una matriz de n tamaño reserva suficiente espacio para contener n cantidad de objetos. El número de elementos en la matriz no puede crecer o reducirse. Dim _array As Int32() = New Int32(100)reserva suficiente espacio en el bloque de memoria para que la matriz contenga 100 objetos de tipo primitivo Int32 (en este caso, la matriz se inicializa para contener 0). Se devuelve la dirección de este bloque _array.

Según el artículo, Common Language Specification (CLS) requiere que todas las matrices estén basadas en cero. Las matrices en .NET admiten matrices no basadas en cero; Sin embargo, esto es menos común. Como resultado de la "similitud" de los arreglos basados ​​en cero, Microsoft ha dedicado mucho tiempo a optimizar su rendimiento ; por lo tanto, las matrices de dimensión única, basadas en cero (SZ) son "especiales", y realmente la mejor implementación de una matriz (en oposición a las multidimensionales, etc.), porque las SZ tienen instrucciones específicas de lenguaje intermediario para manipularlas.

Las matrices siempre se pasan por referencia (como una dirección de memoria), una pieza importante del rompecabezas de la matriz para saber. Mientras realizan la verificación de límites (arrojará un error), la verificación de límites también se puede deshabilitar en las matrices.

Nuevamente, el mayor obstáculo para las matrices es que no son redimensionables. Tienen una capacidad "fija". Presentamos ArrayList y List (Of T) a nuestra historia:

ArrayList: lista no genérica

La ArrayList (junto con List(Of T), aunque hay algunas diferencias críticas, explicadas más adelante), quizás se considere mejor como la próxima adición a las colecciones (en sentido amplio). ArrayList hereda de la interfaz IList (un descendiente de 'ICollection'). Las ArrayLists, en sí mismas, son más voluminosas (requieren más gastos generales ) que las Listas.

IListpermite la implementación para tratar ArrayLists como listas de tamaño fijo (como Arrays); sin embargo, más allá de la funcionalidad adicional agregada por ArrayLists, no hay ventajas reales al usar ArrayLists que tienen un tamaño fijo ya que ArrayLists (sobre Arrays) en este caso son notablemente más lentas.

De mi lectura, ArrayLists no puede ser irregular: "El uso de matrices multidimensionales como elementos ... no es compatible". De nuevo, otro clavo en el ataúd de ArrayLists. ArrayLists tampoco se "escriben" - lo que significa que, por debajo de todo, un ArrayList es simplemente una matriz dinámica de objetos: Object[]. Esto requiere una gran cantidad de boxeo (implícito) y unboxing (explícito) al implementar ArrayLists, una vez más agregando a sus gastos generales.

Pensamiento sin fundamento: creo que recuerdo haber leído o haber escuchado de uno de mis profesores que las ArrayLists son una especie de hijo conceptual bastardo del intento de pasar de Arrays a List-type Collections, es decir, aunque una vez han sido una gran mejora para Arrays, ya no son la mejor opción, ya que se ha realizado un mayor desarrollo con respecto a las colecciones

Lista (de T): en qué se convirtió ArrayList (y esperaba ser)

La diferencia en el uso de la memoria es lo suficientemente significativa como para que una Lista (de Int32) consuma un 56% menos de memoria que una ArrayList que contiene el mismo tipo primitivo (8 MB frente a 19 MB en la demostración vinculada del caballero anterior: nuevamente, vinculado aquí ), aunque Este es un resultado compuesto por la máquina de 64 bits. Esta diferencia realmente demuestra dos cosas: primero (1), un "objeto" de tipo Int32 en caja (ArrayList) es mucho más grande que un tipo primitivo Int32 puro (Lista); segundo (2), la diferencia es exponencial como resultado del funcionamiento interno de una máquina de 64 bits.

Entonces, ¿cuál es la diferencia y qué es una Lista (de T) ? MSDN define un List(Of T)como, "... una lista fuertemente tipada de objetos a los que se puede acceder por índice". La importancia aquí es el bit "fuertemente tipado": una Lista (de T) 'reconoce' los tipos y almacena los objetos como su tipo. Entonces, an Int32se almacena como un Int32y no como un Objecttipo. Esto elimina los problemas causados ​​por el boxeo y el desempaquetado.

MSDN especifica que esta diferencia solo entra en juego cuando se almacenan tipos primitivos y no tipos de referencia. Además, la diferencia realmente ocurre a gran escala: más de 500 elementos. Lo que es más interesante es que la documentación de MSDN dice: "Es una ventaja para usted usar la implementación específica de tipo de la clase List (Of T) en lugar de usar la clase ArrayList ..."

Esencialmente, List (Of T) es ArrayList, pero mejor. Es el "equivalente genérico" de ArrayList. Al igual que ArrayList, no se garantiza que se ordene hasta que se ordene (vaya a la figura). La lista (de T) también tiene alguna funcionalidad adicional.

Simpatizo con la pregunta: también encontré (¿encontrar?) La elección desconcertante, así que me puse científicamente para ver qué estructura de datos es la más rápida (hice la prueba usando VB, pero imagino que C # sería el mismo, ya que ambos idiomas hacer lo mismo a nivel CLR). Puede ver algunos resultados de evaluación comparativa realizados por mí aquí (también hay una discusión sobre qué tipo de datos es mejor usar en qué circunstancias).

Se explican bastante bien en inteligencia. Simplemente escriba System.Collections. o System.Collections.Generics (preferido) y obtendrá una lista y una breve descripción de lo que está disponible.

Hashtables / Dictionaries son O (1) rendimiento, lo que significa que el rendimiento no es una función del tamaño. Eso es importante saberlo.

EDITAR: en la práctica, la complejidad de tiempo promedio para las búsquedas de Hashtable / Dictionary <> es O (1).

Las colecciones genéricas funcionarán mejor que sus contrapartes no genéricas, especialmente cuando se repiten muchos elementos. Esto se debe a que el boxeo y el desempaquetado ya no ocurren.

Una nota importante sobre Hashtable vs Dictionary para ingeniería de negociación sistemática de alta frecuencia: tema de seguridad de subprocesos

Hashtable es seguro para subprocesos para su uso por múltiples subprocesos. Los miembros estáticos públicos de diccionario son seguros para subprocesos, pero no se garantiza que los miembros de instancia lo sean.

Por lo tanto, Hashtable sigue siendo la opción "estándar" a este respecto.

Existen diferencias sutiles y no tan sutiles entre colecciones genéricas y no genéricas. Simplemente usan diferentes estructuras de datos subyacentes. Por ejemplo, Hashtable garantiza un escritor-muchos-lectores sin sincronización. Diccionario no.

Las estructuras y colecciones de datos de C # más populares

• Formación
• Lista de arreglo
• Lista
• Lista enlazada
• Diccionario
• HashSet
• Apilar
• Cola
• SortedList

C # .NET tiene muchas estructuras de datos diferentes, por ejemplo, una de las más comunes es una matriz. Sin embargo, C # viene con muchas más estructuras de datos básicas. Elegir la estructura de datos correcta para usar es parte de escribir un programa bien estructurado y eficiente.

En este artículo repasaré las estructuras de datos integradas de C #, incluidas las nuevas introducidas en C # .NET 3.5. Tenga en cuenta que muchas de estas estructuras de datos se aplican a otros lenguajes de programación.

Formación

La estructura de datos quizás más simple y más común es la matriz. AC # array es básicamente una lista de objetos. Sus rasgos definitorios son que todos los objetos son del mismo tipo (en la mayoría de los casos) y hay un número específico de ellos. La naturaleza de una matriz permite un acceso muy rápido a los elementos en función de su posición dentro de la lista (también conocida como el índice). La matriz AC # se define así:

[object type][] myArray = new [object type][number of elements]

Algunos ejemplos:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Como puede ver en el ejemplo anterior, una matriz se puede inicializar sin elementos o de un conjunto de valores existentes. Insertar valores en una matriz es simple siempre que encajen. La operación se vuelve costosa cuando hay más elementos que el tamaño de la matriz, momento en el cual la matriz necesita expandirse. Esto lleva más tiempo porque todos los elementos existentes deben copiarse en la nueva matriz más grande.

Lista de arreglo

La estructura de datos de C #, ArrayList, es una matriz dinámica. Lo que eso significa es que ArrayList puede tener cualquier cantidad de objetos y de cualquier tipo. Esta estructura de datos fue diseñada para simplificar los procesos de agregar nuevos elementos a una matriz. Debajo del capó, una ArrayList es una matriz cuyo tamaño se duplica cada vez que se queda sin espacio. Duplicar el tamaño de la matriz interna es una estrategia muy efectiva que reduce la cantidad de copia de elementos a largo plazo. No entraremos en la prueba de eso aquí. La estructura de datos es muy simple de usar:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

La desventaja de la estructura de datos de ArrayList es que los valores recuperados deben volver a su tipo original:

int arrayListValue = (int)myArrayList[0]

Fuentes y más información que puedes encontrar aquí :

• Estructuras de datos de C #
• Colecciones y estructuras de datos
• Lista vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Collections.Generic Namespace
• System.Collections Namespace

Encontré la sección "Elegir una colección" de Microsoft Docs en la página Colección y Estructura de datos realmente útil

Colecciones de C # y estructuras de datos: elija una colección

Y también la siguiente matriz para comparar algunas otras características