coda .NET prestazioni ElementAt

Question

Sto avendo un momento difficile con le parti del mio codice:

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; 
    } 

Ci vuole maggior parte del tempo nel programma. Il numero di elementi in HistoryQueue è 200k +. Ciò potrebbe essere dovuto al fatto che la coda in .NET è implementata internamente come elenco collegato?

Quale sarebbe un modo migliore di fare questo? Fondamentalmente, la classe dovrebbe comportarsi come una FIFO che inizia a rilasciare elementi a ~ 500k di campioni e potrei scegliere gli elementi di DisplayedLength e inserirli in OutputField. Stavo pensando di scrivere la mia coda che userebbe un buffer circolare.

Il codice ha funzionato correttamente per contare i valori più bassi. DisplayedLength è 500.

Grazie,

David

Answer 1

Personalmente non credo che una coda è quello che stai cercando, ma il vostro modello di accesso è ancora peggio. Utilizzare iteratori se si desidera l'accesso sequenziale:

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

Answer 2

Assolutamente la struttura dati errata da utilizzare qui. ElementAt è O (n), che rende il loop O (n). Dovresti usare qualcos'altro invece di una coda.

Answer 3

La coda non ha un metodo ElementAt. Immagino che tu stia ottenendo questo tramite Linq e che stia semplicemente facendo un'iterazione forzata su n elementi fino a raggiungere l'indice desiderato. Questo ovviamente sta andando a rallentare man mano che la collezione diventa più grande. Se ElementAt rappresenta un modello di accesso comune, quindi selezionare una struttura di dati a cui è possibile accedere tramite indice, ad es. uno Array.

Answer 4

Sì, la lista dei collegamenti è quasi certamente il problema. C'è una ragione per cui IList<T> non è implementato IList<T> :) (Detto questo, credo che lo Stack<T> sia implementato utilizzando un array e che non implementi ancora IList<T>. È fornire un accesso casuale efficiente, ma non è così.)

non posso facilmente dire che parte della coda si sta cercando di visualizzare, ma ho il forte sospetto che si potrebbe semplificare il metodo di e renderlo più efficiente utilizzando qualcosa di simile:

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

Questo dovrà ancora saltare un numero enorme di elementi individualmente, ma almeno lo dovrà fare solo una volta.

Hai mai pensato di utilizzare direttamente uno LinkedList<T>? Ciò renderebbe molto più facile leggere gli articoli dalla fine della lista molto facilmente.

Costruire la propria coda limitata utilizzando un buffer circolare non sarebbe difficile, ovviamente, e potrebbe essere la soluzione migliore a lungo termine.

Answer 5

Se è necessario eseguire il pop/push a entrambe le estremità, e, è necessario disporre di un accesso indicizzato per l'implementazione di Deque (modulo di array multipli).Sebbene non ci siano implementazioni nel BCL, ce ne sono molte di terze parti (per iniziare, se necessario, è possibile implementarle in seguito).