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

https://stackoverflow.com/questions/75976

09-06-2019
|

Pregunta

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

Se crea una copia vacía de la matriz+1Element y luego los datos de la matriz original se copian en ella 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 utilización de la memoria y la CPU, ¿correcto?

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

Solución

mira el generico List<T> como reemplazo de las matrices.Admiten la mayoría de las mismas cosas que hacen los arreglos, incluida la asignación de un tamaño de almacenamiento inicial si lo desea.

Otros consejos

Esto realmente depende de lo que quieras 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 modificar cualquier tipo de IList en .NET.

Sin embargo, si está utilizando algo como ArrayList, List, Collection, etc.luego llamando al método "Agregar" puede crean una nueva matriz, pero son inteligentes al respecto, no solo cambian el tamaño en 1 elemento, sino que crecen geométricamente, por lo que si agrega muchos valores solo de vez en cuando, tendrá que asignar una nueva matriz .Incluso entonces, puedes usar la propiedad "Capacidad" para forzar su crecimiento de antemano, si sabes cuántos elementos estás agregando (list.Capacity += numberOfAddedElements)

En general, prefiero evitar el uso de matrices.Simplemente use Lista<T>.Utiliza internamente una matriz de tamaño dinámico y es lo suficientemente rápido para la mayoría de los usos.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 sencillo agregar elementos.

Si se encuentra en el 0,1% de uso que requiere velocidad extrema, asegúrese de que los accesos a su lista sean realmente el problema antes de intentar optimizarlo.

Si va a agregar o eliminar elementos con frecuencia, simplemente use una Lista.Si es multidimensional, siempre puedes usar List<List<int>> o algo así.

Por otro lado, las listas son menos eficientes que las matrices si lo que estás haciendo principalmente es atravesando la lista, porque las matrices están todas en un solo lugar en la memoria caché de su CPU, donde los objetos de una lista están 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) 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 incluso más elementos de los que asignó previamente, puede simplemente reasignar la matriz cuando se llene, duplicando el tamaño cada vez.Esto proporciona un rendimiento de cambio de tamaño O(log n) en lugar de O(n) como sería con una matriz de reasignación una vez por adición.Tenga en cuenta que así es como funciona StringBuilder, lo que le brinda una forma más rápida de agregar continuamente una cadena.

Cuándo abandonar el uso de matrices.

Primero y ante todo, cuando la semántica de las matrices no coincide con tu intención - ¿Necesita una colección en crecimiento dinámico?¿Un conjunto que no permite duplicados?¿Una colección que debe permanecer inmutable?Evite las matrices en todos esos casos.Eso es el 99% de los casos.Simplemente exponiendo el punto básico obvio.
En segundo lugar, cuando estás no codificación para una criticidad absoluta del rendimiento - Eso es aproximadamente el 95% de los casos. Las matrices funcionan mejor ligeramente, especialmente en iteración.Casi siempre nunca importa.
Cuando estas no forzado por una discusión con params palabra clave - solo deseaba params aceptó cualquier IEnumerable<T> o incluso mejor, una lengua se construye a sí misma para denotar una secuencia (y no un tipo de marco).
Cuando estás no escribir código heredado o lidiar con la interoperabilidad

En resumen, es muy raro que realmente necesites una matriz.Agregaré ¿por qué se puede evitar?

En mi opinión, la razón principal para evitar matrices 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 Como esta hecho que que se hace lo cual 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 quiero ser pedagógico, pero las matrices realmente se traducen en un significado semántico que rara vez se requiere.La semántica más útil y frecuente es la de colecciones con entradas, conjuntos con elementos distintos, mapas de valores clave, etc. con cualquier combinación de variantes agregables, de solo lectura, inmutables y que respetan el orden.Piense en esto, es posible que desee una colección que se pueda agregar o una colección de solo lectura con elementos predefinidos sin más modificaciones, pero ¿con qué frecuencia su lógica se ve como "Quiero una colección que se puede agregar dinámicamente, pero solo un número fijo de ellos y también deberían ser modificables?" "?Muy raro diría yo.

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

