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

Question

Siempre han dicho que la adición de un elemento a un conjunto sucede así:

una copia vacía de la matriz + 1element se creado y luego los datos de la matriz original se copia en ella a continuación, los nuevos datos para el nuevo elemento se cargan entonces

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

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

Answer 1

Obsérvese el genérico List<T> como reemplazo de las matrices. Son compatibles con la mayoría de las cosas que hacen las matrices, incluida la asignación de un tamaño de almacenamiento inicial, si así lo desea.

Answer 2

Cuando se cambia el tamaño de la matriz, se debe asignar una nueva matriz y se deben copiar los contenidos. Si solo está modificando el contenido de la matriz, solo se trata de 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.

Answer 3

Lo mejor que puede hacer es asignar la mayor cantidad de memoria posible por adelantado. Esto evitará que .NET tenga que hacer llamadas adicionales para obtener memoria en el montón. De lo contrario, tiene sentido asignar en trozos de cinco o cualquier número tiene sentido para su aplicación.

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

Answer 4

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

Answer 5

En general, prefiero evitar el uso de la matriz. Solo use List < T>. Utiliza una matriz de tamaño dinámico internamente, y es lo suficientemente rápida para la mayoría del uso. Si está utilizando matrices multidimensionales, use la lista < lista < lista < T >>> si es necesario. No es mucho peor en términos de memoria, y es mucho más simple agregar elementos a.

Si usted está en el 0,1% del uso que requiere una velocidad extrema, asegúrese de que es su lista de accesos que son realmente el problema antes de intentar optimizarlo.

Answer 6

ArrayList y la lista crece la matriz por más de una cuando sea necesario (creo que es al duplicar el tamaño, pero no lo he comprobado la fuente). En general, son la mejor opción cuando construyes una matriz de tamaño dinámico.

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

Answer 7

Las matrices son geniales para pocas escrituras y muchas lecturas, especialmente aquellas de naturaleza iterativa; para cualquier otra cosa, use una de las muchas otras estructuras de datos.

Answer 8

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

Por otro lado, las listas son menos eficientes que las matrices si lo que estás haciendo es sobre todo que atraviesan la lista, ya que las matrices son todo en un solo lugar en la memoria caché de la CPU, donde los objetos en una lista están dispersos por todo el lugar.

Si desea utilizar una matriz para la lectura eficiente, pero que va a ser "y agregó" los elementos con frecuencia, tiene dos opciones principales:

1) generarla 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 preasignadas. Si termina necesitando aún más elementos de los que preasignó, puede 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 haría con una matriz de reasignación-una-vez-por-agregar. Tenga en cuenta que esto es más o menos cómo funciona StringBuilder, que le da una forma más rápida de agregar continuamente a una cadena.

Answer 9

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

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

O simplemente podría usar una lista vinculada. Luego, sin embargo, las búsquedas son lentas ...

Answer 10

Esto realmente depende de lo que quiere decir con "agregar".

Si se refiere 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 es en realidad la forma más rápida de alterar cualquier tipo de IList en .NET.

Si, sin embargo, está utilizando algo como ArrayList, List, Collection, etc., al llamar al método "Agregar" puede crear una nueva matriz, pero son inteligentes al respecto, no solo Cambiar el tamaño por 1 elemento, crecen geométricamente, por lo que si agrega muchos valores solo de vez en cuando tendrá que asignar una nueva matriz. Incluso entonces, puede usar la propiedad "Capacidad" para forzarlo a crecer de antemano, si sabe cuántos elementos está agregando (list.Capacity += numberOfAddedElements)

Answer 11

Esta publicación en el foro puede serle útil o no. eficiencia de varios tipos de matrices: C# arrays - multidimensional vs lexicographic

Answer 12

Si creo que voy a agregar elementos a la colección durante su vida, entonces utilizaré una lista. Si sé con certeza cuál será el tamaño de la colección cuando se declare, entonces usaré una matriz.

En otra ocasión, generalmente utilizo una matriz sobre una lista cuando necesito devolver una colección como propiedad de un objeto; no quiero que las personas que llaman agreguen 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 y llamaré a ToArray y devolveré una matriz.

Answer 13

Generalmente, si debe tener el MEJOR rendimiento de búsqueda indexada, es mejor crear primero una lista y luego convertirla en una matriz, pagando una pequeña penalización al principio pero evitando una posterior. Si el problema es que continuamente agregará datos nuevos y eliminará datos antiguos, es posible que desee utilizar una Lista de Arreglos o una Lista por conveniencia, pero tenga en cuenta que 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 es necesario. Agregar se amortiza O (1), solo tenga cuidado para asegurarse de que el cambio de tamaño no ocurra en un mal momento. El inserto es O (n) todos los elementos a la derecha se deben mover. Eliminar es O (n) todos los elementos a la derecha se deben mover.

