Czy czas stały i amortyzowany stały czas są faktycznie uważane za równoważne?

Muszę napisać RandomQueue, która pozwala na dołączanie i losowe usuwanie w Constant Time (O (1)).

Moją pierwszą myślą było poparcie go jakimś rodzajem Array (wybrałem ArrayList), ponieważ tablice mają stały dostęp za pośrednictwem indeksu.

Przeglądając dokumentację, zdałem sobie sprawę, że dodatki ArrayLists są uważane za amortyzowane stałe, ponieważ dodanie może wymagać realokacji bazowej tablicy, którą jest O (n).

Czy amortyzowany stały czas i stały czas są faktycznie takie same, czy też muszę przyjrzeć się jakiejś strukturze, która nie wymaga pełnej realokacji przy każdym dodaniu?

Pytam o to, ponieważ poza strukturami opartymi na macierzach (które, o ile mi wiadomo, zawsze będą zawierały zamortyzowane dodatki w czasie stałym), nie mogę wymyślić niczego, co spełni wymagania:

• Wszystko oparte na drzewie będzie miało co najwyżej dostęp O (log n)
• Połączona lista może potencjalnie zawierać dodatki O (1) (jeśli zachowane jest odniesienie do ogona), ale losowe usunięcie powinno być co najwyżej O (n).

Oto pełne pytanie; na wypadek, gdy przeszklę niektóre ważne szczegóły:

Zaprojektuj i zaimplementuj RandomQueue. Jest to implementacja interfejsu kolejki, w której operacja remove () usuwa element losowo wybierany równomiernie spośród wszystkich elementów znajdujących się w kolejce. (Pomyśl o RandomQueue jako o torbie, w której możemy dodawać elementy lub sięgać i ślepo usuwać niektóre losowe elementy.) Operacje add (x) i remove () w RandomQueue powinny działać w stałym czasie na operację.

Amortyzowaną Stały czas można prawie zawsze uznać za równoważny Stałemu Czasowi i bez znajomości specyfiki aplikacji i rodzaju użycia, które zamierzasz zrobić w tej kolejce, istnieje duże prawdopodobieństwo, że będziesz objęty ubezpieczeniem.

Lista tablic ma pojęcie pojemności , która jest w zasadzie równa największemu rozmiarowi / długości / liczbie elementów, jaki kiedykolwiek był od niej wymagany. Tak więc, co się stanie, na początku lista tablic będzie się ponownie przenosić, aby zwiększyć jej pojemność w miarę dodawania do niej przedmiotów, ale w pewnym momencie średnia liczba przedmiotów dodawanych w jednostce czasu nieuchronnie będzie odpowiadać średniej liczbie przedmiotów usuwane na jednostkę czasu (w przeciwnym razie i tak zabraknie pamięci), w tym momencie tablica przestanie się ponownie przydzielać, a wszystkie dodatki zostaną spełnione w stałym czasie O (1).

Należy jednak pamiętać, że domyślnie losowe usuwanie z listy tablic nie jest O (1), jest O (N), ponieważ listy tablic przenoszą wszystkie elementy po usuniętym elemencie o jedną pozycję w dół, aby zająć miejsce usuniętego pozycja. Aby osiągnąć O (1), musisz zastąpić domyślne zachowanie, aby zastąpić usunięty element kopią ostatniego elementu z listy tablic, a następnie usunąć ostatni element, aby żadne elementy nie zostały przeniesione. Ale jeśli to zrobisz, nie będziesz już mieć kolejki.

Wydaje się, że pytanie dotyczy konkretnie stałego czasu, a nie zamortyzowanego stałego czasu . Jeśli chodzi o cytowane pytanie, nie, nie są one faktycznie takie same *. Czy jednak znajdują zastosowanie w rzeczywistych zastosowaniach?

Typową kwestią związaną ze stałą amortyzacją jest to, że czasami trzeba spłacić zakumulowany dług. Tak więc, chociaż wstawki są zasadniczo stałe, czasem trzeba ponieść koszty związane z ponownym wstawianiem wszystkiego po przydzieleniu nowego bloku.