Covarianza rota.

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

¡Las matrices pueden darle 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<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
print array[0].mutable // 1, expected or unexpected? confusing surely

Métodos implementados en tiempo de ejecución como ICollection<T>.Contains puede ser diferente para estructuras y clases.No es gran cosa, pero si olvidas anular 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"

El Length propiedad y [] indexador encendido T[] parecen ser propiedades regulares a las que puedes 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 tienes que escupir exactamente el mismo código que hace el compilador.Hay ArrayLength y ArrayIndex métodos para hacerlo por separado.Uno de tales pregunta 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 utilizado es List<T> que tiene una API más limpia.Pero es una estructura que crece dinámicamente, lo que significa que puedes agregar a una List<T> al final o insertar en cualquier lugar a cualquier capacidad.No existe un sustituto para el comportamiento exacto de una matriz, pero la gente generalmente usa matrices como una colección de solo lectura donde no se puede agregar nada al final.un sustituto es ReadOnlyCollection<T>.Llevo este método de extensión:

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

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

Por lo tanto, no debe utilizar matrices si 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 sencilla de recuperar elementos por índice.

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

Cuando sus puntos de referencia indiquen 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 todos los males), puede evaluar escribir una clase de matriz personalizada con un comportamiento de cambio de tamaño modificado.

Generalmente, 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 más adelante.Si el problema es que continuamente agregará datos nuevos y eliminará datos antiguos, es posible que desee utilizar ArrayList o List por conveniencia, pero tenga en cuenta que son solo arreglos de casos especiales.Cuando "crecen", asignan una matriz completamente nueva y copian todo en ella, lo cual es extremadamente lento.

Lista de arreglo es solo una matriz que crece cuando es necesario.Add se amortiza O(1), solo tenga cuidado de asegurarse 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.Eliminar es O(n). Todos los elementos de la derecha deben moverse.

También es importante tener en cuenta que List no es una lista vinculada.Es solo una ArrayList escrita.La lista documentación señala 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, por lo que es posible que desees explorar el Sistema.Colecciones.Genérico Espacio de nombres.

En este caso particular, diría que si puedes encontrar un buen valor clave Diccionario sería tu mejor apuesta.Tiene inserción y eliminación que se acerca a O (1).Sin embargo, incluso con un Diccionario hay que tener cuidado de no permitir que cambie el tamaño de su matriz interna (una operación O(n)).Es mejor darles mucho espacio especificando una capacidad inicial mayor de la que se espera usar 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, particularmente aquellas de naturaleza iterativa; para cualquier otra cosa, use una de las muchas otras estructuras de datos.

Tienes razón, una matriz es excelente para realizar búsquedas.Sin embargo, las modificaciones del tamaño de la matriz son costosas.

Debe utilizar un contenedor que admita ajustes de tamaño incrementales en el escenario en el que modifica el tamaño de la matriz.Podría usar un ArrayList que le permita establecer el tamaño inicial, y podría verificar continuamente el tamaño versus la capacidad y luego incrementar la capacidad en una gran parte para limitar el número de cambios de tamaño.

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

Esta publicación del foro podría serle de alguna utilidad o no con respecto a la eficiencia de varios tipos de matrices:Matrices C#: multidimensionales frente a lexicográficas

Si creo que voy a agregar muchos elementos a la colección a lo largo de su vida útil, 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 ocasión en la 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 quiero 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 vas a agregar muchas cosas, y no realizarás acceso aleatorio (como myArray[i]).Podrías considerar usar una lista enlazada (LinkedList<T>), porque nunca tendrá que "crecer" como el List<T> implementación.Sin embargo, tenga en cuenta que sólo puede acceder a los elementos en un LinkedList<T> implementación utilizando el IEnumerable<T> interfaz.

Lo mejor que puedes hacer es asignar tanta memoria como necesites por adelantado, si es posible.Esto evitará .NETO de tener que hacer llamadas adicionales para tener memoria en el montón.De lo contrario, 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.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow