Estructuras de datos. NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Speed, memory, and when to use each?

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

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

Primero, todas las colecciones en.NET implementanerableumerable.

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

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

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

Los arrays son una colección de tamaño fijo que puede cambiar el valor almacenado en un determinado Indice.

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

Por lo tanto, las implementaciones IDictionary (las que soportan KeyValuePairs) son: * Hashtable * Diccionario * SortedList * SortedDictionary

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

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

Aquí hay algunos consejos generales para usted:

• Puede usar foreach en tipos que implementan IEnumerable. IList es esencialmente un IEnumberable con Count y Item (acceder a los elementos utilizando un índice basado en cero) propiedades. IDictionary por otro lado significa que puede acceder a los elementos por cualquier índice hashable.

• Array, ArrayList y List implementan IList. Dictionary, SortedDictionary, y Hashtable implementar IDictionary.

• Si está utilizando. NET 2.0 o superior, se recomienda que utiliza 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 espacio de nombres System.Collections. Hay bibliotecas de tipos como PowerCollections que ofrecen estructuras de datos adicionales.

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

Una buena hoja de trucos mencionando las complejidades de las estructuras de datos, algoritmos, etc.

Simpatizo con la pregunta - Yo también encontré(encontrar?) la elección desconcertante, así que me propuse científicamente ver qué estructura de datos es la más rápida (hice la prueba usando VB, pero imagino que C# sería lo mismo, ya que ambos lenguajes hacen lo mismo a nivel de CLR). Puedes ver algunos resultados de benchmarking realizados por mí aquí (también hay alguna discusión sobre qué tipo de datos es mejor usar en qué circunstancias).

Estructuras de datos. NET:

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

Arrays

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

A start, Los arrays en Microsoft.NET son, "mecanismos que le permiten tratar varios elementos [relacionados lógicamente] como una sola colección," (ver artículo vinculado). ¿Qué significa eso? Los arrays almacenan miembros individuales (elementos) secuencialmente, uno tras otro en memoria con una dirección de inicio. Mediante el uso de la matriz, podemos acceder fácilmente a los elementos almacenados secuencialmente a partir de esa dirección.

Más allá de eso y contrariamente a la programación de 101 concepciones comunes, los arrays realmente pueden ser bastante complejo:

Las matrices pueden ser de una sola dimensión, multidimensionales o jadeadas (vale la pena leer sobre las matrices dentadas). Los arrays en sí mismos no son dinámicos: una vez inicializados, un array de n tamaño reserva suficiente espacio para contener n número de objetos. El número de elementos en la matriz no puede crecer o decrecer. 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 0s). La dirección de este bloque se devuelve a _array.

De acuerdo con el artículo, Common Language Specification (CLS) requiere que todos los arrays estén basados en cero. Los arrays en. NET admiten arrays no basados en cero; sin embargo, esto es menos común. Como resultado de la "common-ness" de los arrays basados en cero, Microsoft ha pasado mucho tiempo optimizando su rendimiento; por lo tanto, los arrays de dimensión única basados en cero (SZs) son "especiales", y realmente la mejor implementación de un array (a diferencia de multidimensional, etc.)- porque los SZs tienen instrucciones específicas de lenguaje intermedio para manipularlos.

Las matrices siempre se pasan por referencia (como una dirección de memoria) - una pieza importante del rompecabezas de la Matriz a conocer. Mientras hacen la comprobación de límites (lanzará un error), la comprobación de límites también se puede desactivar en matrices.

Nuevamente, el mayor obstáculo para los arrays es que no son re-considerables. Tienen una capacidad "fija". Introducción de ArrayList y Lista (De T) a nuestra historia:

ArrayList-lista no genérica

El ArrayList (junto con List(Of T) - aunque hay algunas diferencias críticas, aquí, explicadas más adelante) - es quizás mejor pensado como la próxima adición a las colecciones (en el sentido amplio). ArrayList hereda de la interfaz IList (un descendiente de 'ICollection'). Las arraylistas, en sí mismas, son más voluminosas - requiriendo más overhead - que las Listas.

IList habilita el 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 de usar ArrayLists que son de tamaño fijo ya que ArrayLists (sobre Arrays) en este caso son marcadamente más lentas.

