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

Amortyzowany stały czas prawie zawsze można uznać za równoważny ze stałym czasem i bez znajomości specyfiki aplikacji i rodzaju użycia, które zamierzasz wykonać w tej kolejce, najprawdopodobniej zostaniesz objęty.

Lista tablic ma pojęcie pojemności , która jest w zasadzie równa największemu rozmiarowi / długości / liczbie elementów, które do tej pory kiedykolwiek był od niego wymagany. Tak więc, na początku lista tablic będzie się zmieniać, aby zwiększyć swoją pojemność w miarę dodawania do niej elementów, ale w pewnym momencie średnia liczba elementów dodawanych w jednostce czasu nieuchronnie będzie pasować do średniej liczby elementów usuwane na jednostkę czasu (w przeciwnym razie i tak w końcu zabraknie pamięci), w którym to momencie tablica przestanie się ponownie przydzielać, a wszystkie dołączenia zostaną spełnione w stałym czasie O (1).

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

Komentarze

• Cholera, dobra uwaga na temat usuwania; Nie ' nie brałem tego pod uwagę. A ponieważ ' usuwamy elementy w sposób losowy, czy ' nie oznacza to technicznie ' Czy i tak nie jest już kolejką w tym sensie?
• Tak, to znaczy, że tak naprawdę nie traktujesz jej jako kolejki. Ale nie wiem, jak planujesz znaleźć elementy do usunięcia. Jeśli Twój mechanizm ich wyszukiwania oczekuje, że będą one obecne w kolejce w kolejności, w jakiej zostały dodane, to nie masz szczęścia.Jeśli nie obchodzi Cię, czy kolejność elementów ulegnie zniekształceniu, to wszystko w porządku.
• Oczekujemy, że mój RandomQueue zaimplementuje Queue i dla dostarczonej metody remove do losowego usuwania zamiast otwierania głowy, więc nie powinno być ' W żaden sposób nie można polegać na konkretnym zamówieniu. Myślę, że biorąc pod uwagę losowy charakter tego, użytkownik nie powinien ' oczekiwać od niego zachowania określonej kolejności. Zacytowałem to zadanie w moim pytaniu dla wyjaśnienia. Dziękuję.
• Tak, wygląda na to, że wszystko będzie dobrze, jeśli tylko upewnisz się, że usunięcie elementu zostało wykonane tak, jak sugerowałem.
• Ostatnia rzecz, jeśli nie ' nieważne. ' Przemyślałem to więcej i nie ' wydaje się, że tak ' można mieć zarówno ” true ” O (1) dodatki, jak i ” true ” O (1) usuwanie losowe; to ' będzie to kompromis między 2. Masz albo pojedynczo alokowaną strukturę (jak tablica), która umożliwia usunięcie, ale nie dodaje, albo strukturę alokowaną fragmentem, taką jak Linked- Lista zawierająca dodatki, ale nie usuwająca. Czy to prawda? Jeszcze raz dziękuję.

Pytanie wydaje się prosić o stały czas, a nie o amortyzowany stały czas . Zatem w odniesieniu do cytowanego pytania nie, nie są one w rzeczywistości takie same *. Czy jednak występują one w rzeczywistych zastosowaniach?

Typowym problemem z amortyzowaną stałą jest to, że czasami trzeba spłacić narosły dług. Więc chociaż wstawienia są generalnie stałe, czasami trzeba ponieść narzut ponownego wstawiania wszystkiego ponownie, gdy przydzielany jest nowy blok.

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

W przypadku aplikacji krytycznych te czasy mogą być nie do zaakceptowania. Jeśli musisz spełnić krótką gwarancję czasu, 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 zwykle działają dobrze, ponieważ ich koszt ponownej alokacji jest stosunkowo niski. Jeśli jednak przejdziesz do mapy skrótów, realokacja może być znacznie wyższa. Chociaż znowu, dla większości aplikacji prawdopodobnie w porządku, szczególnie dłuższe serwery z górną granicą elementów w kontenerze.

* Jest tu jednak pewien problem. Aby stworzyć dowolny kontener ogólnego przeznaczenia być stałym czasem wstawiania jedna z dwóch rzeczy musi być przechowywana:

• Kontener musi mieć ustalony maksymalny rozmiar; lub
• możesz założyć, że alokacja pamięci poszczególnych elementów jest stała w czasie .

Komentarze

• ” serwer wątroby ” wydaje się dziwne w użyciu tutaj. Czy masz na myśli ” serwer na żywo ” być może?

To zależy – od tego, czy optymalizujesz przepustowość, czy opóźnienie:

• Opóźnienie – wrażliwe systemy wymagają spójnej wydajności. W takim scenariuszu musimy położyć nacisk na najgorsze zachowanie systemu. Przykładami są miękkie systemy czasu rzeczywistego, takie jak s gry, które chcą osiągnąć stałą liczbę klatek na sekundę lub serwery internetowe, które muszą wysłać odpowiedź w określonym czasie: marnowanie cykli procesora jest lepsze niż spóźnienie.
• Systemy zoptymalizowane pod kątem przepustowości nie przejmują się sporadyczne przestoje, o ile maksymalna ilość danych może być przetworzona w dłuższej perspektywie. W tym przypadku interesuje nas przede wszystkim amortyzowana wydajność. Zwykle dzieje się tak w przypadku obliczania liczb lub innych zadań przetwarzania wsadowego.

Zauważ, że jeden system może mieć różne komponenty, które muszą być klasyfikowane w różny sposób. Na przykład. nowoczesny procesor tekstu miałby wątek interfejsu użytkownika wrażliwy na opóźnienia, ale wątki zoptymalizowane pod kątem przepustowości do innych zadań, takich jak sprawdzanie pisowni lub eksportowanie plików PDF.

Ponadto złożoność algorytmów często nie ma tak dużego znaczenia, jak byśmy mogli pomyśl: Kiedy problem jest ograniczony do określonej liczby, to rzeczywiste i zmierzone charakterystyki wydajności są ważniejsze niż zachowanie „dla bardzo dużych n ”.

Komentarze

• Niestety mam bardzo mało informacji.Pytanie kończy się następująco: ” Operacje add (x) i remove () w RandomQueue powinny działać w stałym czasie na operację „.
• @Carcigenicate, chyba że wiesz, że system jest wrażliwy na opóźnienia, użycie zamortyzowanej złożoności do wybrania struktury danych powinno być absolutnie wystarczające.
• Mam wrażenie, że to może być ćwiczenie programistyczne lub test. I na pewno nie jest to łatwe. Absolutnie prawda, że bardzo rzadko ma to znaczenie.

Jeśli zostaniesz poproszony o „amortyzowany stały czas” algorytm, Twój algorytm może czasami zająć dużo czasu. Na przykład, jeśli używasz std :: vector w C ++, taki wektor może mieć przydzielone miejsce na 10 obiektów, a kiedy przydzielisz jedenasty obiekt, zostanie przydzielone miejsce na 20 obiektów, 10 obiektów zostanie skopiowanych, a 11 dodane, co zajmuje dużo czasu. Ale jeśli dodasz milion obiektów, możesz mieć 999 980 szybkich i 20 wolnych operacji, przy czym średni czas jest szybki.

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