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

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 serie que se cambia de tamaño según sea necesario, como con cola y lista. (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) inserción amortizada (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 más que eso? ¿Cuál es la desventaja de una implementación de una lista doblemente vinculada?

Answer 1

pero O (n) peor de los casos

El amortizado peor de los casos todavía es 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 usa 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 sólo mucho menor que con una lista enlazada. 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 guestimation aproximada de los recursos de memoria utilizada para una pila de 100 System.Int32 s:

Una implementación gama 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 aplicación 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) 

El inconveniente principal de la implementación de la matriz sería el acto de copiar la matriz cuando necesita ser e xpanded 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.

mismo modo para la cola.

Answer 3

Esto se debe a .NET fue diseñado para funcionar con los 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, una gran cantidad de propiedades inmobiliarias de chips se quema al 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 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 una Stack <> ya está implementada 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).