¿Cómo y cuándo abandonar el uso de matrices en C #?

Siempre me han dicho que agregar un elemento a una matriz sucede así:

Se crea una copia vacía de la matriz + 1elemento y luego se copian los datos de la matriz original y luego se cargan los nuevos datos para el nuevo elemento.

Si esto es cierto, entonces el uso de una matriz dentro de un escenario que requiere mucha actividad de elementos está contraindicado debido a la memoria y la utilización de la CPU, ¿correcto?

Si ese es el caso, ¿no deberías tratar de evitar usar una matriz tanto como sea posible cuando agregarás muchos elementos? ¿Deberías usar iStringMap en su lugar? Si es así, ¿qué sucede si necesita más de dos dimensiones Y necesita agregar muchas adiciones de elementos? ¿Simplemente tomas el impacto de rendimiento o hay algo más que debería usarse?

Mire la List genérica List como un reemplazo para los arreglos. Admiten la mayoría de las mismas funciones que hacen los arreglos, incluida la asignación de un tamaño de almacenamiento inicial, si así lo desea.

Esto realmente depende de lo que quieres decir con “agregar”.

Si te refieres a:

 T[] array; int i; T value; ... if (i >= 0 && i < = array.Length) array[i] = value; 

Entonces, no, esto no crea una nueva matriz y, de hecho, es la forma más rápida de alterar cualquier tipo de IList en .NET.

Sin embargo, si está usando algo como ArrayList, List, Collection, etc., al llamar al método "Agregar" puede crear una nueva matriz, pero son inteligentes al respecto, no solo cambian de tamaño por 1 elemento, sino que crezca geométricamente, así que si está agregando muchos valores solo de vez en cuando tendrá que asignar una nueva matriz. Incluso entonces, puedes usar la propiedad "Capacidad" para forzarla a crecer de list.Capacity += numberOfAddedElements , si sabes cuántos elementos estás agregando ( list.Capacity += numberOfAddedElements )

En general, prefiero evitar el uso de matrices. Solo usa Lista . Utiliza una matriz de tamaño dynamic internamente y es lo suficientemente rápida para la mayoría de los usos. Si está utilizando matrices multidimensionales, use Lista >> si es necesario. No es mucho peor en términos de memoria, y es mucho más sencillo agregar elementos.

Si está en el 0.1% de uso que requiere una velocidad extrema, asegúrese de que su acceso a la lista sea el problema antes de intentar optimizarlo.

Si va a agregar / eliminar elementos mucho, solo use una Lista. Si es multidimensional, siempre puedes usar una Lista > o algo así.

Por otro lado, las listas son menos eficientes que las matrices si lo que más haces es atravesar la lista, porque todas las matrices están en un solo lugar en la memoria caché de la CPU, donde los objetos de una lista se encuentran dispersos por todo el lugar.

Si desea utilizar una matriz para una lectura eficiente pero va a “agregar” elementos con frecuencia, tiene dos opciones principales:

1) Genérelo como una Lista (o Lista de Listas) y luego use ToArray () para convertirlo en una estructura de matriz eficiente.

2) Asigne la matriz para que sea más grande de lo que necesita, luego coloque los objetos en las celdas asignadas previamente. Si termina necesitando incluso más elementos de los que preasignado, puede simplemente reasignar la matriz cuando se llena, duplicando el tamaño cada vez. Esto le da a O (log n) el rendimiento de cambio de tamaño en lugar de O (n) como lo sería con una matriz de reasignación una vez por adición. Tenga en cuenta que esto es más o menos cómo funciona StringBuilder, lo que le brinda una forma más rápida de agregar continuamente a una cadena.

Cuándo abandonar el uso de matrices.

  1. En primer lugar, cuando la semántica de las matrices no coincida con su intención : ¿Necesita una colección en crecimiento dynamic? ¿Un conjunto que no permite duplicados? ¿Una colección que tiene que permanecer inmutable? Evita matrices en todos los casos. Eso es el 99% de los casos. Sólo indicando el punto básico obvio.

  2. En segundo lugar, cuando no está codificando la crítica absoluta del rendimiento , eso es aproximadamente el 95% de los casos. Las matrices funcionan mejor marginalmente , especialmente en iteración . Casi siempre nunca importa.

  3. Cuando no te obliga un argumento con la palabra clave params , solo deseaba que params aceptara cualquier IEnumerable o incluso mejor, una construcción de lenguaje para denotar una secuencia (y no un tipo de marco).

  4. Cuando no está escribiendo código legado, o está tratando con interoperabilidad

