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

16

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ę.

algorithms complexity

— Carcigenicate
źródło

Czy przypisanie określa sposób przeprowadzania losowych operacji usuwania? Czy masz indeks do usunięcia lub odwołanie do elementu kolejki?

Nie podaje żadnych szczegółów. Wymagania są tylko strukturą, która implementuje interfejs kolejki i ma dodatki O (1) do dodawania i usuwania.

— Carcigenicate

Nawiasem mówiąc - tablica o zmiennym rozmiarze z rosnącym O (n) niekoniecznie ma dodatek O (1): zależy to od tego, jak rozwijamy macierz. Rosnące o stałą kwotę a jest nadal O (n) do dodania (mamy 1/aszansę na operację O (n)), ale rosnące o stały czynnik a > 1jest amortyzowane przez O (1) do dodania: mamy (1/a)^nszansę na O (n) operacja, ale to prawdopodobieństwo zbliża się do zera dla dużej n.

— dniu

ArrayLists używają tych ostatnich, prawda?

— Carcigenicate

1

Autor pytania (ja) myślał o zamortyzowanym rozwiązaniu o stałym czasie. Wyjaśnię to w następnym wydaniu. (Chociaż w najgorszym przypadku stały czas można osiągnąć tutaj za pomocą techniki amortyzacji .)

— Pat Morin

10

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.

— Mike Nakis
źródło

1

Cholera, dobry punkt na przeprowadzki; Nie brałem tego pod uwagę. A ponieważ losowo usuwamy elementy, czy to nie oznacza technicznie, że w tym sensie nie jest już kolejką?

— Carcigenicate

Tak, to znaczy, że tak naprawdę nie traktujesz tego jako kolejki. Ale nie wiem, jak planujesz znaleźć elementy do usunięcia. Jeśli twój mechanizm ich znalezienia oczekuje, że będą obecne w kolejce w kolejności, w jakiej zostały dodane, oznacza to, że nie masz szczęścia. Jeśli nie obchodzi cię, czy kolejność przedmiotów jest zniekształcona, nic ci nie jest.

— Mike Nakis,

2

Oczekuję, że RandomQueuezaimplementuję Queueinterfejs, a dostarczona removemetoda losowo usunie zamiast wyskakiwać z głowy, więc nie powinno być żadnego sposobu polegania na konkretnej kolejności. Myślę, że biorąc pod uwagę losowy charakter tego, użytkownik nie powinien oczekiwać, że zachowa on określoną kolejność. W celu wyjaśnienia zacytowałem zadanie. Dziękuję Ci.

— Carcigenicate

2

Tak, wygląda na to, że wszystko będzie dobrze, jeśli tylko upewnisz się, że usunięcie elementu zostało wykonane tak, jak zasugerowałem.

— Mike Nakis,

Jeszcze jedna rzecz, jeśli nie masz nic przeciwko. Zastanowiłem się nad tym bardziej i wydaje się, że nie jest możliwe, aby mieć zarówno „prawdziwe” dodatki O (1), jak i „prawdziwe” O (1) losowe usuwanie; będzie to kompromis między 2. Masz albo pojedynczo przydzieloną strukturę (jak tablica), która daje usunięcie, ale nie dodaje, lub strukturę przydzieloną do porcji, taką jak lista połączona, która dodaje, ale nie usuwa. Czy to prawda? Jeszcze raz dziękuję.

— Carcigenicate

14

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.

— edA-qa mort-ora-y
źródło

„serwer wątroby” wydaje się dziwnym frazowaniem. Masz na myśli „serwer na żywo”?

— Pieter Geerkens,

6

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 ”.

— amon
źródło

Niestety mam bardzo małe doświadczenie. Pytanie kończy się następująco: „Operacje add (x) i remove () w RandomQueue powinny działać w stałym czasie na operację”.

— Carcigenicate

2

@Carcigenicate, chyba że wiesz, że system jest wrażliwy na opóźnienia, użycie amortyzacji złożoności do wyboru struktury danych powinno być absolutnie wystarczające.

— amon

Mam wrażenie, że może to być ćwiczenie programistyczne lub test. I z pewnością nie jest to łatwe. Absolutnie prawda, że bardzo rzadko ma to znaczenie.

— gnasher729,

1

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”.

— gnasher729
źródło