Tam, gdzie różnica między stałym czasem a zamortyzowanym stałym czasem jest istotna dla aplikacji, zależy od tego, czy ta sporadycznie bardzo niska prędkość jest dopuszczalna. W przypadku bardzo dużej liczby domen jest to ogólnie w porządku. Zwłaszcza jeśli kontener ma efektywny maksymalny rozmiar (np. Pamięci podręczne, bufory tymczasowe, kontenery robocze), możesz skutecznie opłacić koszty tylko raz podczas wykonywania.

W odpowiedzi na krytyczne zastosowania czasy te mogą być nie do przyjęcia. Jeśli musisz spełnić krótkoterminową gwarancję realizacji, nie możesz polegać na algorytmie, który czasami go przekroczy. Pracowałem już nad takimi projektami, ale są one niezwykle rzadkie.

Zależy to również od tego, jak wysoki jest ten koszt. Wektory mają dobre wyniki, ponieważ ich koszt realokacji jest stosunkowo niski. Jeśli jednak przejdziesz do mapy skrótów, przeniesienie może być znacznie wyższe. Chociaż znowu, w przypadku większości aplikacji prawdopodobnie w porządku, szczególnie w przypadku serwerów o dłuższym okresie eksploatacji z górną granicą na elementach w kontenerze.

* Jest tu jednak pewien problem. Aby dowolny pojemnik ogólnego przeznaczenia był stałym czasem wkładania, jedna z dwóch rzeczy musi zawierać:

• Pojemnik musi mieć ustalony maksymalny rozmiar; lub
• możesz założyć, że przydział pamięci dla poszczególnych elementów to stały czas.

To zależy - od tego, czy optymalizujesz przepływność, czy opóźnienie:

• Systemy wrażliwe na opóźnienia wymagają stałej wydajności. W takim scenariuszu musimy podkreślić najgorsze zachowanie systemu. Przykładami są miękkie systemy czasu rzeczywistego, takie jak gry, które chcą osiągnąć stałą liczbę klatek na sekundę, lub serwery sieciowe, które muszą wysłać odpowiedź w ściśle określonym czasie: marnowanie cykli procesora jest lepsze niż spóźnianie się.
• Systemy zoptymalizowane pod kątem przepustowości nie dbają o okazjonalne przeciągnięcia, o ile maksymalna ilość danych może być przetwarzana w długim okresie. Tutaj interesuje nas przede wszystkim amortyzacja wyników. Zasadniczo dzieje się tak w przypadku kruszenia numerów lub innych zadań przetwarzania wsadowego.

Pamiętaj, że jeden system może mieć różne komponenty, które muszą być podzielone na różne kategorie. Na przykład nowoczesny procesor tekstowy miałby wątek interfejsu wrażliwy na opóźnienia, ale wątki zoptymalizowane pod kątem przepustowości do innych zadań, takich jak sprawdzanie pisowni lub eksport plików PDF.

Ponadto złożoność algorytmiczna często nie ma tak dużego znaczenia, jak mogłoby się wydawać: gdy problem jest ograniczony do określonej liczby, wówczas rzeczywiste i mierzone charakterystyki wydajności są ważniejsze niż zachowanie „dla bardzo dużego n ”.

Jeśli zostaniesz poproszony o algorytm „zamortyzowanego stałego czasu”, Twój algorytm może czasem zająć dużo czasu. Na przykład, jeśli używasz std :: vector w C ++, taki wektor może mieć przydzielone miejsce dla 10 obiektów, a gdy przydzielisz 11 obiekt, przydzielane jest miejsce na 20 obiektów, 10 obiektów jest kopiowanych, a 11 dodawany, co zajmuje dużo czasu. Ale jeśli dodasz milion obiektów, możesz mieć 999,980 szybkich i 20 powolnych operacji, przy czym średni czas jest szybki.

Jeśli zostaniesz poproszony o algorytm „stałego czasu”, twój algorytm musi być zawsze szybki, dla każdej operacji. Byłoby to ważne w przypadku systemów w czasie rzeczywistym, w których może być wymagana gwarancja, że ​​każda operacja jest zawsze szybka. „Stały czas” bardzo często nie jest potrzebny, ale zdecydowanie nie jest tym samym, co „zamortyzowany stały czas”.