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

38

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 liniowejO ( n log dziennika n )O(nloglogn)O(nloglogn). 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 k = O (n) . W takim przypadku wymagane jest dokonanie wyboru w czasie O (\ log k) . Jak można to zrobić?n k k = O ( n )O(n/klogk)nkk=O(n)O(logk)

Ari
źródło
13
Byłoby idealnie napisać do niego: [email protected].
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
17
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
18
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
4
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). Ω(nlogn)
Ari

Odpowiedzi:

18

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łkowitychO(nloglogn) :

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
1
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
1
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
2
(loglogn)h(h+1)!2(h+1)!h+22(h+2)!2(h+2)!=nh=Ω(logn/loglogn)(loglogn)
1

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.

K1

K2

Powtórz dla t = log k do 0.

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

  1. K2K1

  2. 2tL

  3. B = Z- (Z&M).

Część 2

  1. K1K1

  2. M = M- (M przesunął lewe miejsca L-1).

  3. MIN = (B&M) LUB (A- (A&M))

  4. MAX = (A&M) LUB (B- (B&M))

  5. 2tL

  6. 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