Jak zachować kolejkę o dużym priorytecie z najważniejszymi pozycjami?

W problemach z optymalizacją trzymam w kolejce wiele propozycji kandydatów, które sprawdzam zgodnie z ich priorytetem .Jak zachować kolejkę o dużym priorytecie z najważniejszymi pozycjami?

Za każdym razem, gdy obsługuję jednego kandydata, jest on usuwany z kolejki, ale tworzy kilka nowych kandydatów, co powoduje, że liczba członków kadry rośnie wykładniczo. Aby sobie z tym poradzić przypisuję każdemu kandydatowi odpowiedź , gdy kandydat jest dodawany do kolejki, jeśli nie ma już dostępnej przestrzeni, zastępuję (jeśli jest to stosowne) co najmniej odpowiednią kandydatkę aktualnie w kolejce z nową kandydatką .

Aby to zrobić skutecznie, zachowuję dużą (ustalony rozmiar) tablicę z kandydatami i dwoma powiązanymi pośrednimi stertami binarnymi: jeden obsługuje kandydatów w malejącej kolejności pierwszeństwa, a drugi w rosnącej trafności.

Jest to wystarczająco skuteczne dla moich celów, a potrzebna dodatkowa powierzchnia wynosi około 4 int/kandydata, co jest również uzasadnione. Jednak kodowanie jest skomplikowane i nie wydaje się optymalne.

Moje pytanie dotyczy tego, czy znasz bardziej adekwatną strukturę danych, czy też bardziej konkretny sposób wykonania tego zadania bez utraty wydajności.

Źródło

2011-01-04 Esteban Crespi

Co powiecie na to, że nie należy wstawiać najmniej istotnych/wcześniejszych kandydatów? Podobnie jak w przypadku wzrostu wykładniczego, i tak nie będą one dostępne. Możesz zmienić X w zależności od wielkości kolejki, aby kolejka mogła uzyskać dane początkowe. Ale twoja kolejka się wypełni, czy jest jakiś warunek stopu? –

@TomWij Nie wiesz, że są one najmniej istotne, dopóki nie znajdziesz gorszych kandydatów. W problemach, które mnie interesują, nie ma warunków do zatrzymania się. –

Kiedy generuję nowego kandydata, obliczam wartość na podstawie prostej łatwej do obliczenia właściwości, która moim zdaniem wygeneruje prawdopodobnie dobre rozwiązanie. Tak więc trafność jest heurystyczna, preferowana przez niektórych kandydatów (i ich potomków) na innych, nie jestem pewien, jak to nazwać. –

Oto wydajne rozwiązanie, które nie zmienia czasu ani przestrzeni złożoność nad normalnym sterty:

W min sterty, każdy węzeł jest mniejsza niż obu swoich dzieci. W maksimum, każdy węzeł jest większy niż jego dzieci. Przełóżmy między właściwością min i maksimum dla każdego poziomu, czyniąc to: każdy rząd nieparzysty jest mniejszy niż jego dzieci i wnuki, a odwrotność równa się rzędom. Następnie znalezienie najmniejszego węzła jest takie samo jak zwykle, a znalezienie największego węzła wymaga spojrzenia na dzieci z korzenia i zrobienia największego węzła. Węzły bąblowe (do wstawiania) stają się nieco trickererem, ale wciąż mają tę samą złożoność O (logN).

Śledzenie pojemności i pojawianie się najmniejszego (najmniej istotnego) węzła jest łatwą częścią.

EDYCJA: Wydaje się, że jest to standardowa kupon min-max! Aby uzyskać opis, patrz: here. Istnieje implementacja C: header, source i example. Oto przykładowy wykres:

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Źródło

2011-01-04 00:38:19 marcog

@marcog +1 Nie nauczyłem się tego na uniwersytecie, całkiem interesującego. –

@Esteban http://stackoverflow.com/questions/2252793/is-there-ac-minmax-heap-implementation –

@TomWij Oh, więc domyślam się, że istnieje standardowa struktura danych :)/ja sprawdza, jak to się porównuje do mojego pomysłu. – marcog

"Optimal" trudno ocenić (prawie niemożliwe) bez profilowania.

Czasami algorytm "głupi" może być najszybszy, ponieważ procesory Intel są niesamowicie szybkie w przypadku głupich skanów tablicowych na sąsiadujących blokach pamięci, zwłaszcza jeśli pętla i dane mieszczą się w układzie scalonym. Natomiast przeskakiwanie po wskaźnikach w większym bloku pamięci, który nie mieści się na chipie, może być dziesiątki lub setki lub razy wolniejsze.

Możliwe są również problemy podczas próby zrównoleglania kodu, jeśli "sprytna" struktura danych wprowadza blokowanie, co zapobiega jednoczesnemu postępowi wielu wątków.

Zalecam profilowanie zarówno bieżącego, minimalnego, jak i prostego skanowania (brak połączonych list = mniej pamięci), aby sprawdzić, który z nich działa najlepiej. Dziwne, jak mogłoby się wydawać, widziałem "sprytne" algorytmy z połączonymi listami pobijanymi przez proste skany tablicowe w praktyce często, ponieważ prostsze podejście wykorzystuje mniej pamięci, ma bardziej rygorystyczną pętlę i przynosi więcej korzyści z optymalizacji procesora.Możesz także potencjalnie uniknąć alokacji pamięci i problemów ze zbieraniem pamięci przy ustawionym rozmiarze tablicy trzymającej kandydatów.

Jedną z opcji, którą warto rozważyć, jest rozwiązanie polegające na przycinaniu rzadziej i usuwaniu kolejnych elementów za każdym razem. Na przykład usunięcie 100 elementów przy każdej operacji przycinania oznacza, że trzeba przycinać setną część czasu. To może pozwolić na bardziej asymetryczne podejście do dodawania i usuwania elementów.

Należy jednak pamiętać, że podejście do optymalizacji w zakresie informatyki nie zawsze jest praktycznym podejściem do najwyższej wydajności na dzisiejszym i jutrzejszym sprzęcie.

Źródło

2011-01-04 01:17:21

Dziękuję za sugestie, zgadzam się z Tobą w twoich rozważaniach. W tym przypadku jednak obsługuję bardzo dużą tablicę, co sprawia, że skanowanie jest niepraktyczne. Binarna kupa jest bardzo wydajną strukturą danych zarówno teoretycznie, jak i praktycznie i miałem nadzieję, że w moim problemie można zastosować pewną odmianę. –

Jeśli użyjesz skip-lists zamiast kupek, będziesz miał czas O (1) na odładowanie elementów, a wciąż będziesz wyszukiwał w O (logn).
Z drugiej strony lista pominięć jest trudniejsza do wdrożenia i zajmuje więcej miejsca niż sterty binarne.

Źródło

2011-01-04 19:02:55

Jak zachować kolejkę o dużym priorytecie z najważniejszymi pozycjami?

Odpowiedz

Powiązane problemy