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

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

¿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é hay de 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 y la velocidad de la memoria (notación Big-O).

La parte superior de mi cabeza:

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

  • ArrayList : matriz en crecimiento automático. Agrega más sobrecarga Puede enum., 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 generics, por lo que puede tener una matriz fuertemente tipada, por ejemplo, List . Aparte de eso, actúa muy parecido a ArrayList

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

  • Dictionary : el mismo que el anterior solo está fuertemente tipado a través de los generics, como Dictionary

  • SortedList : una lista genérica ordenada. Se ralentizó la inserción ya que tiene que descubrir 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 simple lista anterior.

Tiendo a usar List y Dictionary todo el tiempo; una vez que empiezas a usarlos fuertemente tipados con generics, es realmente difícil volver a los que no son generics estándar.

También hay muchas otras estructuras de datos: KeyValuePair que puedes usar para hacer algunas cosas interesantes, hay SortedDictionary que también puede ser útil.

Si es posible, use generics. 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 generics 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.
  • El diccionario es una implementación genérica de Hashtable

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

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 IDictionary (aquellas que soportan KeyValuePairs) son: * Hashtable * Dictionary * SortedList * SortedDictionary

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

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

Aquí hay algunos consejos generales para usted:

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

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

  • Si usa .NET 2.0 o superior, se recomienda que use contrapartes genéricas de los tipos mencionados.

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

  • Las estructuras de datos .NET se encuentran en el espacio de nombres System.Collections . Hay bibliotecas de tipos como PowerCollections que ofrecen estructuras de datos adicionales.

  • Para obtener un conocimiento profundo de las estructuras de datos, consulte recursos como CLRS .

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

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

Estructuras de datos .NET

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

Arrays

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” sobre 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, las matrices en Microsoft .NET son “mecanismos que le permiten tratar varios elementos [relacionados lógicamente] como una única colección” (consulte el artículo vinculado). Qué significa eso? Las matrices almacenan miembros individuales (elementos) secuencialmente, uno después de otro en la memoria con una dirección de inicio. Al usar la matriz, podemos acceder fácilmente a los elementos almacenados secuencialmente comenzando en esa dirección.

Más allá de eso y contrario a la progtwigción de 101 conceptos comunes, Arrays realmente puede ser bastante complejo:

Las matrices pueden ser de una sola dimensión, multidimensionales o jadded (vale la pena leer las matrices irregulares). Las matrices en sí no son dinámicas: una vez inicializado, una matriz de n tamaño reserva suficiente espacio para contener n cantidad de objetos. La cantidad 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 que contenga 0s). La dirección de este bloque se devuelve a _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 “regularidad” de las matrices basadas 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 de lenguaje intermediario específicas para manipularlas.

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

Una vez más, el mayor obstáculo para las matrices es que no son redimensionables. Tienen una capacidad “fija”. Presentamos ArrayList y List (Of T) en nuestra historia:

ArrayList – lista no genérica

ArrayList (junto con List(Of T) – aunque hay algunas diferencias críticas, aquí, explicadas más adelante) – quizás se considere mejor como la próxima adición a las colecciones (en el sentido amplio). ArrayList hereda de la interfaz IList (un descendiente de ‘ICollection’). ArrayLists, ellos mismos, son más voluminosos , requiriendo más sobrecarga , que las Listas.

IList permite que la implementación trate ArrayLists como listas de tamaño fijo (como Arrays); sin embargo, más allá de la funcionalidad adicional añadida por ArrayLists, no existen ventajas reales al usar ArrayLists que son de tamaño fijo ya que ArrayLists (sobre Arrays) en este caso son marcadamente más lentas.

Según mi lectura, ArrayLists no puede ser irregular: “No se admite el uso de matrices multidimensionales como elementos …”. Nuevamente, otro clavo en el ataúd de ArrayLists. ArrayLists tampoco se “mecanografían”, 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, añadiendo de nuevo a su sobrecarga.

Pensamiento sin fundamento: creo recordar haber leído o haber escuchado de uno de mis profesores que ArrayLists es una especie de hijo conceptual bastardo del bash de pasar de Arrays a List-type Collections, es decir, una vez que fue una gran mejora para Array, ya no son la mejor opción, ya que se ha avanzado más con respecto a las colecciones

List (Of 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 enlazada del caballero anterior: de nuevo, vinculada aquí ) 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 de primitiva 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 una 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’ tipos y almacena los objetos como su tipo. Por lo tanto, un Int32 se almacena como un Int32 y no como un tipo de Object . 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 utilizar la implementación específica de tipo de la clase List (Of T) en lugar de usar la clase ArrayList …”

Básicamente, List (Of T) es ArrayList, pero es mejor. Es el “equivalente genérico” de ArrayList. Al igual que ArrayList, no está garantizado que se clasifique hasta que esté ordenado (figura). List (Of T) también tiene alguna funcionalidad adicional.

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

Las tablas hash / Diccionarios tienen un rendimiento O (1), lo que significa que el rendimiento no es una función del tamaño. Eso es importante saber

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

Las colecciones genéricas tendrán un mejor rendimiento que sus contrapartes no genéricas, especialmente al iterar a través de muchos elementos. Esto se debe a que el boxeo y el desempaquetado ya no ocurren.

Una nota importante acerca de Hashtable vs Dictionary para la ingeniería de trading sistemática de alta frecuencia: Tema de seguridad de subprocesos

Hashtable es seguro para subprocesos para ser utilizado por múltiples hilos. Los miembros estáticos del diccionario son seguros para subprocesos, pero no se garantiza que los miembros de instancias sean así.

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

En realidad, creo que MSDN ayuda a dar respuestas bastante buenas a todas estas preguntas. Solo busca colecciones .NET.

Existen diferencias sutiles y no tan sutiles entre las colecciones genéricas y no genéricas. Simplemente usan diferentes estructuras de datos subyacentes. Por ejemplo, Hashtable garantiza one-writer-many-readers sin sincronización. Diccionario no.

La mayoría de las estructuras y colecciones de datos C # populares

  • Formación
  • Lista de arreglo
  • Lista
  • Lista enlazada
  • Diccionario
  • HashSet
  • Astackr
  • 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 estructuras de datos más básicas. Elegir la estructura de datos correcta para usar es parte de escribir un progtwig bien estructurado y eficiente.

En este artículo voy a repasar las estructuras de datos C # integradas, incluidas las nuevas que se presentan en C # .NET 3.5. Tenga en cuenta que muchas de estas estructuras de datos se aplican a otros lenguajes de progtwigció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 índice). AC # array 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 se puede ver en el ejemplo anterior, se puede inicializar una matriz sin elementos o desde un conjunto de valores existentes. Insertar valores en una matriz es simple, siempre y cuando quepan. La operación se vuelve costosa cuando hay más elementos que el tamaño de la matriz, en cuyo punto la matriz necesita expandirse. Esto lleva más tiempo porque todos los elementos existentes deben copiarse en la matriz nueva y más grande.

Lista de arreglo

La estructura de datos de C #, ArrayList, es una matriz dinámica. Lo que eso significa es que una 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 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 elementos copiados 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 a su tipo original:

 int arrayListValue = (int)myArrayList[0] 

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

  • C # Data Structures
  • Colecciones y estructuras de datos
  • Lista vs IEnumerable vs IQueryable vs ICollection vs IDictionary
  • System.Collections.Generic Namespace
  • Espacio de nombres System.Collections