c# - ¿Por qué se implementan Stack<T> y Queue<T> con una matriz?

.net linked-list

Question

Estoy leyendo C # 4.0 en una cáscara de nuez por los hermanos Albahari y me encontré con esto:

Las pilas se implementan internamente con una matriz que cambia de tamaño según sea necesario , como con Queue y List. (pg 288, párrafo 4)

No puedo evitar preguntarme por qué. LinkedList proporciona O (1) inserciones y eliminaciones de cabeza y cola (que deberían funcionar bien para una pila o cola). Una matriz redimensionable tiene O (1) inserto amortizado (si mal no recuerdo), pero O (n) peor caso (no estoy seguro acerca de eliminar). Y probablemente use más espacio que la lista vinculada (para grandes pilas / colas).

¿Hay algo más que eso? ¿Cuál es la desventaja de una implementación de una lista doblemente vinculada?

Answer 1

pero O (n) el peor caso

El peor caso amortizado sigue siendo O (1). Los tiempos de inserción largos y cortos son el promedio: ese es el punto del análisis amortizado (y lo mismo para la eliminación).

Una matriz también utiliza menos espacio que una lista vinculada (que después de todo tiene que almacenar un puntero adicional para cada elemento).

Además, la sobrecarga es mucho menor que con una lista vinculada. En general, una implementación basada en arreglos es simplemente (mucho) más eficiente para casi todos los casos de uso, aunque de vez en cuando el acceso tardará un poco más (de hecho, una cola puede implementarse de manera ligeramente más eficiente al tomar ventaja de las páginas que se administran en una lista vinculada; consulte la implementación de C ++ '' std::deque ).

Answer 2

Aquí hay una estimación aproximada de los recursos de memoria utilizados para una pila de 100 System.Int32 s:

Una implementación de matriz requeriría lo siguiente:

type designator                          4 bytes
object lock                              4
pointer to the array                     4 (or 8)
array type designator                    4
array lock                               4
int array                              400
stack head index                         4
                                       ---
Total                                  424 bytes  (in 2 managed heap objects)

Una implementación de lista enlazada requeriría lo siguiente:

type designator                          4 bytes
object lock                              4
pointer to the last node                 4 (or 8)
node type designator         4 * 100 = 400
node lock                    4 * 100 = 400
int value                    4 * 100 = 400
pointer to next node  4 (or 8) * 100 = 400 (or 800)
                                     -----
Total                                1,612 bytes  (in 101 managed heap objects)

La desventaja principal de la implementación de la matriz sería el acto de copiar la matriz cuando necesita expandirse. Ignorando todos los demás factores, esta sería una operación O (n) donde n es la cantidad de elementos en la pila. Esto parece bastante malo, excepto por dos factores: casi nunca ocurre, ya que la expansión se duplica en cada incremento, y la operación de copia de la matriz está altamente optimizada y es increíblemente rápida. Por lo tanto, la expansión es, en la práctica, fácilmente inundada por otras operaciones de pila.

Del mismo modo para la cola.

Answer 3

Esto es porque .NET fue diseñado para ejecutarse en procesadores modernos. Que son mucho, mucho más rápido que el bus de memoria. El procesador funciona a alrededor de 2 gigahertz. La RAM en su máquina tiene un reloj de unos cientos de megahercios. Leer un byte de RAM lleva más de cien ciclos de reloj.

Lo que hace que la memoria caché de la CPU sea muy importante en los procesadores modernos, y se quema una gran cantidad de propiedades inmobiliarias con chips para hacer las cachés lo más grandes posible. Hoy en día es típico 64 KB para la caché L1, la memoria más rápida y físicamente ubicada muy cerca del núcleo del procesador, 256 KB para la caché L2, más lenta y más alejada del núcleo, alrededor de 8 MB para la caché L3, más lenta y más alejada de distancia, compartida por todos los núcleos en el chip.

Para que las cachés sean efectivas, es muy importante acceder a la memoria secuencialmente. Leer el primer byte puede ser muy costoso si se necesita acceso a memoria L3 o RAM, los siguientes 63 bytes son muy económicos. El tamaño de la "línea de caché", la unidad de transferencia de datos para el bus de memoria.

Esto hace que una matriz sea con mucho la estructura de datos más efectiva, sus elementos se almacenan secuencialmente en la memoria. Y una lista vinculada de lejos la peor estructura de datos posible, sus elementos se encuentran naturalmente dispersos a través de la memoria, lo que puede ocasionar el costoso error de caché para cada elemento.

En consecuencia, todas las colecciones .NET, excepto LinkedList <> se implementan como matrices internamente. Tenga en cuenta que un Stack <> ya está implementado de forma natural como una matriz, ya que solo puede presionar y mostrar un elemento desde el final de la matriz. Una operación O (1). El tamaño de la matriz se amortiza O (logN).