Kolejka priorytetów, która umożliwia sprawną aktualizację priorytetów?

Zgodnie z moją najlepszą wiedzą (napisałem artykuł o nowej kolejce priorytetów, w którym również przeanalizowałem wyniki z przeszłości), Żadna implementacja kolejki priorytetów nie pobiera granic stosów Fibonacciego, a także stałego-time increase-key.

Jest mały problem z otrzymaniem tego dosłownie. Jeśli możesz uzyskać increase-key W O(1), to możesz uzyskać delete w O(1) -- po prostu zwiększ klucz do +nieskończoności (możesz obsłużyć kolejkę pełną mnóstwa + nieskończoności używając standardowej amortyzacji sztuczki). Ale jeśli find-min jest również O (1), oznacza to, że delete-min = find-min + delete staje się O(1). Jest to niemożliwe w kolejce priorytetów opartej na porównaniu, ponieważ sortowanie wiązane implikuje (Wstaw wszystko, a następnie usuń jeden po drugim), że

N * insert + n * delete-min > n log N.

Punkt jest taki, że jeśli chcesz, aby Kolejka priorytetów wspierała increase-key W O(1), Musisz zaakceptować jedną z następujących Kar:

• Not be comparison na podstawie. Właściwie to całkiem dobry sposób na obejście rzeczy, np. VEB trees.
• Accept O (log n) dla wstawek oraz o(n log n) Dla make-heap (podane n wartości początkowe). Do bani.
• Accept O (log n) Dla find-min. Jest to całkowicie dopuszczalne, jeśli nigdy nie wykonasz find-min (bez dołączonego delete).

Ale, z tego co wiem, nikt nie zrobił ostatniej opcji. Zawsze postrzegałem to jako szansę na nowe daje to dość podstawowy obszar struktur danych.

Użyj Haszowane koła rozrządu - Google 'Haszowane hierarchiczne koła rozrządu', aby uzyskać więcej informacji. To uogólnienie odpowiedzi udzielanych przez ludzi. Ja bym wolał zahaczone Koło rozrządu o dużym rozmiarze koła od kół zębatych.

Niektóre kombinacje hashów i struktur o (logN) powinny zrobić to, o co prosisz.

Kusi mnie, by się pokłócić ze sposobem, w jaki analizujesz problem. W komentarzu powyżej piszesz

Ponieważ aktualizacja będzie się pojawiać bardzo często. Załóżmy, że wysyłamy wiadomości M na połączenie, a ogólny czas staje się O (MNlogN), co jest dość duże. - Trustin Lee (6 godzin temu)

Co jest absolutnie poprawne, jeśli chodzi o to. Ale większość ludzi, których znam, skoncentruj się na kosztach za wiadomość , na teorii, że jak aplikacja ma coraz więcej pracy, oczywiście będzie wymagać więcej zasobów.

Więc jeśli Twoja aplikacja ma miliard otwartych gniazd jednocześnie (czy to naprawdę prawdopodobne?) koszt Wstawienia to tylko około 60 porównań za wiadomość.

Założę się, że to przedwczesna optymalizacja: nie mierzyłeś wąskich gardeł w swoim systemie za pomocą narzędzia do analizy wydajności, takiego jak CodeAnalyst lub VTune.

W Każdym Razie, prawdopodobnie istnieje nieskończona liczba sposobów robienia tego, o co prosisz, gdy tylko zdecydujesz, że żadna pojedyncza struktura nie zrobi tego, co chcesz, i chcesz jakąś kombinację mocnych i słabych stron różnych algorytmów.

Jedną z możliwości jest podzielenie domeny gniazda N na pewną liczbę kubełków o rozmiarze B, a następnie skrócenie każdego gniazda do jednego z tych (N/B) kubełków. W tym wiadrze znajduje się sterta (lub cokolwiek) z czasem aktualizacji o (log B). Jeśli górna granica na N nie jest ustalona z góry, ale może się różnić, wtedy można tworzyć więcej wiadra dynamicznie, co dodaje trochę komplikacji, ale z pewnością jest wykonalne.

W najgorszym przypadku, zegar watchdog musi szukać (N/B) kolejek wygasania, ale zakładam, że Zegar watchdog nie jest wymagany do zabicia gniazd bezczynności w żadnej konkretnej kolejności! Oznacza to, że jeśli 10 gniazd poszło bezczynnie w ostatnim czasie, to nie musi przeszukiwać tej domeny dla tego, że czas-out pierwszy, radzić sobie z to, a następnie znaleźć ten, który timed-out sekund, itp. Wystarczy zeskanować (N/B) Zestaw wiaderek i wyliczyć wszystkie przerwy czasowe.

