(prawie) najlepszy sposób zarządzania listą z przesunięciem elementów

Question

Oto sytuacja:
Mam listę ciągów sklepu, które w rzeczywistości są liczbami i mogą stać się całkiem spore (setki milionów pozycji).
Przechowuję liczby jako ciąg znaków, ponieważ istnieje opcja wyświetlania dodatkowych informacji, którymi są tekst.

Ponieważ zajmuje to dużo pamięci, zdecydowałem, że będę przechowywać maksymalnie 5 milionów sztuk. (zajmie to tylko około 250-300mb).

Lista jest wypełniona wynikiem obliczeń. Jeśli liczba zostanie znaleziona, zostanie dodana do listy, ta liczba jest zawsze większa niż istniejące elementy.

Gdy lista osiągnie 5 mil, chcę usunąć pierwszy element i dodać nowy element do listy.

lubię:

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

Jak można przeczytać w komentarzu, to jest bardzo, bardzo, bardzo powoli. Po prostu zmniejszyłem moją wydajność 15 razy. Gdzie zajęło to 2 minuty zajmuje teraz około 30.

Próbowałem kilku rzeczy z linq jak .Skip(1).ToList, ale to odtworzy listę i dlatego jest jeszcze wolniejsze.

Lista musi pozostać we właściwej kolejności, więc nadpisanie według indeksu nie jest opcją (chyba że można wytłumaczyć miłą pracę).

Moje pytanie:
Czy jest jakiś przyzwoity sposób na zrobienie tego?

Naprawdę potrzebuję wydajności tutaj, ponieważ może zajść potrzeba sprawdzenia około 10000000000 numerów. Może to potrwać dzień oczywiście, ale miesiąc jest nieco zbyt dużo :(

potrzebują dodatkowych informacji, nie krępuj się zapytać, będę szczęśliwy dostarczyć

. Rozwiązanie:.
ten wykonuje 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

Czy kiedykolwiek zmienić kolejność elementów? Jeśli nie, kolejka cykliczna działałaby całkiem dobrze.

System.Collections.Generic.Queue jest jeden, właśnie sprawdziłem.

Aby rozwinąć na korzyści z kolejki, jest to realizacja (w przybliżeniu) RemoveAt:

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

Ponieważ list[0] zawsze jest pierwszy element, trzeba przenieść wszystko, aby usunąć pierwszy element.

W przeciwieństwie do tego kolejka śledzi pierwszy element osobno. To zmienia powyższy kod do tego:

head++ 

Answer 2

będę proponujemy, aby lepiej realizować okrągły kolejki. następnie należy wcisnąć każdy int na końcu kolejki, a kiedy zabraknie miejsca (określanej przez stałej wielkości), a następnie każdy operacja będzie wymagać pop pierwsze i wypchnąć na dole.

Advantage vs. Array to to, że nie zwalniasz miejsca, dopóki nie będzie potrzebne. Ale, ostatecznie, rozważ NAPRAWDĘ, aby przechowywać ints jako, no cóż, ints. Bez względu na to, jakie operacje wykonasz, zawsze przechowuj liczby jako liczby.

Answer 3

Dlaczego nie dokonujesz wstępnej alokacji tablicy i masz dwie liczby całkowite, wskazujące początek i koniec tablicy. Oczywiście oboje zaczynają od zera równego 0. Gdy zabraknie ci miejsca, po prostu zaczynasz się owijać.

Przykładem klasa psuedo pomocnik:

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

Po usunięciu pierwszego elementu w ArrayList, wszystkie inne elementy są przesunięte w dół. Okrągła kolejka pozwoliłaby zachować oryginalną kolejność i wyeliminować czasochłonne przesunięcia, które wystąpiły po usunięciu nagłówka listy.

Answer 5

Może być LinkedList<T> Class może ci pomóc? Usuwanie i dodawanie na obu końcach jest operacją O (1), ale iteracja będzie O (n), lub jeśli potrzebujesz O (1) podczas uzyskiwania dostępu, możesz użyć Dictionary lub SortedDictionary Inną niestandardową implementacją jest QueueDictionary, użyłem jej gdy potrzebuję operacji O (1) na dodawanie i usuwanie na końcu lub na początku (kolejka/wycofanie) i na dostęp do wartości. QueueDictionary tutaj: How would I implement a QueueDictionary, a combination of Queue and Dictionary in C#?