net - initialize array c#

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

Question

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

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

Si esto es cierto, entonces el uso de una matriz dentro de un escenario que requiere mucha actividad del elemento está contraindicado debido a la utilización de la memoria y 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

ArrayList y List hacen crecer la matriz en más de una cuando sea necesario (creo que es duplicando el tamaño, pero no he verificado la fuente). En general, son la mejor opción cuando construyes una matriz de tamaño dinámico.

Cuando los puntos de referencia indican que el cambio de tamaño de la matriz está ralentizando seriamente 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 cambio de tamaño ajustado.

Answer 2

Cuando se cambia el tamaño de la matriz, se debe asignar una nueva matriz y copiar el contenido. 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

En general, prefiero evitar el uso de la matriz. Solo usa 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 List <List <List <T >>> si es necesario. No es mucho peor en términos de memoria, y es mucho más simple agregar elementos a.

Si está en el 0.1% de uso que requiere una velocidad extrema, asegúrese de que sean los accesos a su lista los que realmente sean el problema antes de intentar optimizarlos.

Answer 4

En general, si debe tener el MEJOR rendimiento de búsqueda indexada, es mejor crear una Lista primero 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 de asegurarse de que el cambio de tamaño no ocurra en un mal momento. Insertar 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 documentación de la Lista sí nota 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 apropiada para su problema. Esto depende de MUCHAS cosas y, por lo tanto, es posible que desee explorar el espacio de nombres System.Collections.Generic Namespace.

En este caso particular, diría que si puede encontrar un buen valor de clave, el diccionario 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.

-Almiar

Answer 5

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

Debería usar un contenedor que admita ajustes de tamaño incrementales 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. Entonces, sin embargo, las búsquedas son lentas ...

Answer 6

Esta publicación en el foro podría ser de alguna utilidad para la eficiencia de varios tipos de matriz: matrices C # - multidimensional vs lexicographic

Answer 7

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á utilizando algo como ArrayList, List, Collection, etc., al llamar al método "Add" puede crear una nueva matriz, pero son inteligentes al respecto, no solo cambian el tamaño por 1 elemento, sino que crecer 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 list.Capacity += numberOfAddedElements , si sabe cuántos elementos está agregando ( list.Capacity += numberOfAddedElements )

Answer 8

Las matrices son excelentes 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 9

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

Otra vez que generalmente utilizo 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 Lista, sino que desean 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 10

Si va a agregar / eliminar elementos mucho, simplemente use una lista. Si es multidimensional, siempre puede usar una Lista <List <int >> 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 las matrices están todas en un lugar en tu caché de CPU, donde los objetos en una lista están dispersos por todos lados.

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

1) Generarlo como una Lista (o Lista de Listas) y luego usar 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 11

Si vas a agregar mucho y no harás acceso aleatorio (como myArray[i] ). Podría considerar usar una lista vinculada ( LinkedList<T> ), porque nunca tendrá que "crecer" como la implementación de la List<T> . Tenga en cuenta, sin embargo, que solo puede acceder realmente a los elementos en una implementación LinkedList<T> utilizando la IEnumerable<T> .

Answer 12

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 13

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 puedes aplicar a cualquier cosa realmente.

Answer 14

Cuándo abandonar el uso de matrices

1. En primer lugar, cuando la semántica de las matrices no coincide con su intención : ¿necesita una colección que crezca dinámicamente? 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 no está codificando la criticidad absoluta del rendimiento , eso es aproximadamente el 95% de los casos. Las matrices funcionan mejor marginalmente , especialmente en iteración . Casi nunca importa.

3. Cuando no se ve forzado por un argumento con la palabra clave params , solo deseé que los params aceptaran cualquier IEnumerable<T> o incluso mejor un constructo de lenguaje para denotar una secuencia (y no un tipo de marco).

4. Cuando no está escribiendo código heredado o lidiando con interoperabilidad

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

1. La razón más importante 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 lo que se hace, lo que va 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éricos e imita la genericidad 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 referencias 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<Value>[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<T>.Contains pueden ser diferentes para estructuras y clases . No es un gran problema, pero si olvida anular Equals no genéricos correctamente para los tipos de referencia que esperan que la colección genérica busque Equals genéricos , 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. La propiedad Length y [] indexer en T[] parecen ser propiedades regulares a las que se puede acceder mediante 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 compilador. Hay métodos ArrayLength y ArrayIndex para hacer eso por separado. Una de esas preguntas aquí . 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 comúnmente usado es List<T> que tiene una API más limpia. Pero es una estructura que crece dinámicamente, lo que significa que puede agregar a una List<T> al final o insertar en cualquier parte 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> . Llevo este método de extensión:

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

Answer 15

Mire la List<T> genérica 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.