¿Hay alguna razón para usar una matriz cuando hay listas disponibles? [cerrado]

30

Parece que List<T>en C # puede hacer todo lo que una matriz puede hacer y más, y también parece tan eficiente en memoria y rendimiento como una matriz.

Entonces, ¿por qué querría usar una matriz?

Obviamente no estoy preguntando sobre casos en los que una API u otra restricción externa (es decir, la función Principal) requiere que use una matriz ... Solo estoy preguntando sobre la creación de nuevas estructuras de datos en mi propio código.

JoelFan
fuente
56
Para implementarList<T>
monstruo de trinquete
43
is also just as efficient in memory and performance as an array- um. ¿De dónde sacaste esa idea?
Oded
12
Múltiples dimensiones como var test = new string[5,5];)
Knerd
77
También está el conjunto de bytes [] comúnmente utilizado.
SBoss
11
Para C # específicamente, Eric Lippert escribió sobre esto en blogs.msdn.com/b/ericlippert/archive/2008/09/22/… .
Mephy

Respuestas:

26

La misma razón por la que no conduzco un camión cuando voy a trabajar. No uso algo de lo que no usaré las características.

En primer lugar, una matriz es una construcción primitiva, por lo que una matriz es más rápida y más eficiente que una Lista <>, por lo que su argumento no es verdadero. La matriz también está disponible en todas partes y es conocida por los desarrolladores que utilizan diferentes idiomas y plataformas.

La razón más importante por la que uso una matriz en lugar de una Lista <> es para implicar que los datos tienen una longitud fija . Si no voy a agregar o eliminar ningún elemento de esa recopilación de datos, quiero asegurarme de que el tipo refleje eso.

Otra cosa es, digamos, que está implementando una nueva estructura de datos y que ha leído algunos documentos al respecto. Ahora, al implementar algoritmos específicos, no siempre se puede confiar en la implementación de otro tipo de propósito general. Cambia de .NET a Mono e incluso entre diferentes versiones del marco.

Y a veces es más fácil portar un fragmento de código que utiliza una matriz en lugar de un tipo dependiente del marco.

Mert Akcakaya
fuente
44
¿Cómo es una matriz "más rápida" que una lista, considerando que List<T>se implementa usando una matriz? Si conoce el recuento de elementos de antemano (que debe saber cuando usa una matriz), puede usar ese conocimiento al inicializar la lista también.
Theodoros Chatzigiannakis
1
@TheodorosChatzigiannakis Cuando usamos una matriz, asignamos la memoria y simplemente hacemos asignaciones, malloc simple (), sin sobrecarga. Cuando use Lista <>, "Agregará" elementos y al agregar elementos, Lista <> realizará algunas comprobaciones de límites y llamará al método GuaranteeCapacity, que copiará el contenido a otra matriz recién asignada si la capacidad actual no es suficiente. Significa que si no necesita asignar dinámicamente nueva memoria, el rendimiento de List no es tan bueno como la matriz.
Mert Akcakaya
44
Lo que está diciendo es correcto, pero se supone que, o bien no sabemos contador de elementos de antemano (en cuyo caso, las matrices son de todos modos no útil) o que nos haga conocer el contador de elementos de antemano, sino que deliberadamente no hacer uso en el caso de la lista Si nosotros hacemos utilizar el contador de elementos para inicializar la lista con la capacidad deseada, obtenemos una única distribución array (hasta llegar a esa capacidad), por lo tanto tenemos que pagar los mismos costos de funcionamiento. Todas las demás operaciones comunes son iguales (búsqueda, recuperación por índice, asignación por índice), excepto las adiciones adicionales (que las matrices no tienen en absoluto).
Theodoros Chatzigiannakis
3
@TheodorosChatzigiannakis: Las matrices son más rápidas que las listas. Simplemente ejecute un punto de referencia simple para verificar.
Mehrdad
1
@TheodorosChatzigiannakis, sí, pero todavía hay controles de límites.
Mert Akcakaya
18