De mi lectura, los ArrayLists no pueden ser irregulares: "Usando arrays multidimensionales como elementos... no es compatible". De nuevo, otro clavo en el ataúd de ArrayLists. Los ArrayLists tampoco están "mecanografiados", lo que significa que, debajo de todo, una 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, de nuevo añadiendo a su sobrecarga.

Pensamiento sin fundamento: Creo que recuerdo haber leído o haber escuchado de uno de mis profesores que los arraylistas son una especie de hijo conceptual bastardo del intento de pasar de los Arrays a las Colecciones tipo Lista, es decir, mientras que una vez ha 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): Lo que ArrayList se convirtió (y esperaba ser)

La diferencia en el uso de memoria es lo suficientemente significativa como para que una Lista (De Int32) consumiera un 56% menos de memoria que una ArrayList que contiene el mismo tipo primitivo ( 8 MB vs. 19 MB en la demostración anterior de gentleman's linked: again, linked here ) - aunque este es un resultado equipo. Esta diferencia realmente demuestra dos cosas: primero (1), un "objeto" tipo Int32 en caja (ArrayList) es mucho más grande que un tipo primitivo Int32 puro (List); 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 a List(Of T) como, "... una lista fuertemente escrita de objetos a los que se puede acceder por index."La importancia aquí es el bit "fuertemente escrito": a List (Of T) 'reconoce' tipos y almacena los objetos como su tipo. Por lo tanto, un Int32 se almacena como un Int32 y no como un tipo Object. Esto elimina los problemas causados por el boxeo y unboxing.

MSDN especifica que esta diferencia solo entra en juego cuando se almacenan tipos primitivos y no tipos de referencia. También, 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 para su ventaja utilizar el tipo específico implementación de la clase List (Of T) en lugar de usar la clase ArrayList...."

Esencialmente, List(De T) es ArrayList, pero mejor. Es el "equivalente genérico" de ArrayList. Al igual que ArrayList, no se garantiza que se clasifique hasta que se clasifique (figura go). Lista (De T) también tiene algunas funcionalidades añadidas.

Están muy bien escritas en intellisense. Simplemente escriba System.Colecciones. o Sistema.Colecciones.Generics (preferido) y obtendrá una lista y una breve descripción de lo que está disponible.

Los hashtables/Diccionarios tienen un rendimiento O(1), lo que significa que el rendimiento no es una función del tamaño. Es importante saberlo.

EDIT: 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 iteran a través de muchos elementos. Esto se debe a que el boxeo y el unboxing ya no ocurren.

Una nota importante sobre Hashtable vs Dictionary for high frequency systematic trading engineering: Thread Safety Issue

La tabla hash es segura para el uso de subprocesos múltiples. Los miembros estáticos públicos del Diccionario son seguros para subprocesos, pero no se garantiza que los miembros de instancia lo sean.

Así que Hashtable sigue siendo la opción 'estándar' en este sentido.

En realidad, creo que MSDN ayuda a proporcionar respuestas bastante buenas a todas estas preguntas. Basta con buscar colecciones. NET.

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

Las Estructuras y Colecciones de datos más populares de C#

• Array
• ArrayList
• List
• LinkedList
• Diccionario
• HashSet
• Stack
• 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 C# integradas, incluidas las nuevas que se introducen en C#.NET 3.5. Tenga en cuenta que muchas de estas estructuras de datos se aplican a otros lenguajes de programación.

Array

La estructura de datos quizás más simple y común es la matriz. Una matriz de C# es básicamente una lista de objetos. Su definición los rasgos 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 basados en su posición dentro de la lista (también conocido como el índice). Un array C# 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 puede inicializarse sin elementos o a partir de un conjunto de valores existentes. Insertar valores en una matriz es simple, siempre y cuando encajar. La operación se vuelve costosa cuando hay más elementos que el tamaño de la matriz, momento en el que la matriz necesita expandirse. Esto lleva más tiempo porque todos los elementos existentes deben copiarse a la nueva matriz más grande.

ArrayList

La estructura de datos de C#, ArrayList, es una matriz dinámica. Lo que eso significa es que un 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 en matriz. Bajo el 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 vamos a entrar 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 uno debe convertir los valores recuperados en su tipo original:

int arrayListValue = (int)myArrayList[0]

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

• Estructuras de datos en C#
• Colecciones y Estructuras de Datos
• Lista de vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• Sistema.Colecciones.Espacio de nombres genérico
• Sistema.Espacio de nombres de colecciones