Jeśli nie jesteś zadowolony z liniowej tablicy wiadrów, możesz użyć priorytetowej kolejki kolejek, ale chcesz uniknąć aktualizowania tej kolejki przy każdej wiadomości, albo wrócisz do punktu wyjścia. Zamiast tego zdefiniuj pewien czas, który jest krótszy niż rzeczywisty czas. (Powiedzmy, 3/4 lub 7/8 tego) i wstawiasz kolejkę niskiego poziomu do kolejki wysokiego poziomu tylko wtedy, gdy jest najdłuższy czas przekracza to.

I ryzykując stwierdzenie oczywistego, nie chcesz, aby Twoje kolejki były ustawione naupłynął Czas. Klucze powinny być start time. Dla każdego rekordu w kolejkach, upłynął czas musi być stale aktualizowany, ale czas rozpoczęcia każdego rekordu nie zmienia się.

Istnieje bardzo prosty sposób na wykonanie wszystkich wstawiania i usuwania w O(1), korzystając z faktu, że 1) priorytet opiera się na czasie i 2) prawdopodobnie masz małą, ustaloną liczbę czasu trwania limitu.

1. Utwórz regularną kolejkę FIFO, aby trzymać wszystkie zadania, które timeout w 10 sekund. Ponieważ wszystkie zadania mają identyczny czas trwania, możesz po prostu wstawić do końca i usunąć Od początku, aby uporządkować kolejkę.
2. tworzenie kolejnej kolejki FIFO Dla zadań z 30-sekundowym czas trwania limitu. Utwórz więcej kolejek dla innych okresów czasu.
3. aby anulować, Usuń element z kolejki. Jest to O (1), jeśli kolejka jest zaimplementowana jako lista połączona.
4. Zmiana harmonogramu może być wykonana jako cancel-insert, ponieważ obie operacje są O (1). Należy pamiętać, że zadania mogą być przenoszone do różnych kolejek.
5. wreszcie, aby połączyć wszystkie kolejki FIFO w jedną ogólną kolejkę priorytetową, niech Głowa każdej kolejki FIFO uczestniczy w regularnym stercie. Głowa tej sterty będzie to zadanie z najwcześniejszym upływem czasu ze wszystkich zadań.

Jeśli masz m liczbę różnych czasów trwania, złożoność dla każdej operacji ogólnej struktury wynosi O (log m). Wstawianie to o (log m) ze względu na konieczność wyszukania kolejki do której ma zostać wstawiona. Remove-min jest O (log m) dla przywrócenia sterty. Anulowanie to O (1), ale najgorszy przypadek O (log m), jeśli anulujesz początek kolejki. Ponieważ m jest małą, stałą liczbą, o (log m) jest zasadniczo O (1). Tak. nie skaluj z liczbą zadań.

Twój konkretny scenariusz sugeruje mi okrągły bufor. Jeśli max. timeout wynosi 30 sekund i chcemy zbierać gniazda co najmniej co dziesiątą sekundę, a następnie użyć bufora 300 podwójnie połączonych list, po jednej na każdą dziesiątą sekundę w tym okresie. Aby "increaseTime" na wpisie, usuń go z listy, w której się znajduje i dodaj go do nowego okresu dziesiątego sekundy (obie operacje w czasie stałym). Kiedy kończy się okres, zbieraj wszystko, co pozostało na bieżącej liście (może karmiąc go do reaper thread) i przesunąć wskaźnik bieżącej listy.

Masz hard-limit na liczbę pozycji w kolejce - jest limit dla gniazd TCP.

Dlatego problem jest ograniczony. Podejrzewam, że każda sprytna struktura danych będzie wolniejsza niż używanie typów wbudowanych.

Czy istnieje dobry powód, aby nie używać Javy.lang.PriorityQueue? Czy funkcja remove() nie obsługuje operacji anulowania w czasie log (N)? Następnie zaimplementuj własne oczekiwanie w oparciu o czas do pozycji na początku kolejki.

Myślę, że przechowywanie wszystkich zadań na liście i przeglądanie ich byłoby najlepsze.

Musisz (zamierzasz) uruchomić serwer na jakiejś ładnej maszynie, aby dostać się do limitów, gdzie ten koszt będzie ważny?