Nietrywialny algorytm obliczania mediany okna przesuwnego

Muszę obliczyć medianę biegu:

Dane wejściowe: , , wektor . $n$ $k$ $(x_1, x_2, \dotsc, x_n)$
Wyjście: wektor $(y_1, y_2, \dotsc, y_{n-k+1})$ , gdzie $y_i$ jest medianą $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$ .

(Brak oszustw z przybliżeniami; Chciałbym mieć dokładne rozwiązania. Elementy $x_i$ są dużymi liczbami całkowitymi.)

Istnieje prosty algorytm, który utrzymuje drzewo wyszukiwania o rozmiarze $k$ ; całkowity czas działania wynosi $O(n \log k)$ . („Drzewo wyszukiwania” odnosi się do wydajnej struktury danych, która obsługuje wstawianie, usuwanie i zapytania o medianę w czasie logarytmicznym).

Wydaje mi się to jednak trochę głupie. Skutecznie nauczymy się wszystkich statystyk zamówień we wszystkich oknach wielkości $k$ , nie tylko median. Co więcej, w praktyce nie jest to zbyt atrakcyjne, szczególnie jeśli $k$ jest duże (duże drzewa wyszukiwania są zwykle wolne, narzut w zużyciu pamięci nie jest trywialny, wydajność pamięci podręcznej jest często niska itp.).

Czy możemy zrobić coś znacznie lepszego?

Czy są jakieś dolne granice (np. Czy trywialny algorytm jest asymptotycznie optymalny dla modelu porównawczego)?

Edycja: David Eppstein podał dolną granicę dla modelu porównawczego! Zastanawiam się, czy można zrobić coś nieco sprytniejszego niż prosty algorytm?

Na przykład, czy moglibyśmy zrobić coś wzdłuż tych linii: podzielić wektor wejściowy na części wielkości $k$ ; posortuj każdą część (śledząc oryginalne pozycje każdego elementu); a następnie użyć wektora posortowanego w części, aby znaleźć działające mediany wydajnie bez żadnych struktur danych pomocniczych? Oczywiście nadal byłoby to $O(n \log k)$ , ale w praktyce sortowanie tablic jest zwykle znacznie szybsze niż utrzymywanie drzew wyszukiwania.

Edycja 2: Saeed chciał zobaczyć kilka powodów, dla których myślę, że sortowanie jest szybsze niż operacje drzewa wyszukiwania. Oto bardzo szybkie testy porównawcze, dla $k = 10^7$ , $n = 10^8$ :

≈ 8s: sortowanie $n/k$ wektorów z $k$ elementami każdy
≈ 10s: sortowanie wektora z elementami $n$
≈ lata 80 .: wstawiania i usuwania w tablicy mieszającej o rozmiarze $n$ $k$
≈ 390s: wstawiania i usuwania w zrównoważonym drzewie wyszukiwania o rozmiarze $n$ $k$

Tabela skrótów jest tylko dla porównania; nie ma bezpośredniego zastosowania w tej aplikacji.

Podsumowując, mamy prawie 50-krotną różnicę w wydajności sortowania vs. zrównoważone operacje drzewa wyszukiwania. I wszystko pogorszy się, jeśli zwiększymy . $k$

(Szczegóły techniczne: Dane = losowe 32-bitowe liczby całkowite. Komputer = typowy nowoczesny laptop. Kod testowy został napisany w C ++, przy użyciu standardowych procedur bibliotecznych (std :: sort) i struktur danych (std :: multiset, std :: unsorted_multiset). Użyłem dwóch różnych kompilatorów C ++ (GCC i Clang) oraz dwóch różnych implementacji biblioteki standardowej (libstdc ++ i libc ++). Tradycyjnie, std :: multiset został zaimplementowany jako wysoce zoptymalizowane drzewo czerwono-czarne.)

ds.algorithms ds.data-structures lower-bounds Jukka Suomela
źródło

Nie sądzę, że będziesz w stanie ulepszyć . Powodem jest to, że jeśli spojrzysz na okno , nigdy nie można wykluczyć żadnej liczby od bycia medianami przyszłego okna. Oznacza to, że w każdej chwili musisz zachować przynajmniej liczby całkowite w strukturze danych, i nie wydaje się, aby aktualizowała się w czasie krótszym niż dziennik.

n l o g k

$nlogk$

x_{t}, . . ., x_{t + k - 1}

$x_t,...,x_{t+k-1}$

x_{t + \frac{k}{2}}, . . ., x_{t + k - 1}

$x_{t+\frac{k}{2}},...,x_{t+k-1}$

\frac{k}{2}

$\frac{k}{2}$