En resumen, es muy raro que realmente necesite una matriz. Añadiré en cuanto a por qué uno puede evitarlo?

  1. La mayor razón para evitar arreglos imo es conceptual. Las matrices están más cerca de la implementación y más lejos de la abstracción. Las matrices transmiten más cómo se hace que lo que se hace, lo que va en contra del espíritu de los lenguajes de alto nivel. Eso no es sorprendente, considerando que los arreglos están más cerca del metal, son de un tipo especial (aunque el arreglo interno es una clase). No es pedagógico, pero las matrices realmente se traducen a un significado semántico muy raramente requerido. La semántica más útil y frecuente es la de una colección con entradas, conjuntos con elementos distintos, mapas de valores clave, etc., con cualquier combinación de variantes añadibles, de solo lectura, inmutables, que respeten el orden. Piense en esto, es posible que desee una colección agregable, o una colección de solo lectura con elementos predefinidos sin más modificaciones, pero con qué frecuencia su lógica parece “Quiero una colección agregable dinámicamente pero solo un número fijo de ellos y deberían ser modificables también “? Muy raro diría yo.

  2. Array fue diseñado durante la era pre-generica e imita la genérica con muchos hacks de tiempo de ejecución y mostrará sus rarezas aquí y allá. Algunas de las capturas que encontré:

    1. Covarianza rota.

       string[] strings = ... object[] objects = strings; objects[0] = 1; //compiles, but gives a runtime exception. 
    2. ¡Las matrices pueden darte referencia a una estructura! . Eso es diferente a cualquier otro lugar. Una muestra:

       struct Value { public int mutable; } var array = new[] { new Value() }; array[0].mutable = 1; //< -- compiles ! //a List[0].mutable = 1; doesnt compile since editing a copy makes no sense print array[0].mutable // 1, expected or unexpected? confusing surely 
    3. Los métodos implementados en tiempo de ejecución como ICollection.Contains pueden ser diferentes para las estructuras y las clases . No es un gran problema, pero si olvida anular los Equals no generics correctamente para los tipos de referencia que esperan que la colección genérica busque los Equals generics , obtendrá resultados incorrectos.

       public class Class : IEquatable { public bool Equals(Class other) { Console.WriteLine("generic"); return true; } public override bool Equals(object obj) { Console.WriteLine("non generic"); return true; } } public struct Struct : IEquatable { public bool Equals(Struct other) { Console.WriteLine("generic"); return true; } public override bool Equals(object obj) { Console.WriteLine("non generic"); return true; } } class[].Contains(test); //prints "non generic" struct[].Contains(test); //prints "generic" 
    4. La propiedad Length y el indexador [] en T[] parecen ser propiedades normales a las que se puede acceder a través de la reflexión (lo que debería implicar algo de magia), pero cuando se trata de árboles de expresión, hay que escupir exactamente el mismo código que el comstackdor. Hay métodos ArrayLength y ArrayIndex para hacerlo por separado. Una de esas preguntas aquí . Otro ejemplo:

       Expression> e = () => new[] { "a" }[0]; //e.Body.NodeType == ExpressionType.ArrayIndex Expression> e = () => new List() { "a" }[0]; //e.Body.NodeType == ExpressionType.Call; 

Cómo abandonar el uso de matrices.

El sustituto más utilizado es List que tiene una API más limpia. Pero es una estructura que crece dinámicamente, lo que significa que puede agregarse a la List al final o insertar en cualquier lugar a cualquier capacidad. No hay un sustituto para el comportamiento exacto de una matriz, pero la mayoría de las personas usan matrices como una colección de solo lectura en la que no se puede agregar nada a su final. Un sustituto es ReadOnlyCollection . Llevo este método de extensión:

 public ReadOnlyCollection ToReadOnlyCollection(IEnumerable source) { return source.ToList().AsReadOnly(); } 

Cuando se cambia el tamaño de la matriz, se debe asignar una nueva matriz y se debe copiar el contenido. Si solo está modificando el contenido de la matriz, es solo una asignación de memoria.

Por lo tanto, no debe usar matrices cuando no conoce el tamaño de la matriz, o es probable que el tamaño cambie. Sin embargo, si tiene una matriz de longitud fija, son una forma fácil de recuperar elementos por índice.

ArrayList y List aumentan la matriz en más de uno cuando sea necesario (creo que es duplicando el tamaño, pero no he comprobado la fuente). En general, son la mejor opción cuando se construye una matriz de tamaño dynamic.