Necesita matrices para administrar su colección de estructuras mutables , por supuesto, y qué haríamos sin ellas.

struct EvilMutableStruct { public double X; } // don't do this

EvilMutableStruct[] myArray = new EvilMutableStruct[1];
myArray[0] = new EvilMutableStruct()
myArray[0].X = 1; // works, this modifies the original struct

List<EvilMutableStruct> myList = new List<EvilMutableStruct>();
myList.Add(new EvilMutableStruct());
myList[0].X = 1; // does not work, the List will return a *copy* of the struct

(tenga en cuenta que puede haber algunos casos en los que sea deseable una matriz de estructuras mutables, pero generalmente este comportamiento diferente de estructuras mutables dentro de las matrices frente a otras colecciones es una fuente de errores que deben evitarse)


Más en serio, necesita una matriz si desea pasar un elemento por referencia . es decir

Interlocked.Increment(ref myArray[i]);  // works
Interlocked.Increment(ref myList[i]);   // does not work, you can't pass a property by reference

Eso puede ser útil para el código seguro de subprocesos sin bloqueo.


Necesita una matriz si desea inicializar de manera rápida y eficiente su colección de tamaño fijo con el valor predeterminado .

double[] myArray = new double[1000]; // contains 1000 '0' values
                                     // without further initialisation

List<double> myList = new List<double>(1000) // internally contains 1000 '0' values, 
                                             // since List uses an array as backing storage, 
                                             // but you cannot access those
for (int i =0; i<1000; i++) myList.Add(0);   // slow and inelegant

