Wybór klasy do stworzenia rodzaju kolejki FIFO

Potrzebuję klasy loggera, która będzie pamiętała ostatnie 50 000 wpisów
Czy lista

List<String> lista

się do tego nadaje?

chcę tylko 3 rzeczy: szybkie dodawanie nowych zdarzeń, szybkie usuwanie nadwyżki zdarzeń, zachowanie kolejności zdarzeń
czy wykonanie:

lista.RemoveRange(0, list.Count - 50000); // zostawienie tylko ostatnich 50'000 wpisów

będzie wystarczająco szybkie czy spowoduje mozolne przeindeksowanie wszystkich innych elementów listy?
może jakiś pomysł na wykorzystanie czegoś innego?

aha, zamiast "String" prawdopodobnie będzie wykorzystany "long" - przepraszam za pomyłkę

będzie wystarczająco szybkie czy spowoduje mozolne przeindeksowanie wszystkich innych elementów listy?

To jest lista a nie tablica. Będzie równie szybkie jak usunięcie jednego elementu.

A czemu, skoro już chcesz kolejkę FIFO to nie użyjesz jak bóg przykazał Queue<long>?

MSM napisał(a)

A czemu, skoro już chcesz kolejkę FIFO to nie użyjesz jak bóg przykazał Queue<long>?

hmm, pewnie dlatego że zapomniałem o istnieniu czegoś takiego :-|
a użycie Queue zamiast List będzie choć trochę szybsze? potrzebuję co jakiś czas (niezbyt często) użyć tej kolejki jako listy i wyświetlić całą zawartość - czy Queue się do tego nadaje?

aha i rozumiem że w kolejce żeby usunąć pierwszy element trzeba użyć Dequeue które przy okazji zwraca pierwszy element, który w zasadzie nie jest mi potrzebny - czy nie będzie to wówczas trochę wolniejsze niż zwykłe usunięcie elementu w przypadku listy?

wiem że to nic nie znaczące optymalizacje ale te operacje będą się wykonywać kilkaset razy na sekundę i nie chcę żeby choć trochę niepotrzebnie zamulały komputer

Tutaj masz cały interfejs queue - http://msdn.microsoft.com/en-us/library/kf7596ed.aspx.
Jeśli chodzi o użycie jej jako listy - nie da się w 100% prosto, ale CopyTo albo ToArray powinno ci (chyba) wystarczyć.

żeby usunąć pierwszy element trzeba użyć Dequeue które przy okazji zwraca pierwszy element, który w zasadzie nie jest mi potrzebny - czy nie będzie to wówczas trochę wolniejsze niż zwykłe usunięcie elementu w przypadku listy?

Możliwe że będzie nawet szybsze, bo kolejka może być optymalizowana specjalnie do takich funkcji. A to czy zwraca czy nie zwraca naprawdę nie spowalnia pracy kolejki.

Teraz małe wtf 0_0

Specjalnie dla ciebie przeprowadziłem małe testy :D Oto kod testowy: (nie chciało mi się dokumentować, chyba wiadomo co on robi)

    
[STAThread]
static void Main(string[] args)
        {
            Queue<long> kolejka = new Queue<long>(); ;
            List<long> lista = new List<long>();
            string wynik;

            for (int i = 0; i < 10000; i++)
            {
                kolejka.Enqueue((long)i);
                lista.Add((long)i);
            }

            Stopwatch watch = new Stopwatch();
            watch.Start();

            for (int i = 0; i < 10000; i++) kolejka.Dequeue();
            watch.Stop();
            wynik = "kolejka: " + watch.Elapsed.ToString();

            watch.Reset();
            watch.Start();

            for (int i = 0; i < 10000; i++) lista.Remove(i);
            watch.Stop();

            wynik += "\nlista:   " + watch.Elapsed.ToString();

            Console.WriteLine(wynik); // wypisuje i...
            Clipboard.SetText(wynik); // kopiuje do schowka wynik;

            Console.Read();
        }

Przetestuj sam jeśli nie wierzysz, ale oto wyniki: (myślałem nawet że gdzieś się pomyliłem o zero albo... dwa zera)

kolejka: 00:00:00.0008904
lista:   00:00:00.0384543

