Algorytmy „dziel i rządź” - dlaczego nie podzielić na więcej niż dwie części?

W algorytmach dzielenia i zdobywania, takich jak szybkie sortowanie i scalanie, dane wejściowe są zwykle (przynajmniej w tekstach wprowadzających) podzielone na dwie części , a dwa mniejsze zestawy danych są następnie przetwarzane rekurencyjnie. Ma dla mnie sens, że przyspiesza to rozwiązanie problemu, jeśli dwie połowy zajmują mniej niż połowę pracy nad całym zestawem danych. Ale dlaczego nie podzielić zestawu danych na trzy części? Cztery? n ?

Myślę, że praca dzielenia danych na wiele, wiele podzestawów sprawia, że ​​nie warto, ale brakuje mi intuicji, aby zobaczyć, że należy zatrzymać się na dwóch podzestawach.

Widziałem także wiele odniesień do 3-kierunkowego szybkiego sortowania. Kiedy to jest szybsze? Co stosuje się w praktyce?

Ma dla mnie sens, że przyspiesza to rozwiązanie problemu, jeśli dwie połowy zajmują mniej niż połowę pracy nad całym zestawem danych.

To nie jest istota algorytmów „dziel i rządź”. Zazwyczaj chodzi o to, że algorytmy nie mogą w ogóle „poradzić sobie z całym zestawem danych”. Zamiast tego jest on podzielony na części, które są trywialne do rozwiązania (jak sortowanie dwóch liczb), następnie są one rozwiązywane trywialnie, a wyniki ponownie łączone w sposób, który daje rozwiązanie dla pełnego zestawu danych.

Ale dlaczego nie podzielić zestawu danych na trzy części? Cztery? n?

Głównie dlatego, że podzielenie go na więcej niż dwie części i ponowne połączenie więcej niż dwóch wyników skutkuje bardziej złożoną implementacją, ale nie zmienia podstawowej (Big O) charakterystyki algorytmu - różnica jest stałym czynnikiem i może spowodować spowolnienie jeśli podział i rekombinacja więcej niż 2 podzbiorów powoduje dodatkowe obciążenie.

Na przykład, jeśli wykonujesz sortowanie metodą łączenia w 3 kierunkach, w fazie rekombinacji musisz teraz znaleźć największy z 3 elementów dla każdego elementu, co wymaga 2 porównań zamiast 1, więc wykonasz dwa razy więcej porównań ogółem . W zamian zmniejszasz głębokość rekurencji o współczynnik ln (2) / ln (3) == 0,63, więc masz o 37% mniej swapów, ale 2 * 0,63 == 26% więcej porównań (i dostępu do pamięci). To, czy to dobrze, czy źle, zależy od tego, który jest droższy w twoim sprzęcie.

Widziałem także wiele odniesień do 3-kierunkowego szybkiego sortowania. Kiedy to jest szybsze?

Najwyraźniej można udowodnić, że wariant podwójnego obrotu Quicksort wymaga takiej samej liczby porównań, ale średnio o 20% mniej swapów, więc jest to zysk netto.

Co stosuje się w praktyce?

Obecnie prawie nikt już nie programuje własnych algorytmów sortowania; używają jednego dostarczonego przez bibliotekę. Na przykład interfejs API języka Java 7 faktycznie używa podwójnego przestawnego szybkiego sortowania.

Ludzie, którzy faktycznie programują własny algorytm sortowania z jakiegoś powodu, będą skłonni trzymać się prostego wariantu dwukierunkowego, ponieważ mniejszy potencjał błędów przewyższa o 20% lepszą wydajność przez większość czasu. Pamiętaj: zdecydowanie najważniejszą poprawą wydajności jest zmiana kodu z „niedziałający” na „działający”.

Asymptotycznie rzecz biorąc, to nie ma znaczenia. Na przykład wyszukiwanie binarne wykonuje około ₂  n porównań, a wyszukiwanie trójskładnikowe wykonuje około ₃  n porównań. Jeśli znasz swoje logarytmy, wiesz, że log _a  x = log _b  x / log _b  a, więc wyszukiwanie binarne daje tylko około 1 / log ₃ 2 ≈ 1,5 razy więcej porównań niż wyszukiwanie trójskładnikowe. Jest to również powód, dla którego nikt nigdy nie określa podstawy logarytmu w dużej notacji Oh: Zawsze jest to stały czynnik z dala od logarytmu w danej bazie, bez względu na rzeczywistą bazę. Zatem podział problemu na większą liczbę podzbiorów nie poprawia złożoności czasu i praktycznie nie wystarcza, aby przeważyć bardziej złożoną logikę. W rzeczywistości złożoność ta może negatywnie wpłynąć na wydajność praktyczną, zwiększając nacisk na pamięć podręczną lub zmniejszając nieopłacalność mikrooptymalizacji.

