Il modo (quasi) migliore per gestire un elenco con elementi in movimento

Question

Ecco la situazione:
Ho una lista che memorizza le stringhe che sono in realtà numeri e possono diventare piuttosto grandi (centinaia di milioni di elementi).
Memorizzo i numeri come stringa perché esiste un'opzione per visualizzare alcune informazioni aggiuntive che sono testo.

Poiché ciò richiede molta memoria per l'archiviazione, ho deciso di archiviare solo un massimo di 5 milioni di elementi. (questo richiederà solo circa 250-300 mb).

L'elenco viene riempito dall'output di un calcolo. Se viene trovato un numero verrà aggiunto alla lista, questo numero è sempre più grande degli articoli esistenti.

Quando l'elenco ha raggiunto 5 mil, desidero rimuovere il primo elemento e aggiungere il nuovo elemento all'elenco.

piace:

// Why is this so freaking slow??? 
    if (_result.Count == 5000000) 
     _result.RemoveAt(0); 
    _result.Add(result); 

Come si può leggere nel commento, questo è molto, molto, molto lento. Ha ridotto la mia prestazione di 15 volte. Dove ci sono voluti 2 minuti ora ci vogliono circa 30.

Ho provato alcune cose con linq come .Skip(1).ToList ma questo ricreerà la lista ed è quindi ancora più lento.

L'elenco deve rimanere nel giusto ordine, quindi la sovrascrittura per indice non è un'opzione (a meno che non si possa spiegare un buon lavoro in giro).

La mia domanda:
C'è qualche modo decente per farlo?

Ho davvero bisogno delle prestazioni qui poiché potrebbe essere necessario controllare circa 10000000000 numeri. Questo può prendere un giorno naturalmente, ma un mese è un po 'troppo :(

bisogno di ulteriori informazioni, non esitate a chiedere, sarò felice di fornire

Soluzione:..
Questo esegue O (1)

// Set the _result 
    Queue<object> _result = new Queue<object>(5000000); 

    /// Inside the method 
    // If the count has reach it's max, dequeue the first item 
    if (_result.Count == 5000000) 
     _result.Dequeue(); 
    _result.Enqueue(result); 

Answer 1

Ti capita mai di riordinare gli elementi? Se non lo fai, una coda circolare funzionerebbe abbastanza bene.

System.Collections.Generic.Queue è uno, ho appena controllato due volte.

Per espandere sui benefici di una coda, questo è il RemoveAt implementazione (approssimativamente):

for (int i = 1; i < count; i++) 
    items[i-1] = items[i]; 
count--; 

Perché list[0] è sempre il primo elemento, si deve spostare tutto per rimuovere il primo elemento.

Al contrario, una coda traccia il primo elemento separatamente. Questo cambia il codice sopra a questo:

head++ 

Answer 2

io suggerisco di implementare al meglio una coda circolare. poi si spinge ogni int alla fine della coda e quando si esaurisce lo spazio (determinata dalla dimensione fissa) allora ogni l'operazione richiederà di far scoppiare il primo e premere sul fondo. O(1).

Vantaggio contro array è che non si prealloca lo spazio finché non è necessario. Ma, infine, considera VERAMENTE di memorizzare valori come, beh, int. Indipendentemente dalle operazioni che eseguirai, dovresti sempre memorizzare i numeri come numeri.

Answer 3

Perché non preallocare la matrice e disporre di due numeri interi, che indicano l'inizio e la fine della matrice. Ovviamente, entrambi inizierebbero uguali a 0. Una volta che sei a corto di spazio, inizi a ricominciare.

Un esempio di classe pseudo helper:

class CircularArray 
{ 
    const int maxSize = 5000000; 
    private int[] arr = new int[maxSize]; 
    private int start = 0; 
    private int end = 0; 

    public void Add(int value) 
    { 
    int newEnd = (end + 1) % maxSize; 
    if (newEnd == start) 
     start = (start + 1) % maxSize; 
    end = newEnd; 
    arr[end] = value; 
    } 

    public int Get(int index) 
    { 
    int newIndex = (start + index) % maxSize; 
    return arr[newIndex]; 
    } 
} 

Answer 4

Quando si rimuove il primo elemento in un oggetto Array, tutti gli altri elementi vengono spostati verso il basso. Una coda circolare consente di mantenere l'ordine originale ed eliminare i turni che si verificano quando si rimuove la testa dell'elenco.

Answer 5

may be LinkedList<T> Class potrebbe esserti di aiuto? La rimozione e l'aggiunta a entrambe le estremità è operazione O (1), ma l'iterazione sarà O (n), o se hai bisogno di O (1) all'accesso puoi usare Dictionary o SortedDictionary Un'altra implementazione personalizzata è QueueDictionary, l'ho usata quando ho bisogno dell'operazione O (1) su entrambi aggiungere e rimuovere alla fine o iniziare (coda/coda di rondini) e all'accesso a un valore. QueueDictionary qui: How would I implement a QueueDictionary, a combination of Queue and Dictionary in C#?