Twój trywialny algorytm wydaje mi się nie , czy coś źle zrozumiałem? I myślę, że z tego powodu masz problem z dużym , w przeciwnym razie czynnik logarytmiczny nie ma znaczenia w praktycznych zastosowaniach, a także nie ma dużej ukrytej stałej w tym algorytmie.

O ((n - k) \cdot k \cdot \log k)

$O((n-k)\cdot k \cdot \log k)$

O (n \log k)

$O(n \log k)$

k

$k$

Saeed

@Saeed: W trywialnym algorytmie elementy są przetwarzane jeden po drugim; w kroku dodajesz do drzewa wyszukiwania i (jeśli ) również usuwasz z drzewa wyszukiwania. To jest kroków, z których każdy zajmuje czas .

i

$i$

x_{i}

$x_i$

i > k

$i > k$

x_{i - k}

$x_{i-k}$

n

$n$

O (\log k)

$O(\log k)$

Jukka Suomela

Masz na myśli zrównoważone drzewo wyszukiwania, a nie zwykłe drzewo wyszukiwania?

Saeed

@ Saeed: Pamiętaj, że w moich testach porównawczych nawet nie próbowałem znaleźć median. Właśnie zrobiłem wstawień i usunięć w drzewie wyszukiwania o rozmiarze , a operacje te z pewnością zajmą czas . Musisz tylko zaakceptować fakt, że operacje drzewa wyszukiwania są w praktyce bardzo wolne, w porównaniu z sortowaniem. Zobaczysz to łatwo, jeśli spróbujesz napisać algorytm sortowania, który działa poprzez dodanie elementów do zrównoważonego drzewa wyszukiwania - z pewnością działa w czasie , ale w praktyce będzie absurdalnie powolny, a także zmarnuje dużo pamięci.

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

O (n \log n)

$O(n \log n)$

Jukka Suomela

Odpowiedzi:

Oto dolna granica sortowania. Biorąc pod uwagę zestaw wejściowy o długości do posortowania, utwórz dane wejściowe do swojego problemu z medianą, składającego się z kopii liczby mniejszej niż minimum , następnie samego , a następnie kopii liczby większej niż maksimum i ustawić . Te prowadzące mediany tego wejścia są takie same jak na posortowanych w . $S$ $n$ $n-1$ $S$ $S$ $n-1$ $S$ $k=2n-1$ $S$

Zatem w porównawczym modelu obliczeniowym wymagany jest czas . Być może, jeśli dane wejściowe są liczbami całkowitymi i używasz algorytmów sortowania liczb całkowitych, możesz to zrobić lepiej. $\Omega(n\log n)$

David Eppstein
źródło

Ta odpowiedź naprawdę sprawia, że zastanawiam się, czy konwersacja również się utrzymuje: czy mając wydajny algorytm sortowania, czy otrzymujemy wydajny działający algorytm mediany? (Na przykład, czy efektywny algorytm sortowania liczb całkowitych implikuje wydajny działający algorytm medianowy dla liczb całkowitych? Czy też algorytm sortowania efektywny IO zapewnia działający algorytm medianowy?)

Jukka Suomela

Jeszcze raz wielkie dzięki za odpowiedź, to naprawdę ustawiło mnie na właściwej drodze i dało inspirację dla opartego na sortowaniu algorytmu filtru medianowego! W końcu udało mi się znaleźć artykuł z 1991 r., Który przedstawił zasadniczo ten sam argument, co tu podasz, a Pat Morin wskazał na inny odpowiedni artykuł z 2005 r .; patrz referencje. [6] i [9] tutaj .

Jukka Suomela,

Edycja: ten algorytm jest teraz prezentowany tutaj: http://arxiv.org/abs/1406.1717

Tak, aby rozwiązać ten problem, wystarczy wykonać następujące operacje:

Sortuj wektorów, każdy z elementami. $n/k$ $k$
Wykonaj przetwarzanie końcowe w czasie liniowym.

Z grubsza chodzi o to, że:

