cola de .NET rendimiento ElementAt

Question

estoy teniendo un tiempo duro con partes de mi código:

private void UpdateOutputBuffer() 
    { 
     T[] OutputField = new T[DisplayedLength]; 

     int temp = 0; 
     int Count = HistoryQueue.Count; 
     int Sample = 0; 

     //Then fill the useful part with samples from the queue 
     for (temp = DisplayStart; temp != DisplayStart + DisplayedLength && temp < Count; temp++) 
     { 
      OutputField[Sample++] = HistoryQueue.ElementAt(Count - temp - 1); 
     } 

     DisplayedHistory = OutputField; 
    } 

Se necesita la mayor parte del tiempo en el programa. La cantidad de elementos en HistoryQueue es de 200k +. ¿Podría ser porque la cola en .NET se implementa internamente como una lista vinculada?

¿Cuál sería una mejor forma de solucionar esto? Básicamente, la clase debería actuar como un FIFO que comienza a soltar elementos a ~ 500k muestras y podría elegir elementos DisplayLong y ponerlos en OutputField. Estaba pensando en escribir mi propia Cola que usaría un buffer circular.

El código funcionó bien para contar valores más bajos. DisplayedLength es 500.

Gracias,

David

Answer 1

Personalmente no creo que una cola es lo que estás buscando, pero su patrón de acceso es aún peor. Use iteradores si desea acceso secuencial:

foreach(var h in HistoryQueue.Skip(DisplayStart).Take(DisplayedLength).Reverse()) 
    // work with h 

Answer 2

Absolutamente la estructura de datos incorrecta para usar aquí. ElementAt es O (n), lo que hace que su bucle O (n). Deberías usar algo más en lugar de una cola.

Answer 3

Queue no tiene un método ElementAt. Supongo que está obteniendo esto a través de Linq, y que simplemente está haciendo una iteración forzada sobre n elementos hasta que llegue al índice deseado. Obviamente, esto se ralentizará a medida que la colección se agrande. Si ElementAt representa un patrón de acceso común, elija una estructura de datos a la que se pueda acceder mediante el índice, p. un Array.

Answer 4

Sí, la lista enlazada es casi con certeza el problema. Hay una razón por la cual Queue<T> no implementa IList<T> :) (Dicho esto, creo que Stack<T> se implementa utilizando una matriz, y que aún no implementa IList<T>. podría proporcionar acceso aleatorio eficiente, pero no es así.)

no puedo decir fácilmente qué parte de la cola que está tratando de visualizar, pero sospecho fuertemente que usted podría simplificar el método y hacerlo más eficiente de usar algo como:

T[] outputField = HistoryQueue.Skip(...) /* adjust to suit requirements... */ 
           .Take(DisplayedLength) 
           .Reverse() 
           .ToArray(); 

Eso todavía tendrá que saltar sobre una gran cantidad de artículos individualmente, pero al menos solo tendrá que hacerlo una vez.

¿Has pensado en usar un LinkedList<T> directamente? Eso haría que sea mucho más fácil leer los elementos del final de la lista con mucha facilidad.

Construir su propia cola limitada utilizando un búfer circular no sería difícil, por supuesto, y bien podría ser la mejor solución a largo plazo.

Answer 5

Si tiene que ser capaz de hacer estallar/pulsador en cada extremo y han indexado acceso que realmente necesita una implementación de Deque (forma matricial múltiple).Si bien no hay implementación en el BCL, existen muchos terceros (para comenzar, si es necesario, puede implementar el suyo más adelante).