Cuando sus puntos de referencia indican que el cambio de tamaño de la matriz está ralentizando seriamente su aplicación (recuerde que la optimización prematura es la raíz de todo mal), puede evaluar la escritura de una clase de matriz personalizada con un comportamiento de cambio de tamaño ajustado.

Por lo general, si debe tener el MEJOR rendimiento de búsqueda indexada, es mejor crear una Lista primero y luego convertirla en una matriz, pagando así una pequeña penalización al principio, pero evitando las posteriores. Si el problema es que continuamente agregará datos nuevos y eliminará datos antiguos, entonces puede usar una ArrayList o Lista para mayor comodidad, pero tenga en cuenta que solo son Arrays de casos especiales. Cuando “crecen”, asignan una matriz completamente nueva y copian todo lo que es extremadamente lento.

ArrayList es solo una matriz que crece cuando se necesita. La adición se amortiza O (1), solo asegúrese de que el cambio de tamaño no se realice en un mal momento. Insertar es O (n) todos los elementos a la derecha deben moverse. Quitar es O (n) todos los elementos a la derecha deben moverse.

También es importante tener en cuenta que Lista no es una lista vinculada. Es solo un ArrayList typescript. La documentación de la lista indica que se desempeña mejor en la mayoría de los casos, pero no dice por qué.

Lo mejor que puede hacer es elegir una estructura de datos que sea apropiada para su problema. Esto depende de MUCHAS cosas y, por lo tanto, es posible que desee explorar el System.Collections.Generic Namespace.

En este caso en particular, diría que si puede encontrar un buen valor clave, su mejor opción sería un diccionario . Tiene insertar y quitar que se acerca a O (1). Sin embargo, incluso con un Diccionario, debe tener cuidado de no cambiar el tamaño de su matriz interna (una operación O (n)). Es mejor darles mucho espacio especificando una capacidad inicial más grande de la que se espera que utilice en el constructor.

-Almiar

Una matriz estándar debe definirse con una longitud, que reserve toda la memoria que necesita en un bloque contiguo. Agregar un elemento a la matriz lo colocaría dentro del bloque de memoria ya reservada.

Las matrices son excelentes para pocas escrituras y muchas lecturas, en particular las de carácter iterativo; para cualquier otra cosa, utilice una de las muchas otras estructuras de datos.

Estás en lo cierto, una matriz es ideal para las búsquedas. Sin embargo, las modificaciones al tamaño de la matriz son costosas.

Debe usar un contenedor que admita ajustes de tamaño incrementales en el escenario donde está modificando el tamaño de la matriz. Podría usar un ArrayList que le permite establecer el tamaño inicial, y podría verificar continuamente el tamaño en función de la capacidad y luego boost la capacidad en una gran parte para limitar el número de tamaños.

O simplemente puedes usar una lista enlazada. Entonces, sin embargo las búsquedas son lentas …

Esta publicación en el foro puede o no serle de alguna utilidad en relación con la eficiencia de varios tipos de arreglos: arrays C # – multidimensionales frente a lexicográficos

Si creo que voy a agregar muchos artículos a la colección durante su vida útil, entonces usaré una Lista. Si sé con certeza cuál será el tamaño de la colección cuando se declare, usaré una matriz.

Otra vez que generalmente uso una matriz sobre una Lista es cuando necesito devolver una colección como propiedad de un objeto. No quiero que las personas que llaman agreguen elementos a esa colección a través de los métodos Agregar de la Lista, sino que quieran que agreguen elementos a la colección. a través de la interfaz de mi objeto. En ese caso, tomaré la Lista interna, llamaré a ToArray y devolveré una matriz.

Si va a hacer una gran cantidad de agregados y no va a hacer un acceso aleatorio (como myArray[i] ). Podría considerar el uso de una lista vinculada ( LinkedList ), ya que nunca tendrá que “crecer” como la implementación de la List . Sin embargo, tenga en cuenta que solo puede acceder realmente a los elementos en una implementación de LinkedList utilizando la IEnumerable .

Lo mejor que puedes hacer es asignar tanta memoria como necesites por adelantado si es posible. Esto evitará que .NET tenga que hacer llamadas adicionales para obtener memoria en el montón. Si falla, entonces tiene sentido asignar en partes de cinco o cualquier número que tenga sentido para su aplicación.

Esta es una regla que puedes aplicar a cualquier cosa realmente.