Czas Hana , przestrzeń liniowa, algorytm sortowania liczb całkowitych

Czy ktoś zna Yijie Han , algorytm sortowania liczb całkowitych? Wynik ten pojawia się w dość krótkim artykule ( Sortowanie deterministyczne w czasie i przestrzeni liniowej . J. Alg. 50: 96–105, 2004), który zasadniczo skleja ze sobą wiele wcześniejszych wyników, z odpowiednimi adaptacje. Mój problem polega na tym, że jest napisany raczej machaniem ręką, bez wchodzenia w szczegóły. Opiera się w dużej mierze na poprzednich artykułach, wyróżniających się wśród nich innym artykule Hana ( Ulepszone szybkie sortowanie liczb całkowitych w przestrzeni liniowej $O(n \log\log n)$ $O(n \log\log n)$ . Informacje i obliczenia 170 (1): 81–94) napisane w bardzo podobnym stylu. Mam poważne trudności ze zrozumieniem tych dwóch artykułów, zwłaszcza sposobu, w jaki dostosowują i wykorzystują poprzednie wyniki. Byłbym wdzięczny za każdą pomoc.

Jest to oczywiście zbyt ogólne i niejasne, aby uznać je za właściwe pytanie, ale mam nadzieję rozwinąć dyskusję na temat kilku ściśle określonych pytań i odpowiedzi.

Na wstępie oto moje pierwsze konkretne pytanie. W Lemat 2 informacji. Komp. W dokumencie znajduje się rekurencyjny algorytm czasowy służący do znajdowania m-tej najmniejszej liczby całkowitej w zestawie małych liczb całkowitych upakowanych każdy w słowa RAM. Opis algorytmu nie wspomina o tym, jak obsługiwany jest przypadek podstawowy . W takim przypadku wymagane jest dokonanie wyboru w czasie . Jak można to zrobić? $O(n/k \log k)$ $n$ $k$ $k=O(n)$ $O(\log k)$

ds.algorithms sorting

— Ari
źródło

Byłoby idealnie napisać do niego: hanyij@umkc.edu.

— Joseph O'Rourke

Tak. Omówiliśmy już ten ogólny problem i właściwym sposobem rozwiązania tego jest wysłanie e-maila do autora.

— Suresh Venkat

Obejmuje to konkretne pytanie dotyczące artykułu, który ma 7 lat i został już poddany procesowi wzajemnej oceny. Ari może przesłać autorowi e-maila, ale wydaje się, że jest to idealne pytanie do tej witryny. Nie rozumiem odchylenia.

— Huck Bennett

Oczywiście pierwszą rzeczą, którą zrobiłem, było napisanie Hana. Brak odpowiedzi. Potem skontaktowałem się z kimś innym, kto przeprowadził badania nad liczbami całkowitymi, a on powiedział, że po przejrzeniu stwierdził, że dokumenty były zbyt niechlujne, aby zasłużyć na dalsze inwestowanie swojego czasu. Właśnie wtedy tu przyszedłem. Jeśli jest ktoś, kto zna Hana i może zwrócić jego uwagę w moim imieniu, to też byłoby świetnie.

— Ari

Ogólne sortowanie nie ma dolnej granicy . Wręcz przeciwnie - sortowanie ogranicza się do porównań, które są z tym związane. Problemem tutaj nie jest ograniczenie danych wejściowych, ale udoskonalenie modelu obliczeniowego. Moim modelem obliczeniowym jest dowolna wersja RAM kosztów jednostkowych i pozwolę na wszelkie rozsądne założenia (takie jak dostępność stałych zależnych od długości słowa).

Ω (n \log n)

$\Omega(n\log n)$

— Ari

Odpowiedzi:

Zastanawiałem się tylko nad tym samym.

Na szczęście udało mi się znaleźć artykuł w czasopiśmie opublikowany w 2011 r., Który wyjaśnia to właśnie; co więcej, nie potrzebujesz subskrypcji, aby ją zobaczyć: implementacja i analiza wydajności wykładniczego sortowania drzew

Polecam przeczytać cały artykuł, aby dowiedzieć się, jak można go wdrożyć i lepiej zrozumieć jego leżącą u podstaw teorię. Pokazuje także, w jaki sposób drzewa wykładnicze zestawiają się z drzewami szybkiego sortowania i drzewami binarnymi. Oto odpowiedni fragment związany z czasem Hana , przestrzenią liniową, algorytmem sortowania liczb całkowitych $\bf O(n \log\log n)$ :

Yijie Han podsunął pomysł, który zmniejsza złożoność do oczekiwanego czasu w przestrzeni liniowej [6]. Stosowana przez niego technika polega na skoordynowanym przekazywaniu liczb całkowitych w drzewie wyszukiwania wykładniczego Anderssona [8] i liniowym dzieleniu w czasie bitów liczb całkowitych. Zamiast wstawiać liczby całkowite pojedynczo do drzewa wyszukiwania wykładniczego, przekazywał wszystkie liczby całkowite o jeden poziom drzewa wyszukiwania wykładniczego naraz. Takie skoordynowane przekazywanie daje szansę na wielokrotne dzielenie w czasie liniowym, a tym samym na przyspieszenie algorytmu. Ten pomysł może przyspieszyć, ale w praktyce bardzo trudno jest poradzić sobie z liczbami całkowitymi w partiach.

[6] Y. Han, Sortowanie deterministyczne w czasie O (n log log n) w czasie i przestrzeni liniowej, 34. STOC, 2002.

[8] A. Andersson, Szybkie deterministyczne sortowanie i wyszukiwanie w przestrzeni liniowej, IEEE Symposium on Foundations of Computer Science, 1996.