Jeszcze jakieś wątpliwości? :D

dzięki wielkie, dla pewności przerobiłem jeszcze test tak żeby symulował prawdziwe warunki, czyli najpierw uzupełniłem kolejkę i listę o 100'000 elementów a następnie 100'000 razy dodawałem nowy element usuwając jednocześnie pierwszy i wyniki jeszcze bardziej pozbawiają wątpliwości:

kolejka: 00:00:00.0018952
lista:   00:00:03.1513150 (!)

sprawdziłem też ile czasu zajmuje przepisanie zawartości kolejki i listy do stringa i uzyskany wynik też jest satysfakcjonujący choć już z malutką przewagą dla listy:

wyświetlenie kolejki: 00:00:00.0285576
wyświetlenie listy:   00:00:00.0233174

dodając jedno zero:

kolejka: 00:00:00.0104035
lista:   00:01:03.7104764

czyli ponad minuta kontra dziesiąta część sekundy - było jednak o co walczyć

Zamiast się bawić w mierzenie czasu, nie prościej użyć MSDN:

Queue<(Of <(T>)>)..::.Dequeue Method
This method is an O(1) operation.

List<(Of <(T>)>)..::.Remove Method
This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

A jeśli zamiast używać do usuwania z List naiwnego Remove użyje się RemoveAt, to która kolekcja wygrywa? ;)

somekind napisał(a)

A jeśli zamiast używać do usuwania z List naiwnego Remove użyje się RemoveAt, to która kolekcja wygrywa? ;)

oczywiście pomiary wykonywane na metodzie RemoveAt
na Remove nie sprawdzałem, ale patrząc na wyniki MSM jest jeszcze gorzej

Deti: faktycznie łatwiej ;) ale nie wszystko można sprawdzić w ten sposób

MSDN podaje też że dla RemoveAt:
This method is an O(n) operation, where n is (Count - index)

z czego wychodziłoby że dla Listy usuwanie ostatniego elementu jest równie szybkie jak usuwanie pierwszego w kolejce, ale nie chce mi się już tego sprawdzać
poza tym musiałbym wtedy wsuwać nowe elementy na sam początek listy czego nie wiem jaka jest złożoność a nie chce mi się sprawdzać

w każdym razie temat zakończony

to troszke dziwne bo mi wychodzi ze metoda listy RemoveAt jest szybsza od kolejki. Cos pokreciles i sprawdzales na zwyklym Remove

Taka złożoność dla RemoveAt oznacza, że wszystkie elementy w tablicy które leżą za elementem usuwanym są przesuwane o jedną pozycję w dół.

HideYoshi: uzupełnij najpierw kolejkę i listę czymś bo jak robisz na pustych dodawanie i usuwanie jednego elementu to nie dziwne

grymas napisał(a)

z czego wychodziłoby że dla Listy usuwanie ostatniego elementu jest równie szybkie jak usuwanie pierwszego w kolejce

Właśnie tak jest.

grymas napisał(a)

oczywiście pomiary wykonywane na metodzie RemoveAt
na Remove nie sprawdzałem, ale patrząc na wyniki MSM jest jeszcze gorzej

grymas napisał(a)

HideYoshi: uzupełnij najpierw kolejkę i listę czymś bo jak robisz na pustych dodawanie i usuwanie jednego elementu to nie dziwne

he? kolejka i lista byla wypelniona. Tylko twoje czasy pokazuja ze uzywales metody Remove a nie RemoveAt

te czasy pokazują że używałem metody Remove w takim samym stopniu jak twój nick pokazuje że jesteś debilem

Misie, o co Wy się jeszcze bijecie?
Jeśli przy pomocy RemoveAt usuwamy z listy od końca, to jest tak samo szybka jak kolejka, a jeśli od początku, to jest znacznie wolniejsza.

dokładnie, ale Yoshi ma jakąś magiczną klasę List która jest dużo szybsza od naszych

w dodatku nawet jakbym użył (czego nie zrobiłem) Remove zamiast RemoveAt to w przypadku usuwania pierwszego elementu listy nie miałoby to znaczenia bo obie funkcje mają w tym przypadku tą samą złożoność i czasy byłyby dokładnie takie same