Z drugiej strony niektóre drzewiaste struktury danych wykorzystują wysoki współczynnik rozgałęzienia (znacznie większy niż 3, często 32 lub więcej), choć zwykle z innych powodów. Usprawnia to wykorzystanie hierarchii pamięci: struktury danych przechowywane w pamięci RAM lepiej wykorzystują pamięć podręczną, struktury danych przechowywane na dysku wymagają mniejszego odczytu HDD-> RAM.

Istnieją algorytmy wyszukiwania / sortowania, które dzielą nie według dwóch, ale według N.

Prostym przykładem jest wyszukiwanie za pomocą kodowania mieszającego, które zajmuje czas O (1).

Jeśli funkcja skrótu zachowuje porządek, można jej użyć do utworzenia algorytmu sortowania O (N). (Można pomyśleć o jakimkolwiek algorytmie sortowania jako po prostu przeprowadzeniu N wyszukiwania, gdzie liczba powinna iść w wyniku).

Podstawową kwestią jest to, że kiedy program analizuje niektóre dane, a następnie wprowadza niektóre kolejne stany, ile jest kolejnych stanów i jak bliskie są ich prawdopodobieństwa?

Gdy komputer dokonuje porównania dwóch liczb, powiedzmy, a następnie albo przeskakuje, albo nie, jeśli obie ścieżki są jednakowo prawdopodobne, licznik programu „zna” jeszcze jeden kawałek informacji na każdej ścieżce, więc średnio „nauczył się” jednego kawałek. Jeśli problem wymaga uczenia się M bitów, to przy użyciu decyzji binarnych nie można uzyskać odpowiedzi w mniej niż M decyzjach. Na przykład wyszukiwanie liczby w posortowanej tabeli o rozmiarze 1024 nie może być wykonane w mniejszej liczbie niż 10 decyzji binarnych, choćby dlatego, że jakaś mniejsza liczba nie miałaby wystarczającej liczby wyników, ale z pewnością można to zrobić w większym stopniu.

Gdy komputer pobiera jedną liczbę i przekształca ją w indeks w tablicę, „uczy się”, by zapisać log 2 podstawy liczby elementów w tablicy i robi to w stałym czasie. Na przykład, jeśli istnieje tabela skoków zawierająca 1024 wpisy, wszystkie bardziej lub mniej jednakowo prawdopodobne, wówczas przeskakiwanie przez tę tabelę „uczy się” 10 bitów. To podstawowa sztuczka związana z kodowaniem skrótu. Przykładem tego sortowania jest sposób sortowania talii kart. Posiadaj 52 pojemniki, po jednym na każdą kartę. Rzuć każdą kartę do kosza, a następnie zgarnij je wszystkie. Nie jest wymagane dzielenie.

Ponieważ jest to pytanie o ogólne dzielenie i podbijanie, a nie tylko sortowanie, jestem zaskoczony, że nikt nie podniósł Twierdzenia Mistrza

W skrócie, czas działania algorytmów dzielenia i zdobywania określają dwie siły przeciwdziałające: korzyść, którą uzyskujesz z przekształcania większych problemów w małe problemy, oraz cena, jaką płacisz za rozwiązywanie większej liczby problemów. W zależności od szczegółów algorytmu może, ale nie musi, płacić za podzielenie problemu na więcej niż dwie części. Jeśli podzielisz się na tę samą liczbę podproblemów na każdym etapie i znasz złożoność czasową łączenia wyników na każdym etapie, Twierdzenie nadrzędne powie ci o złożoności czasowej całego algorytmu.

Karatsuba algorytm mnożenia wykorzystuje 3-drożny dziel i przejęcie aby osiągnąć czas pracy o (3 n ^ log_2 3), który bije O (N ^ 2) dla algorytmu mnożenia zwykłą (n oznacza liczbę cyfr w liczby).

Ze względu na jego binarną naturę komputer bardzo skutecznie dzieli rzeczy na 2, a nie tyle na 3. Otrzymujesz podział na 3, dzieląc najpierw na 2, a następnie ponownie dzieląc jedną z części na 2. Więc jeśli musisz podzielić przez 2, aby uzyskać 3 dywizje, równie dobrze możesz podzielić na 2.