— W
źródło

Dlaczego głosowanie negatywne?

— Suresh Venkat

Właśnie dodałem ten link do artykułu z czasopisma na stronie wikipedii o drzewie wykładniczym . FYI: Ten artykuł mógł zostać opublikowany po zadaniu pytania.

— AT

@AT, czy mógłbyś nieco rozszerzyć swoją odpowiedź i wyjaśnić, w jaki sposób odpowiada ona na pytanie? W tej chwili jedyne, co daje, to link do artykułu w jakimś czasopiśmie.

— Kaveh

Cóż, już zrezygnowałem z pracy Hana, więc cieszę się, że mogłeś udzielić tej pomocy. Tak naprawdę nie spodziewałem się, że coś zobaczę, kiedy dzisiaj tu wrócę. Dzięki! Przeczytam ten nowy artykuł i zobaczę, czy pomoże mi to zrobić postęp w pracy Hana.

— Ari

(\log \log n)

$(\log\log n)$

h

$h$

(h + 1)!

$(h+1)!$

2 \cdot (h + 1)!

$2\cdot(h+1)!$

h + 2

$h+2$

2 \cdot (h + 2)!

$2\cdot(h+2)!$

2 \cdot (h + 2)! = n

$2\cdot(h+2)!=n$

h = Ω (\log n / \log \log n)

$h=\Omega(\log n/\log\log n)$

(\log \log n)

$(\log\log n)$

nie jestem pewien odpowiedzi (nie przeszedłem przez papier), ale myślę, że to powinno pomóc. Liczby są upakowane w jednym słowie, więc operacje na jednym słowie zajmują O (1). Jeśli są, powiedzmy, k liczb bitów h każda, to rozmiar słowa zależy od k, h, która z kolei zależy również od zakresu liczb. Dlatego stosujemy techniki redukcji zasięgu, które mogą zmniejszyć zakres liczb, aby wiele liczb mieściło się w jednym słowie. Następnie tworząc odpowiednie maski bitowe, możemy znaleźć oddzielne większe liczby całkowite od krótszych, biorąc pod uwagę dwa słowa na raz. Można to zrobić w czasie O (1). (Ontuition: do tego każda liczba przechowywana w słowie ma bit flagi związany z nim, a następnie odejmujemy dwa słowa ... jeśli bit flagi idzie, to jest mniejsza liczba).

Podobnie, używając powyższego, możemy również sortować dowolne słowo zawierające k liczb w czasie O (log k) (sortowanie bitoniczne).

Edycja: Algorytm sortowania liczb 2k z zakresu od 0 do m-1 upakowanych w słowie, gdzie każda liczba przyjmuje rozmiar L = log (m + k) +2.

$K_1$

$K_2$

Powtórz dla t = log k do 0.

Część 1 - podziel oryginalne słowo Z na dwa słowa A i B.

$K_2$ $K_1$
$2^t L$
B = Z- (Z&M).

Część 2

$K_1$ $K_1$
M = M- (M przesunął lewe miejsca L-1).
MIN = (B&M) LUB (A- (A&M))
MAX = (A&M) LUB (B- (B&M))
$2^t L$
Wreszcie odpowiednio ORing MAX i MIN wracamy Z.

Dałem szkic, mam nadzieję, że możesz uzupełnić wymagane szczegóły.

— singhsumit
źródło

Nie mam jasności co do tego, co sugerujesz. Zakłada się, że liczby całkowite są już małe, a k z nich jest już spakowanych w jednym słowie. Czy zamierzasz jeszcze bardziej zmniejszyć ich rozmiar? Jeśli tak, co wtedy robisz? Wiem także, jak posortować sekwencję bitoniczną spakowaną do pojedynczego słowa w czasie O (log k) lub posortować ogólną (niebitoniczną) sekwencję w czasie O (log ^ 2 k). Jeśli znasz algorytm sortujący ogólną sekwencję w czasie O (log k), czy możesz opisać go bardziej szczegółowo? (Taki algorytm rozwiązałby oczywiście problem wyboru).

— Ari

nie dalej zmniejszam rozmiaru, sugerowałem, jak zmniejszyć rozmiar, który nie był wymagany w twojej odpowiedzi. Przepraszam za zamieszanie.

— singhsumit

O ile go nie zrozumiałem, wygląda to na algorytm sortowania sekwencji bitonicznych. Nie sortuje ogólnych sekwencji. Na przykład, czy sortuje sekwencję 3,0,2,0, gdzie 3 znajduje się w polu najbardziej lewym (najbardziej znaczącym)?

— Ari

3 0 2 0 jest oddzielone n otrzymujemy A = 3 2 i B = 0 0, a następnie MAX staje się 3 2, a MIN wynosi 0 0. Następnie mamy nowe Z jako 3 2 0 0. Każda ogólna sekwencja ma sekwencję bitoniczną o rozmiarze 2. z każdą iteracją te rozmiary się podwajają, a na koniec w dzienniku k otrzymujemy odpowiedź.

— singhsumit

Nie. Liczby się nie zagęszczają, tylko się zmniejszają. W pierwszej iteracji dzielimy pary liczb różniących się wysokim bitem ich pozycji, więc otrzymujemy A = 0 3 0 2 i B = 0 0 0 0, więc MIN = 0 0 0 0, MAX = 0 3 0 2 i Z = 3 0 2 0. W drugiej iteracji dzielimy pary różniące się niskim bitem ich pozycji, więc ponownie otrzymujemy A = 0 3 0 2, B = 0 0 0 0 i ponownie Z pozostaje niezmienione.

— Ari