c# - for - vb.net array multidimensional

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

Question

.NET tiene muchas estructuras de datos complejas. Desafortunadamente, algunos de ellos son muy 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 en cierta medida, pero en realidad nunca entran en ningún detalle real.

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

Answer 1

Estructuras de datos .NET:

Más para conversar sobre por qué ArrayList y List son realmente diferentes

Arrays

Como afirma 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 los arreglos en comparación con otras colecciones, es decir, las que has enumerado en tu título (aquí, ArrayList y List (Of T))? Comencemos con lo básico mirando Arrays.

Para comenzar, los Arrays en Microsoft .NET son "mecanismos que le permiten tratar varios elementos [relacionados con la lógica] como una sola colección" (ver artículo vinculado). Qué significa eso? Las matrices almacenan miembros individuales (elementos) secuencialmente, uno tras otro en la memoria con una dirección de inicio. 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 contrariamente a la programación de concepciones comunes, Arrays puede ser bastante complejo:

Las matrices pueden ser de una sola dimensión, multidimensionales o jadded (vale la pena leer las matrices dentadas). Las matrices en sí no son dinámicas: una vez inicializadas, una matriz de tamaño n reserva espacio suficiente para contener n cantidad de objetos. El número de elementos en la matriz no puede aumentar o disminuir. 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, la especificación de lenguaje común (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 lo "común" de los arreglos basados ​​en cero, Microsoft ha dedicado mucho tiempo a optimizar su rendimiento ; por lo tanto, las matrices de una sola dimensión y basadas en cero (SZ) son "especiales", y en realidad son la mejor implementación de una matriz (en lugar de multidimensional, etc.) porque las SZ tienen instrucciones específicas de lenguaje intermediario para manipularlas.

Los arreglos siempre se pasan por referencia (como una dirección de memoria), una pieza importante del rompecabezas de arreglos que se debe conocer. Mientras realizan la verificación de límites (arrojará un error), la verificación de límites también se puede desactivar en los arreglos.

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) a nuestra historia:

ArrayList - lista no genérica

La ArrayList (junto con List(Of T) - aunque hay algunas diferencias críticas, aquí, explicadas más adelante) - quizás sea mejor considerada como la próxima adición a las colecciones (en el sentido amplio). ArrayList se hereda de la interfaz IList (un descendiente de ''ICollection''). Las listas de arreglos, en sí mismas, son bulkier , lo que requiere más overhead , que las listas.

IList permite que la implementación trate a 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 tienen un tamaño fijo como ArrayLists (sobre Arrays) en este caso son notablemente más lentos.

Desde 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. Las ArrayLists tampoco están "escritas", 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, agregando nuevamente a sus gastos generales.

Pensamiento no confirmado: Creo que recuerdo haber leído o haber escuchado a uno de mis profesores que ArrayLists es una especie de hijo conceptual bastardo del intento de pasar de Arrays a colecciones de tipo Lista, es decir, que una vez fue una gran mejora para Arrays, Ya no son la mejor opción ya que se ha hecho 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 la memoria es lo suficientemente significativa como para que una Lista (de Int32) consumiera un 56% menos de memoria que una ArrayList que contenga el mismo tipo primitivo (8 MB vs. 19 MB en la demostración vinculada del caballero anterior: nuevamente, vinculado overhead ). 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 una List(Of T) como "... una lista de objetos fuertemente tipada a la que se puede acceder por índice". La importancia aquí es el bit "fuertemente tipado": una Lista (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 de 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 en gran escala: más de 500 elementos. Lo que es más interesante es que la documentación de MSDN dice: "Le conviene utilizar 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 (ver figura). Lista (de T) también tiene algunas funcionalidades añadidas.

Answer 2

Aquí hay algunos consejos generales para usted:

• Puede usar foreach en tipos que implementan IEnumerable . IList es esencialmente un IEnumberable con IEnumberable de Count e Item (acceso a elementos mediante un índice basado en cero). IDictionary por otra parte, significa que puede acceder a los elementos mediante un índice de cualquier hashable.

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

• Si está utilizando .NET 2.0 o superior, se recomienda que utilice homólogos genéricos 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 .

Answer 3

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

Answer 4

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

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

Answer 5

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 lectores de muchos escritores sin sincronización. Diccionario no lo hace.

Answer 6

La parte superior de mi cabeza:

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

• ArrayList - matriz que crece automáticamente. Añade más gastos generales. Se puede enumerar, probablemente más lento que un arreglo normal pero aún bastante rápido. Estos se utilizan mucho en .NET

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

• Hashtable - hashtable viejo llano. O (1) a O (n) peor de los casos. Puede enumerar las propiedades de valores y claves, y hacer pares clave / val

• Dictionary : igual que el anterior solo se escribe con fuerza mediante genéricos, como Dictionary<string, string>

• SortedList - una lista genérica ordenada. Disminuido en la inserción, ya que tiene que averiguar dónde colocar las cosas. Se 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 antigua.

Tiendo a usar List y Dictionary todo el tiempo; una vez que empiezas a usarlos con tipos genéricos, es realmente difícil volver a los estándares no genéricos.

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

Answer 7

Las colecciones genéricas se desempeñarán mejor que sus contrapartes no genéricas, especialmente cuando se repiten en muchos elementos. Esto es porque el boxeo y el unboxing ya no ocurren.

Answer 8

Primero, todas las colecciones en .NET implementan IEnumerable.

Segundo, muchas de las colecciones son duplicadas porque los genéricos se agregaron 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.
• Diccionario 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 determinado.

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

Por lo tanto, las implementaciones de IDictionary (aquellas 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 soporta operaciones de conjunto.

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

Answer 9

Se explican bastante bien en intellisense. Sólo tienes que escribir System.Collections. o System.Collections.Generics (preferido) y obtendrá una lista y una breve descripción de lo que está disponible.

Answer 10

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

Answer 11

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

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

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

Answer 12

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

Answer 13

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

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

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 # incorporadas, 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 según su posición dentro de la lista (también conocido como índice). La matriz de 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 puede inicializarse sin elementos o de un conjunto de valores existentes. Insertar valores en una matriz es simple siempre y cuando 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 debe expandirse. Esto lleva más tiempo porque todos los elementos existentes deben copiarse a 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 un ArrayList puede tener cualquier cantidad de objetos y de cualquier tipo. Esta estructura de datos se diseñó para simplificar los procesos de agregar nuevos elementos a una matriz. Debajo del capó, un 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 que se copian 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 ArrayList es que uno debe convertir los valores recuperados en su tipo original:

int arrayListValue = (int)myArrayList[0]

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

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

Answer 14

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

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