También es importante tener en cuenta que List no es una lista vinculada. Es solo una ArrayList mecanografiada. La lista documentation tiene en cuenta que funciona 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 adecuada para su problema. Esto depende de MUCHAS cosas y, por lo tanto, es posible que desee explorar el espacio de nombres System.Collections.Generic.

En este caso en particular, diría que si puede obtener una buena clave de valor Dictionary sería su mejor opción. Tiene insertar y eliminar que se acerca a O (1). Sin embargo, incluso con un diccionario, debe tener cuidado de no dejar que cambie el tamaño de su matriz interna (una operación O (n)). Lo mejor es darles un montón de espacio al especificar una capacidad inicial más grande de lo que esperaba en el constructor.

-Rick

Answer 14

Si usted va a estar haciendo un montón de añadir, y no se va a hacer de acceso aleatorio (como myArray[i]). Podría considerar usar una lista vinculada (LinkedList<T>), porque nunca tendrá que "crecer" como la implementación List<T>. Tenga en cuenta, sin embargo, que solo puede acceder realmente a los elementos en una implementación LinkedList<T> utilizando la interfaz IEnumerable<T>.

Answer 15

Cuando a abandonar el uso de matrices

1. En primer lugar, cuando semántica de matrices dont partido con su intención - Necesidad de una colección de crecimiento dinámico? Un conjunto que no permite duplicados? ¿Una colección que debe permanecer inmutable? Evite arreglos en todos los casos. Eso es el 99% de los casos. Solo indicando el punto básico obvio.

2. En segundo lugar, cuando se está no de codificación de criticidad rendimiento absoluto - Eso es alrededor de 95% de los casos. Arrays perform better marginally, especially in iteration. Casi nunca importa.

3. Cuando estás no forzado por una discusión con params palabra clave - Ojalá params aceptado ninguna IEnumerable<T> o incluso mejor un lenguaje construirse para denotar una secuencia de (y no un tipo de marco).

4. Cuando esté no la escritura de código heredado, o tratar con interoperabilidad

En resumen, es muy raro que en realidad se necesitaría una matriz. Agregaré en cuanto a por qué uno puede evitarlo?

1. La mayor razón para evitar matrices 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 qué se hace que está en contra del espíritu de los lenguajes de alto nivel. Eso no es sorprendente, considerando que las matrices están más cerca del metal, son directamente de un tipo especial (aunque internamente la matriz es una clase). No es pedagógico, pero las matrices realmente se traducen en un significado semántico muy raramente requerido. La semántica más útil y frecuente es la de una colección con cualquier entrada, conjuntos con elementos distintos, mapas de valores clave, etc., con cualquier combinación de variantes que se puedan añadir, de solo lectura, inmutables, que respeten el orden. Piense en esto, es posible que desee una colección ampliable 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 dinámicamente ampliable pero solo un número fijo de ellas y también deben poder modificarse? "¿?" Muy raro diría.

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

   1. Broken covariance.

      string[] strings = ... 
      object[] objects = strings; 
      objects[0] = 1; //compiles, but gives a runtime exception. 
      

   2. Arrays can give you reference to a struct!. 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<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense 
      print array[0].mutable // 1, expected or unexpected? confusing surely 
      

   3. Run time implemented methods like ICollection<T>.Contains can be different for structs and classes. No es gran cosa, pero si olvida sobrescribir no genérico Equals correctamente para los tipos de referencia que esperan que la colección genérica busque genérico Equals, obtendrá resultados incorrectos.

      public class Class : IEquatable<Class> 
      { 
          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<Struct> 
      { 
          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. El Length propiedad y [] indexador en T[] parecen ser propiedades regulares que se puede acceder a través de la reflexión (que debe incluir un poco de magia), pero cuando se trata de árboles de expresión que tiene que escupir el mismo exacta el código que hace el compilador Hay ArrayLength y ArrayIndex métodos para hacerlo por separado. Uno de tales question here.Otro ejemplo:

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

Cómo abandonar el uso de matrices

El sustituto más utilizado es List<T> que tiene una API más limpio. Pero es una estructura de crecimiento dinámico que significa que puede agregar un List<T> al final o insertar en cualquier lugar a cualquier capacidad. No hay sustituto para el comportamiento exacto de una matriz, pero la mayoría de las personas usan matrices como colecciones de solo lectura donde no se puede agregar nada. Un sustituto es ReadOnlyCollection<T>. Yo llevo este método de extensión:

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