(tenga en cuenta que sería posible implementar un constructor para List que haga lo mismo, es solo que C # no ofrece esta función)


necesita una matriz si quiere copiar eficientemente partes de la colección

Array.Copy(array1, index1, array2, index2, length) // can't get any faster than this

double[,] array2d = new double[10,100];
double[] arraySerialized = new double[10*100];
Array.Copy(array2d, 0, arraySerialized, 0, arraySerialized.Length);
// even works for different dimensions

(de nuevo, esto es algo que también podría implementarse para List, pero esta característica no existe en c #)

HugoRune
fuente
Si se supone que un tipo representa un grupo de variables relacionadas pero independientes pegadas con cinta adhesiva (por ejemplo, las coordenadas de un punto), una estructura de campo expuesto es la mejor representación. Si se supone que una variable contiene un grupo de tales grupos, una matriz de ese tipo de estructura es la mejor representación. Uno no debería usar estructuras mutables en lugares donde quiere un objeto, pero eso no significa que deba usar objetos o cosas que pretenden ser objetos en lugares donde uno quiere un montón de variables pegadas con cinta adhesiva.
supercat
Hay algunas situaciones en las que es posible que desee una estructura mutable, como cuando necesita el último bit de rendimiento y no puede permitirse las asignaciones y referencias del montón, y en ese caso una variedad de estructuras es su mejor opción. Buen ensayo aquí . Pero no estoy de acuerdo con que una clase no represente "un grupo de variables unidas". Conceptualmente, las estructuras y las clases son básicamente las mismas, las diferencias se deben principalmente a los detalles de implementación.
HugoRune
Si se desea utilizar una colección de referencias de objetos mutables como una colección de grupos independientes de variables independientes, se debe establecer y mantener una invariante de que cada elemento identifica un objeto para el cual no existen otras referencias no efímeras en ningún lugar del universo. Eso ciertamente se puede hacer (y a menudo se hace), pero no hay nada en el lenguaje o marco para ayudar al programador a mantener esa invariante. Por el contrario, una matriz de longitud 100 de un tipo de estructura con cuatro campos de instancia encapsulará automática y permanentemente 400 variables independientes.
supercat
Creo que estos comentarios son el lugar equivocado para discutir este tema más a fondo, y dado que agregó su propia respuesta , no parece ser necesario duplicar esta información aquí. Baste decir que las matrices se pueden usar para administrar estructuras mutables. Si usar el comportamiento de implementación de esas estructuras y cuándo aplicar ciertas restricciones de datos realmente va más allá del alcance de mi respuesta.
HugoRune
15

Entonces, ¿por qué querría usar una matriz?

En raras ocasiones , tendrá un escenario en el que sabe que necesita un número fijo de elementos. Desde una perspectiva de diseño, esto debe evitarse. Si necesita 3 cosas, la naturaleza del negocio significa que muy a menudo necesitará 4 en la próxima versión.

Aún así, cuando este raro escenario realmente ocurre, es útil usar una matriz para hacer cumplir ese invariante de tamaño fijo. Proporciona una señal a otros programadores de que tiene un tamaño fijo y ayuda a evitar el mal uso en el que alguien agrega o elimina un elemento, lo que rompe las expectativas en otras partes del código.

Telastyn
fuente
23
El tamaño de las matrices no está establecido en piedra en el momento en que uno escribe el código. Puede, y a menudo es, una variable de tiempo de ejecución. Simplemente nunca cambia después de que se haya creado la matriz .
11
No es inusual tratar con un número fijo de elementos. Si está trabajando con puntos 3D, probablemente no trabajará con puntos 5D en ningún momento en el futuro. El mayor problema con las matrices es que son mutables y no tienen etiquetas convenientes adheridas a sus elementos.
Doval
3
@JanDvorak Las listas pueden reducirse o crecer y, por lo tanto, no tienen sentido en ningún contexto que implique un número fijo de elementos.
Doval
99
¿Raramente? No todos trabajan en monstruos empresariales súper complicados y ultraconfigurables.
whatsisname
3
Es muy común tener un número fijo de elementos. Solo asegúrese de que la longitud esté definida por una constante, de modo que cuando la próxima versión aumente el número de elementos de 3 a 4, simplemente cambie la constante y todo lo que se base en esto se adaptará.
Hans
9

Su pregunta ya ha sido respondida antes .

y también parece tan eficiente en memoria y rendimiento como una matriz.

No lo es De la pregunta que vinculé:

List/foreach:  3054ms (589725196)
Array/foreach: 1860ms (589725196)

Las matrices son dos veces más rápidas en ciertos casos importantes. Estoy seguro de que el uso de la memoria también difiere de manera no trivial.

Dado que la premisa principal de su pregunta es derrotada, supongo que esto responde a su pregunta. Además de esto, a veces las matrices son forzadas por Win32 API, o el sombreador de su GPU, o alguna otra biblioteca que no sea DotNet.

Incluso dentro de DotNet, algunos métodos consumen y / o devuelven matrices (como String.Split). Lo que significa que ahora debe pagar el costo de las llamadas ToListy ToArraytodo el tiempo, o debe conformarse y usar la matriz, posiblemente continuando el ciclo propagándolo a los usuarios pobres de su código.

Más preguntas y respuestas sobre Stack Overflow sobre este tema:

Superbest
fuente
Curiosamente, esa respuesta señala que si usa bucles indexados anticuados ( para en lugar de foreach ) la diferencia de rendimiento es mínima.
user949300
3

Además de las razones enumeradas en otras respuestas, el literal de matriz requiere menos caracteres para declarar:

var array = new [] { "A", "B", "C" };
var list = new List<string>() { "A", "B", "C" };

El uso de la matriz en lugar de Listhace que el código sea un poco más corto y un poco más legible en los casos en que (1) necesita pasar un IEnumerable<T>literal, o (2) donde otras funciones Listno importan y necesita usar algunas listas literal.

He hecho esto ocasionalmente en pruebas unitarias.

ikh
fuente
1
Sí solo para agregar. También funciona si necesita pasar una IList <T>
Esben Skov Pedersen
+1, a menudo tengo alguna operación para un par de objetos del mismo tipo que no están en una colección. Es fácil, breve y claro para escribir foreach( var x in new []{ a, b, c ) ) DoStuff( x )o new []{ a, b, c ).Select( ... )etc.
stijn
3

Esto es estrictamente desde una perspectiva OO.

Si bien no puedo pensar en una razón para pasar solo una matriz, ciertamente puedo ver situaciones en las que una representación de matriz interna de la clase es probablemente la mejor opción.

Si bien existen otras opciones que ofrecen características similares, ninguna parece tan intuitiva como una matriz para problemas relacionados con el procesamiento de permutaciones, anidadas para bucles, representación matricial, mapas de bits y algoritmos de intercalación de datos.

Hay un número considerable de campos científicos que se basan ampliamente en las matemáticas de matriz. (por ejemplo, procesamiento de imágenes, corrección de errores de datos, procesamiento de señales digitales, una gran cantidad de problemas matemáticos aplicados). La mayoría de los algoritmos en esos campos están escritos en términos de uso de matrices / matrices multidimensionales. Por lo tanto, sería más natural implementar los algoritmos tal como se definen en lugar de hacerlos más amigables con el "software" a expensas de perder los vínculos directos con los documentos en los que se basan los algoritmos.

Como dije, en estos casos, probablemente pueda salirse con la suya usando listas, pero eso agrega otra capa de complejidad además de lo que ya son algoritmos complejos.

Remojar
fuente
3

Esto realmente se aplica a otros lenguajes que también tienen listas (como Java o Visual Basic). Hay casos en los que necesita usar una matriz porque un método devuelve una matriz en lugar de una Lista.

En un programa real, no creo que se use una matriz muy a menudo, pero a veces sabes que los datos tendrán un tamaño fijo y te gusta la pequeña ganancia de rendimiento que obtienes al usar una matriz. La microoptimización sería una razón válida, como un método que devuelve una lista, o la necesidad de una estructura de datos multidimensional.

Dylan Meeus
fuente
1
Muchos idiomas ni siquiera tienen colecciones de listas y matrices separadas. Por otro lado, usar list<T>where vector<T>will work es una idea desastrosamente mala en C / C ++.
Gort the Robot
1
"Debido a que un método devuelve una matriz": esta es una característica incorrecta de Java, lo que obliga a los programadores a descifrar el código con "Arrays.asList (x)". T [] debería al menos implementar Iterable <T>
kevin cline
44
@StevenBurnap: ciertamente es desastrosamente malo en C, porque no hay forma de compilar ese código.
Pete Becker
La expresión @PeteBecker vector<T> x compila bien para mí en C . :-)
svick
Lo siento, quise decir el equivalente a C enrollado a mano list<T>. Básicamente, he visto muchos problemas de rendimiento causados ​​por los desarrolladores que solo usan listas por defecto cuando una matriz era una mejor opción.
Gort the Robot
1

Bueno, encontré un uso para las matrices en un juego que he estado escribiendo. Lo usé para crear un sistema de inventario con un número fijo de ranuras. Esto tuvo varios beneficios:

  1. Sabía exactamente cuántas ranuras de inventario abiertas tenía el objeto del juego mirando y viendo qué ranuras eran nulas.
  2. Sabía exactamente en qué índice estaba cada elemento.
  3. Seguía siendo una matriz "tipificada" (Inventario de Ítem []), por lo que podía agregar / eliminar los objetos de tipo "Ítem".

Pensé que si alguna vez necesitaba "aumentar" el tamaño del inventario, podría hacerlo transfiriendo los elementos antiguos a la nueva matriz, pero dado que el inventario estaba arreglado por el espacio de la pantalla y no tenía necesidad de hacerlo dinámicamente más grande / más pequeño, funcionó bien para el propósito para el que lo estaba usando.

monte
fuente
1

Si está atravesando todos los elementos de una lista, entonces no, no es necesaria una matriz, la 'selección sin reemplazo' 'siguiente' o arbitraria funcionará bien.

Pero si su algoritmo necesita acceso aleatorio a los elementos de la colección, entonces, sí, es necesaria una matriz.

Esto es algo análogo a "¿es necesario ir?". En un lenguaje moderno razonable no es necesario en absoluto. Pero si elimina las abstracciones, en algún momento, eso es todo lo que está realmente disponible para usted, es decir, la única forma de implementar estas abstracciones es con la característica 'innecesaria'. (Por supuesto, la analogía no es perfecta, no creo que nadie diga que los arreglos son una mala práctica de programación; son fáciles de entender y pensar).

Mitch
fuente
La lista <T> también ofrece acceso aleatorio. Claro, se implementa con una matriz, pero eso no tiene por qué molestarlo a usted, el usuario. En el mejor de los casos, ofreció una única razón para usar matrices: implementar List<T>.
@delnan Creo que ese es mi punto con respecto a las abstracciones. A veces es mejor pensar en términos de una matriz, no solo por razones de eficiencia. (por supuesto, a veces es mucho mejor pensar en una lista enlazada, y mucho mejor que eso pensar en una lista (sin preocuparse por los enlaces o de otra manera cómo se implementa), y mucho mejor solo una colección.
Mitch
0

Compatibilidad heredada.

Todo forma experiencia personal:

Programadores heredados: mi colega usa matrices en todas partes, lo ha hecho durante más de 30 años, la buena suerte cambió de opinión con sus nuevas ideas.

Código heredado: foo (barra de matriz []) seguro de que puede usar una función de lista / vector / colección toarray, pero si no usa ninguna de las características adicionales, es más fácil usar una matriz para empezar, a menudo más legible sin el cambio de tipo.

Jefa heredada: mi jefa era una buena programadora antes de que ella se pusiera en la gerencia hace muchos años y todavía piensa que está al día, "estaba usando matrices" puede finalizar una reunión, explicando lo que una colección puede costarles a todos el almuerzo.

Skeith
fuente
3
colegas que llevan 20 años detrás de la curva y un jefe que quiere saber qué tipos de datos está utilizando ... Me encanta este sitio por recordarme lo peor que podría ser mi trabajo
JoelFan
1
alrededor del 40% de lo que hacemos está incrustado diseño donde las discusiones se llevan a cabo en KB, que le gusta a mí, no hes hes obsoletos specalised decir lol
Skeith
0

1) No hay una versión multidimensional de List. Si sus datos tienen más de una dimensión, será muy ineficiente usar listas.

2) Cuando se trata de una gran cantidad de tipos de datos pequeños (por ejemplo, un mapa donde todo lo que tiene es un byte para el tipo de terreno) puede haber diferencias de rendimiento considerables debido al almacenamiento en caché. La versión de matriz carga varios elementos por lectura de memoria, la versión de lista carga solo uno. Además, la versión de la matriz contiene varias veces más celdas en la memoria caché que la versión de la lista; si está procesando repetidamente los datos, esto puede hacer una gran diferencia si la versión de la matriz cabe en la memoria caché pero la versión de la lista no.

