Actualmente estoy usando List<T> como una cola (use lst[0] then lst.removeAt(0)) para contener objetos. Hay alrededor de 20 elementos como máximo en un momento dado. Me di cuenta de que había una clase real Queue<T>. Me pregunto si hay algún beneficio (rendimiento, memoria, etc.) al usar un Queue<T> sobre un List<T> actuando como una cola?Queue <T> vs List <T>
El rendimiento se puede perfilar. Aunque en este caso son tan pocos los elementos, es posible que deba ejecutar el código millones de veces para obtener realmente las diferencias que valen la pena.
Voy a decir esto: Queue<T> expondrá su intención de manera más explícita, la gente sabe cómo funciona una cola.
Una lista que se utiliza como una cola no es tan clara, especialmente si tiene mucha indexación innecesaria y código RemoveAt(magicNumber). Dequeue es mucho más consumible desde el punto de vista de mantenimiento del código.
Si esto le da problemas de rendimiento mensurables, puede solucionarlo. No aborde cada problema potencial de rendimiento por adelantado.
¿Por qué no deberíamos abordar todos los posibles problemas de rendimiento por adelantado? –
@JohnIsaiahCarmona: Porque usar un algoritmo O (n^2) en lugar de un O (n) uno en 10 elementos no es un problema de rendimiento. – Jon
@JohnIsaiahCarmona Porque caes en la trampa de la micro optimización cuando no la necesitas. Mi opinión sobre todo esto es que deberíamos estar atentos a los ruidos obvios, pero los pocos submilisegundos entre A y B no valen la pena hasta que se conviertan en un problema. El código legible y legible es más importante que el rendimiento en la mayoría de los casos. –
Además del hecho de que la clase Queue<T> implementa una cola y la clase List<T> implementa una lista, existe una diferencia de rendimiento.
Cada vez que elimina el primer elemento de List<T>, se copian todos los elementos en la cola. Con solo 20 elementos en la cola, puede que no se note. Sin embargo, cuando elimina el siguiente elemento del Queue<T>, dicha copia no se realiza y siempre será más rápido. Si la cola es larga, la diferencia puede ser significativa.
Quería enfatizar lo que HugoRune ya señaló. Queue es significativamente más rápido que List, donde los accesos de memoria son 1 vs. n para List en este caso de uso. Tengo un caso de uso similar pero tengo cientos de valores y usaré Cola porque es un orden de magnitud más rápido.
Una nota sobre Queue se implementa sobre List: la clave está "implementada". No copia todos los valores a una nueva ubicación de memoria al dequeue, en lugar de usar un buffer circular. Esto se puede hacer en "la parte superior de la lista" sin las penalidades de las copias que implica el uso directo de la lista.
No puede usar un buffer circular a menos que la capacidad sea de tamaño fijo. – Didaxis
Respuesta corta:
Queue<T> es más rápido que List<T> cuando se usa como una cola. List<T> es más rápido que Queue<T> cuando se usa como una lista.
Respuesta larga:
A Queue<T> es más rápido para la operación, que es un (1) operación O desencola. El bloque completo de elementos posteriores de la matriz no se mueve hacia arriba. Esto es posible porque un Queue<T> no necesita facilitar la eliminación de posiciones aleatorias, sino solo desde la parte superior. Por lo tanto, mantiene una cabeza (desde la cual se tira del artículo al Dequeue) y la posición de la cola (a la que se agrega el artículo al Enqueue). Por otro lado, quitar de la parte superior de un List<T> requiere cambiar las posiciones de cada uno de los siguientes elementos. Esto es O (n) - el peor caso si está eliminando de la parte superior, que es lo que es una operación de dequeue. La ventaja de la velocidad puede ser notable si está eliminando en un bucle.
Un List<T> es más performante si necesita acceso indexado, recuperación aleatoria etc. Un Queue<T> tendrá que enumerar totalmente para encontrar la posición de índice apropiado (que no expone IList<T>).
Dicho esto, un Stack<T> vs List<T> está mucho más cerca, no hay diferencia de rendimiento en las operaciones de empujar y estallar. Ambos presionan para terminar y eliminar del extremo de las estructuras de matriz (ambos son O (1)).
Por supuesto se debe utilizar la estructura correcta que revela la intención. En la mayoría de los casos, tendrán un mejor rendimiento ya que están hechos a medida para este propósito. Creo que si no hubiera habido ninguna diferencia en el rendimiento, Microsoft no habría incluido Queue<T> y Stack<T> en el marco de una semántica simplemente diferente. Hubiera sido simplemente extensible fácilmente si ese fuera el caso. Piense en SortedDictionary<K, V> y SortedList<K, V>, los cuales hacen exactamente lo mismo pero se diferencian solo por la característica de rendimiento; ellos encuentran un lugar en BCL.
¿Qué tal en una situación de Add-heavy? –
@AlexanderRyanBaggett No debería hacer ninguna diferencia (mi mejor estimación) pero realmente debería usar la estructura que revela mejor el intento. Ambos le cuentan historias diferentes al desarrollador. – nawfal
'Probablemente' no si no está utilizando más de 20 elementos. Pero puedes medir eso usando la clase StopWatch. – alexn
Depende de su escenario de uso si es importante. lst.RemoveAt (0) hará que la lista reubique todos los elementos mientras que la cola es más inteligente. En teoría, Queue es mejor, pero para asegurarse de que debe medir su caso de uso. –
No puede acceder a una cola por índice. Tienes que usar las entradas que detras y no puedes volverlas a poner. Peek no es una solución, sin embargo Count> 0 puede ser. – Jay