2010-09-13 24 views
5

En mi opinión, List se implementa básicamente utilizando LinkedList, mientras que un Array normal se implementa como bloques contiguos. Siempre utilicé List porque está en el espacio de nombres Generic y porque pensé que usaba asignación de memoria dinámica - pero estaba equivocado.¿Por qué SortedList y List usan array y por qué LinkedList no se usa mucho?

Ayer vi la implementación de List usando Reflector y encontré que en realidad es una matriz de T (T[]). Hay muchos Array.Copy alrededor al manipular cada elemento en el List. Por ejemplo, cuando usa Insert, creará una nueva memoria y copiará todos los elementos antes/después de los elementos insertados. Entonces me parece que el uso de List es muy caro.

Vi el SortedList también. No estoy seguro de por qué un SortedList también implementa una matriz dentro de él. ¿No cree que SortedList sería horrible utilizar una matriz, ya que necesita ordenar la lista cada vez que se produce una manipulación menor en el List?

También me pregunto por qué List es tan popular como la mayoría de la gente lo usa en lugar de ir por LinkedList. ¿Es solo por la flexibilidad del indexador?

+5

Mire de cerca: Lista <> no * crea una nueva matriz y copia todos los elementos en * cada * llamada. La matriz solo se redimensiona cuando está llena y se redimensiona al doble de su tamaño original. El redimensionamiento se produce solo a intervalos exponencialmente crecientes cuando se agregan elementos continuamente. – dtb

+2

No hay una respuesta correcta a esta pregunta. Piense en ser más específico o marque como wiki –

+0

@dtb sí, usa this._items [this._size ++] = item; Sí, aumenta exponencialmente los intervalos, pero ¿cómo garantiza siempre que el tamaño ++ tenga un espacio vacío? – abhishek

Respuesta

13

Sí, SortedList es O (n) para inserciones. Usar con cuidado

La razón principal es el diseño moderno de la computadora. La memoria caché de la CPU es muy importante porque la memoria RAM es muy lenta. El diseño del bus de memoria simplemente no podía seguir el ritmo de los rápidos avances en las velocidades de reloj de la CPU. Hacer que una señal digital de alta frecuencia viaje más de una pulgada es muy difícil.

Una matriz tiene un rendimiento de la memoria caché inmejorable, es muy probable que el siguiente elemento ya esté en la memoria caché cuando lo itere. Una lista vinculada ofrece muy pocas probabilidades de que este sea el caso, el siguiente elemento está esencialmente en una dirección aleatoria. Eso es caro, detiene el procesador, esperando que la memoria RAM se ponga al día. Puede ser cientos de ciclos

+0

Sí, SortedList realmente me pareció caro. Creo que recibí mi respuesta. Así que el punto es: Array => Bueno, porque el siguiente elemento está disponible al instante, regalando menos carga de trabajo a la CPU. LinkedList => Bueno cuando se inserta en el medio, a menudo no es necesario para mí. SortedList => Muy caro, debe ser avioided. – abhishek

+0

+1 muy buen punto/explicación. Y no olvide que es aún más lento si tiene que acceder a la dirección del elemento anterior cuando necesita la siguiente :) – digEmAll

+1

@abhishek: SortedList tiene un propósito diferente. Es una colección asociativa (Key-Value), está ordenada por clave y tiene una búsqueda de clave O (log n) bastante rápida. – digEmAll

2

Porque la mayoría de las colecciones no necesitan inserciones en el medio a menudo. Pero sí necesitan acceso directo a través de un indexador.

+0

clavado :) La mejor razón. Además, una 'List ' es mucho más fácil de usar y comprender. – nawfal

1

En la vida real Lista no llama Array.Copy menudo, por lo general sólo necesario añadir elementos a la matriz, no inserte. Es un propósito de Lista, a diferencia de una lista vinculada. Solo debes elegir una clase de colección adecuada.

Si inserta elementos a menudo utilice la lista vinculada. Si generalmente agrega elementos y necesita repetirlos de manera efectiva, use List.

2

Si desea una colección en memoria de un solo tipo para el cual:

  1. La colección debe ser cultivable.
  2. La operación de mutación más común es que agrega un elemento al final de la colección.
  3. La recuperación rápida por índice es esencial.

luego List<T> es probablemente su mejor opción. LinkedList<T> puede ser una mejor opción cuando (2) y (3) no se aplican.

Cuestiones relacionadas