Para un caso extremo, considere Minecraft. (Sí, no está escrito en C #. Se aplica la misma razón).

Loren Pechtel
fuente
0

Una matriz de 100 elementos de algún tipo T encapsula 100 variables independientes de tipo T. Si T es un tipo de valor que tiene un campo público mutable de tipo Q y uno de tipo R, entonces cada elemento de la matriz encapsulará variables independientes de los tipos Q y R. La matriz en su conjunto encapsulará así 100 variables independientes del tipo Q y 100 variables independientes del tipo R; Se puede acceder a cualquiera de esas variables individualmente sin afectar a ninguna otra. Ningún tipo de colección que no sean matrices puede permitir que los campos de estructuras se utilicen como variables independientes.

Si, en cambio, T es un tipo de clase con campos públicos mutables de tipo Q y R, cada elemento de la matriz tiene la única referencia, en cualquier parte del universo, a una instancia de T, y si ninguno de los elementos de la matriz alguna vez se modifique para identificar un objeto para el cual existe alguna referencia externa, entonces la matriz encapsulará efectivamente 100 variables independientes de tipo Q y 100 variables independientes de tipo R. Otros tipos de colección pueden imitar el comportamiento de dicha matriz, pero si el único propósito de la matriz es encapsular 100 variables de tipo Q y 100 de tipo R, encapsular cada par de variables en su propio objeto de clase es una forma costosa de hacerlo. Promover,El uso de una matriz o colección de tipo de clase mutable crea la posibilidad de que las variables identificadas por los elementos de la matriz no sean independientes .

Si se supone que un tipo se comporta como algún tipo de objeto, debe ser un tipo de clase o una estructura de campo privado que no proporcione otro medio de mutación que no sea el reemplazo. Sin embargo, si se supone que un tipo se comporta como un conjunto de variables relacionadas pero independientes unidas con cinta adhesiva, entonces se debe usar un tipo que es un conjunto de variables unidas con cinta adhesiva, una estructura de campo expuesto . Las matrices de este tipo son muy eficientes para trabajar y tienen una semántica muy limpia. El uso de cualquier otro tipo conducirá a una semántica confusa, un rendimiento inferior o ambos.

Super gato
fuente
0

Una diferencia importante es la asignación de memoria. Por ejemplo, atravesar una lista vinculada podría ocasionar muchos errores de caché y un rendimiento más lento, mientras que una matriz representa una porción contigua de memoria que contiene múltiples instancias de algún tipo de datos en particular, y atravesarla en orden es más probable que golpee la CPU cache.

Por supuesto, una serie de referencias a objetos puede no beneficiarse tanto de los éxitos de caché, ya que la desreferenciación podría llevarlo a cualquier parte de la memoria.

Luego están las implementaciones de listas como ArrayList, que implementan una lista usando una matriz. Son primitivas útiles para tener.

Rory Hunter
fuente
2
La pregunta se refiere específicamente al tipo .Net List<T>, que no se implementa usando una lista vinculada, sino usando una matriz (es esencialmente equivalente a ArrayList<T>en Java).
svick
-2

Aquí hay algunas pautas que puede usar sobre cuándo seleccionar Arrayy cuándo seleccionar List.

  • Úselo Arraycuando regrese de un método.
  • Úselo Listcomo variable cuando construya el valor de retorno (dentro del método). Luego, use .ToArray()cuando regrese del método.

En general, use un Arraycuando no tenga la intención de que el consumidor agregue elementos a la colección. Úselo Listcuando desee que el consumidor agregue elementos a la colección.

Arrayestá destinado a tratar con colecciones "estáticas", mientras que Listestá destinado a tratar con colecciones "dinámicas".

Daniel Lidström
fuente
2
La regla que sugiere es arbitraria y es probable que genere un código ineficiente que realice copias innecesarias. Por lo menos necesitas alguna forma de justificación para ello.
Jules
@Jules He encontrado que la experiencia del desarrollador es mucho más importante que las micro optimizaciones. Nunca tengo problemas de rendimiento en este nivel.
Daniel Lidström
Sin embargo, no veo cómo esta experiencia mejora la experiencia del desarrollador. Requiere que adivine lo que los clientes de su código van a querer hacer con los valores devueltos, y hace que su código sea menos conveniente de usar cuando se equivoca, y aún así no veo ninguna ventaja en absoluto. El rendimiento puede ser una preocupación secundaria, pero no lo sacrificaría para seguir una regla que no gana nada.
Jules
@Jules Supongo que todo se reduce a tus preferencias entonces. Prefiero tratar los valores de retorno como constantes, como tal prefiero usar en Arraylugar de List. ¡Es bueno escuchar tus pensamientos!
Daniel Lidström
¿Has considerado usar UmmodifiableLists?
Jules