Velocidad de C# listas

Question

¿Las listas de C# son rápidas? ¿Cuáles son los lados buenos y malos de usar listas para manejar objetos?

¿El uso extenso de listas hará que el software sea más lento? ¿Cuáles son las alternativas a las listas en C#?

¿Cuántos objetos son "demasiados objetos" para las listas?

Answer 1

List<T> utiliza un array de soporte para sostener artículos:

• acceso Indizador (es decir FETCH/actualización) es O (1)
• Quitar de la cola es O (1)
• Eliminar de requiere otra parte elementos existentes que se desplazarán hacia arriba, por lo que O (n) efectivamente
• Añadir al final es O (1) a menos que requiera cambio de tamaño, en cuyo caso es O (n). (Esto duplica el tamaño del búfer, por lo que el costo amortizado es O (1).)
• Añadir a otro lugar requiere que los elementos existentes se desplacen hacia abajo, por lo que O (n) efectivamente
• Encontrar un artículo es O (n) a menos que esté ordenado, en cuyo caso una búsqueda binaria da O (log n)

En general, está bien usar listas bastante extensas. Si conoce el tamaño final cuando comience a completar una lista, es una buena idea usar el constructor que le permite especificar la capacidad, para evitar el cambio de tamaño. Más allá de eso: si le preocupa, explique el generador de perfiles ...

Answer 2

¿En comparación con qué?

• Si se refiere a List<T>, entonces eso es esencialmente un envoltorio alrededor de una matriz; tan rápido para leer/escribir por índice, relativamente rápido para agregar (ya que permite espacio adicional al final, duplicando el tamaño cuando sea necesario) y eliminarlo del final, pero es más costoso realizar otras operaciones (insertar/eliminar que no sea al final)
• Una matriz es más rápida por el índice, pero de tamaño fijo (sin anexar/borrar)
• Dictionary<,> etc ofrecen un mejor acceso mediante llave

Una lista no es intrínsecamente lenta; especialmente si usted sabe que siempre necesita ver todos los datos, o puede acceder a ellos por índice. Pero para listas grandes, puede ser mejor (y más conveniente) buscar a través de una clave. Existen varias implementaciones de diccionario en .NET, cada una con diferentes costos de tamaño/rendimiento.