Wybierz w połączeniu uporządkowanych tablic: Już znasz?

Szukam odniesień bibliograficznych dla następującego algorytmu / problemu: nazwałem go „BiSelect” lub „t-ary Select” lub „Select in Union of Sorted Arrays”, ale myślę, że został wprowadzony wcześniej pod inną nazwą?

Problem

Rozważ następujący problem:

Biorąc pod uwagę $k$ rozłożonych tablic posortowanych , o odpowiednich rozmiarach , oraz liczbę całkowitą , jaka jest -ta wartość ich posortowanego związku ?n 1 , … , n k t ∈ [ 1 .. ∑ n i ] t ∪ i A $A_1,\ldots, A_k$$n_1,\ldots,n_k$$t\in[1..\sum n_i]$$t$ $\cup_i A_i$

Rozwiązania

Istnieje bardzo prosty i elegancki algorytm działający w czasie jeśli k = 2 : jeśli k = 2 , po prostu porównaj A_1 [t / 2] z A_2 [t / 2] i powtórz odpowiednio w A_1 [t / 2..t] i A_2 [1..t / 2] lub A_1 [1..t / 2] i A_2 [t / 2..t] odpowiednio, w obu przypadkach z parametr t / 2 (i kilka drobnych optymalizacji, gdy n_1 lub n_2 są mniejsze niż t ).k = $O(\lg\min\{n_1,n_2,t\})$$k=2$A 1 [ t / 2 ] A 2 [ t / 2 ] A 1 [ t / 2 .. t ] A 2 [ 1 .. t / 2 ] A 1 [ 1 .. t / 2 ] A 2 [ t / 2 .. t ] t / 2 n 1 n 2$k=2$$A_1[t/2]$$A_2[t/2]$$A_1[t/2..t]$$A_2[1..t/2]$$A_1[1..t/2]$$A_2[t/2..t]$$t/2$$n_1$$n_2$$t$

Uogólnia to na nieco bardziej wyrafinowany algorytm działający w czasie $O(k\lg t)$ dla większych wartości $k$ , oparty na obliczeniu mediany wartości $A_i[t/k]$ dla $i\in[1..k]$ : Najmniejsze elementy $t/k$ można dalej ignorować w tablicach $k/2$ gdzie $A_i[t/k]$ jest mniejsza niż mediana, a elementy rang w $[t-t/k..]$ można dalej ignorować w $k/2$ inne tablice, co powoduje zmniejszenie o połowę $t$ w każdym nawrocie (i koszt $O(k)$ dla mediany).

Bibliografia?

Jestem zadowolony z moich rozwiązań, ale przypuszczam, że problem (i jego rozwiązanie) był już znany. Jest to związane z algorytmem liniowego czasu obliczania mediany (przez sortowanie grup o rozmiarze i powtarzanie się na środkowej ich środkowej długości), ale jest nieco bardziej ogólne. Poprosiłem kilka uczelni w Madalgo w Aarhus (Dania), a następnie kilka innych w warsztacie Stringology (Rouen), bez powodzenia: Mam nadzieję, że ktoś bardziej kompetentny może pomóc na Stack Exchange ...$5$

Motywacje

Rozwiązania tego problemu obejmują aplikacje odroczonej struktury danych w tablicach (w rzeczywistości można to postrzegać jako operator w odroczonej strukturze danych dla unii sortowanych tablic); i w bardziej skomplikowany sposób, do adaptacyjnego obliczania optymalnych kodów wolnych od prefiksów.

Algorytm opisany przez Fredericksona i Johnsona w 1982 r. Uważa, że ​​wszystkie zestawy mają ten sam rozmiar. W 1980 r. Opisali również optymalne rozwiązanie, które wykorzystuje różne rozmiary posortowanych zestawów. Złożoność tego algorytmu mieści się w zakresie .$O(k + \sum^k_{i=1}\log{n_i})$

Odniesienie

Greg N. Frederickson i Donald B. Johnson. 1980. Ogólny wybór i ranking (wersja wstępna). W materiałach z dwunastego dorocznego sympozjum ACM na temat teorii obliczeń (STOC '80). ACM, Nowy Jork, NY, USA, 420-428. DOI = 10.1145 / 800141.804690 http://doi.acm.org/10.1145/800141.804690

Frederickson i Johnson osiągnęli optymalny wynik w latach 80. Niech , wtedy istnieje algorytm rozwiązujący twój problem w O ( k + p log $p=\min(k,t)$.$O(k+p \log \frac{t}{p})$

Odniesienie

GN Frederickson, DB Johnson „ Złożoność wyboru i rankingu w x + y i macierzy z posortowanymi kolumnami ” J. Comput. System Sci., 24 (2) (1982), s. 197–208

Przypadek k = 2 pojawia się w równoległym sortowaniu scalającym, ponieważ połączenie dwóch posortowanych tablic z różnych wątków musi zostać podzielone na dwa wątki, aby zachować tę samą równoległość. To zadanie domowe jest jednym z odniesień.