Rozważ dwa sąsiednie bloki wejściowe, i , oba z elementami ; pozwolić elementów być i w kolejności pojawienia się w wektorze wejściowym . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Posortuj te bloki i poznaj pozycję każdego elementu w bloku.
Rozszerz wektory i pomocą wskaźników poprzedników / następców, aby postępując zgodnie z łańcuchami wskaźników, można było przemieszczać elementy w kolejności rosnącej. W ten sposób stworzyliśmy podwójnie połączone listy i . $a$ $b$ $a'$ $b'$
Jeden po drugim, usunąć wszystkie elementy z listy połączonej , w odwrotnej kolejności występowania . Ilekroć usuwamy element, pamiętaj, jaki był jego następca i poprzednik w momencie usunięcia . $b'$ $b_k, b_{k-1}, ..., b_1$
Teraz utrzymać „średnie wskaźniki” i , które wskazują na listach i , odpowiednio. Uruchomienie do punktu środkowego i inicjalizacji do ogona pustego liście . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Dla każdego : $i$
- Usuń z listy (jest to czas, po prostu usunąć z połączonej listy). Porównać z elementem wskazanych przez aby zobaczyć, czy usunięte przed lub po . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Umieścić powrót do listy w swojej pierwotnej pozycji (jest to czas, my zapamiętane poprzednik i następca ). Porównaj z elementem wskazanym przez , aby zobaczyć, czy dodaliśmy element przed lub po . $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ $q$
- Zaktualizuj wskaźniki i tak aby mediana połączonej listy się w lub w punkcie . (Jest to czas , wystarczy postępować zgodnie z listami połączonymi jeden lub dwa kroki, aby wszystko naprawić. Będziemy śledzić, ile elementów znajduje się przed / po i na każdej liście, i zachowamy niezmienność, że oba i wskazują elementy, które są jak najbliżej mediany). $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ $q$

Połączone listy są tylko tablicami indeksów typu element, więc są lekkie (poza tym, że lokalizacja dostępu do pamięci jest niska). $k$

Oto przykładowa implementacja i testy porównawcze:

https://github.com/suomela/median-filter

Oto wykres czasów działania (dla ): $n \approx 2\cdot 10^6$

Niebieski = sortowanie + przetwarzanie końcowe, . $O(n \log k)$
Zielony = utrzymuj dwa stosy, , wdrożenie z https://github.com/craffel/median-filter $O(n \log k)$
Czerwony = utrzymuj dwa drzewa wyszukiwania, . $O(n \log k)$
Czarny = zachowaj posortowany wektor, . $O(n k)$
Oś X = rozmiar okna ( ). $\approx k/2$
Oś Y = czas pracy w sekundach.
Dane = 32-bitowe liczby całkowite i losowe 64-bitowe liczby całkowite, z różnych dystrybucji.

czasy pracy

Jukka Suomela
źródło

Biorąc pod uwagę granice Davida, jest mało prawdopodobne, abyś mógł zrobić lepszy najgorszy przypadek, ale istnieją lepsze algorytmy wrażliwe na wyniki. W szczególności, jeśli wyniku jest liczba median, możemy rozwiązać problem w czasie . $m$ $O(n \log m + m \log n)$

Aby to zrobić, zastąp zbalansowane drzewo binarne zrównoważonym drzewem binarnym składającym się tylko z tych elementów, które w przeszłości były medianami, plus dwa stosy Fibonacciego między każdą parą poprzednich median (po jednym dla każdego kierunku), a także zliczaj, abyśmy mogli zlokalizuj, która kupa Fibonacciego zawiera określony element w kolejności. Nie zawracaj sobie głowy usuwaniem elementów. Po wstawieniu nowego elementu możemy zaktualizować naszą strukturę danych w czasie . Jeśli nowe liczby wskazują, że mediana znajduje się w jednym z hałd Fibonacciego, potrzeba dodatkowego aby wyciągnąć nową medianę. To $O(\log m)$ $O(\log n)$ $O(\log n)$ ładunek występuje tylko raz na medianę.

Gdyby istniał czysty sposób usuwania elementów bez uszkadzania ładnej złożoności Fibonacciego, przechodzilibyśmy do , ale nie jestem pewien, czy jest to możliwe. $O(n \log m + m \log k)$

Geoffrey Irving
źródło

Ups, to nie działa tak, jak napisano, ponieważ jeśli nie usuniesz elementów, liczby nie odzwierciedlą nowego okna. Nie jestem pewien, czy można to naprawić, ale zostawię odpowiedź na wypadek, gdyby był sposób.

Geoffrey Irving

Myślę więc, że ten algorytm może faktycznie przyjąć

jeśli usuniesz węzły z hałd Fibonacciego, ponieważ głębokość sterty Fibonacciego wzrasta tylko wtedy, gdy wywoływane jest delete-min. Czy ktoś zna ładne granice złożoności sterty Fibonacciego, biorąc pod uwagę liczbę wywołań delete-min?

O (n \log m)

$O(n \log m)$

Geoffrey Irving

uwaga dodatkowa: pytanie nie jest jasne, podstawowa struktura danych nie jest zdefiniowana, po prostu wiemy coś bardzo niejasnego. jak chcesz poprawić coś, czego nie wiesz, co to jest? jak chcesz porównać swoje podejście?

Saeed

Przepraszam za niepełną pracę. Poprosiłem konkretne pytanie potrzebne, aby rozwiązać tę odpowiedź tutaj: cstheory.stackexchange.com/questions/21778/... . Jeśli uważasz, że to właściwe, mogę usunąć tę odpowiedź, dopóki drugie pytanie nie zostanie rozwiązane.

Geoffrey Irving