Oblicz medianę miliarda liczb

Jeśli masz miliard liczb i sto komputerów, jaki jest najlepszy sposób na zlokalizowanie mediany tych liczb?

Jedno rozwiązanie, które mam, to:

• Podziel zestaw równo między komputery.
• Sortuj je.
• Znajdź mediany dla każdego zestawu.
• Sortuj zestawy według środkowych.
• Połącz dwa zestawy naraz, od najniższej do najwyższej mediany.

Jeśli mamy m1 < m2 < m3 ...to najpierw scal, Set1aw Set2powstałym zbiorze możemy odrzucić wszystkie liczby niższe niż mediana Set12(scalone). Tak więc w dowolnym momencie mamy zbiory o równej wielkości. Nawiasem mówiąc, nie można tego zrobić równolegle. Jakieś pomysły?

Ach, mój mózg właśnie się włączył, mam teraz sensowną sugestię. Prawdopodobnie za późno, gdyby to był wywiad, ale nieważne:

Maszyna 1 powinna być nazywana „maszyną sterującą” i ze względu na argumentację albo zaczyna od wszystkich danych i wysyła je w równych paczkach do pozostałych 99 maszyn, albo dane zaczynają się równomiernie rozprowadzać między maszynami i przesyła każdemu z pozostałych 1/99 swoich danych. Przegrody nie muszą być równe, wystarczy zamknąć.

Każda inna maszyna sortuje swoje dane i robi to w sposób, który faworyzuje znalezienie najpierw niższych wartości. Na przykład quicksort, sortując zawsze najpierw dolną część partycji [*]. Zapisuje swoje dane z powrotem do maszyny sterującej w kolejności rosnącej tak szybko, jak to możliwe (używając asynchronicznego IO, aby kontynuować sortowanie, i prawdopodobnie z włączonym Nagle: trochę poeksperymentuj).

Maszyna sterująca wykonuje 99-stopniowe scalanie danych w chwili ich nadejścia, ale odrzuca połączone dane, po prostu rejestrując liczbę wartości, które widziała. Oblicza medianę jako średnią z 1/2 miliardowej i 1/2 miliarda plus jedna wartość.

To cierpi na problem „najwolniejszego w stadzie”. Algorytm nie może zakończyć się, dopóki każda wartość mniejsza niż mediana nie zostanie wysłana przez maszynę sortującą. Istnieje spora szansa, że ​​jedna taka wartość będzie dość wysoka w ramach tej paczki danych. Tak więc po zakończeniu wstępnego partycjonowania danych szacowany czas pracy jest połączeniem czasu sortowania 1/99 danych i wysyłania ich z powrotem do komputera sterującego oraz czasu, w którym sterowanie odczytuje 1/2 danych. . „Kombinacja” jest gdzieś pomiędzy maksimum a sumą tych czasów, prawdopodobnie blisko maksimum.

Wydaje mi się, że aby przesyłanie danych przez sieć było szybsze niż ich sortowanie (nie mówiąc już o wybraniu mediany), musi to być cholernie szybka sieć. Może być lepszą perspektywą, jeśli można założyć, że sieć jest natychmiastowa, na przykład jeśli masz 100 rdzeni z równym dostępem do pamięci RAM zawierającej dane.

Ponieważ sieć I / O prawdopodobnie będzie związana, mogą istnieć pewne sztuczki, które możesz wykorzystać, przynajmniej w przypadku danych wracających do maszyny sterującej. Na przykład zamiast wysyłać „1, 2, 3, .. 100”, być może maszyna sortująca mogłaby wysłać wiadomość oznaczającą „100 wartości mniejszych niż 101”. Maszyna sterująca mogłaby następnie wykonać zmodyfikowane scalanie, w którym znajdzie najmniejszą ze wszystkich tych najwyższych wartości, a następnie poinformuje wszystkie maszyny sortujące, co to było, aby mogły (a) powiedzieć maszynie sterującej, w jaki sposób wiele wartości do „zliczenia” poniżej tej wartości i (b) wznowić wysyłanie posortowanych danych od tego momentu.

Mówiąc bardziej ogólnie, prawdopodobnie istnieje sprytna gra polegająca na zgadywaniu odpowiedzi na wyzwania, w którą maszyna sterująca może grać z 99 maszynami sortującymi.

Obejmuje to jednak podróże w obie strony między maszynami, których unika moja prostsza pierwsza wersja. Naprawdę nie wiem, jak ślepo oszacować ich względne wyniki, a ponieważ kompromisy są złożone, wyobrażam sobie, że istnieją znacznie lepsze rozwiązania niż cokolwiek, co pomyślę o sobie, zakładając, że to kiedykolwiek jest prawdziwy problem.

[*] dostępny stos, jeśli pozwala na to - wybór, którą część wykonać jako pierwszą, jest ograniczony, jeśli nie masz O (N) dodatkowej przestrzeni. Ale jeśli masz wystarczająco dużo dodatkowej przestrzeni, możesz wybrać swój wybór, a jeśli nie masz wystarczająco dużo miejsca, możesz przynajmniej użyć tego, co musisz, aby wyciąć kilka rogów, wykonując najpierw małą część dla pierwszych kilku partycji.

sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

Nienawidzę być tutaj przeciwieństwem, ale nie wierzę, że sortowanie jest wymagane i myślę, że każdy algorytm obejmujący sortowanie miliardów / 100 liczb będzie powolny. Rozważmy algorytm na jednym komputerze.

1) Wybierz losowo 1000 wartości z miliarda i użyj ich, aby zorientować się w rozkładzie liczb, zwłaszcza w zakresie.

2) Zamiast sortować wartości, przydziel je do koszyków na podstawie właśnie obliczonego rozkładu. Liczba pojemników jest tak dobrana, aby komputer mógł je wydajnie obsługiwać, ale poza tym powinna być tak duża, jak wygodna. Zakresy segmentów powinny być takie, aby w każdym segmencie znajdowały się w przybliżeniu równe liczby wartości (nie jest to krytyczne dla algorytmu, ale zwiększa wydajność. 100 000 zasobników może być odpowiednie). Zanotuj liczbę wartości w każdym segmencie. To jest proces O (n).

3) Dowiedz się, w jakim zakresie wiadra leży mediana. Można to zrobić, po prostu sprawdzając łączne liczby w każdym segmencie.

4) Znajdź rzeczywistą medianę, badając wartości w tym segmencie. Jeśli chcesz, możesz użyć sortowania, ponieważ sortujesz tylko może 10 000 liczb. Jeśli liczba wartości w tym zasobniku jest duża, możesz ponownie użyć tego algorytmu, aż uzyskasz wystarczająco małą liczbę do sortowania.

To podejście działa równolegle w trywialny sposób, dzieląc wartości między komputerami. Każdy komputer zgłasza sumy z każdego segmentu do komputera „sterującego”, który wykonuje krok 3. W kroku 4 każdy komputer wysyła (posortowane) wartości z odpowiedniego segmentu do komputera sterującego (można również wykonać oba te algorytmy równolegle, ale chyba nie warto).

Cały proces wynosi O (n), ponieważ oba kroki 3 i 4 są trywialne, pod warunkiem, że liczba pojemników jest wystarczająco duża.

Miliard to właściwie dość nudne zadanie dla nowoczesnego komputera. Mówimy tutaj o 4 GB wartości 4-bajtowych liczb całkowitych ... 4 GB ... to pamięć RAM niektórych smartfonów.

public class Median {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] numbers = new int[1_000_000_000];

        System.out.println("created array after " +  (System.currentTimeMillis() - start) + " ms");

        Random rand = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = rand.nextInt();
        }

        System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");

        Arrays.sort(numbers);

        System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");

        if (numbers.length % 2 == 1) {
            System.out.println("median = " + numbers[numbers.length / 2 - 1]);
        } else {
            int m1 = numbers[numbers.length / 2 - 1];
            int m2 = numbers[numbers.length / 2];
            double m = ((long) m1 + m2) / 2.0;
            System.out.println("median = " + new DecimalFormat("#.#").format(m));
        }
}

Wyjście na moim komputerze:

created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196

Więc to kończy się na moim komputerze w mniej niż dwie minuty (1:43 z czego 0:10 to generowanie liczb losowych) przy użyciu pojedynczego rdzenia, a nawet wykonuje pełne sortowanie. Naprawdę nic nadzwyczajnego.

Z pewnością jest to interesujące zadanie dla większych zbiorów liczb. Chcę tylko zwrócić uwagę: miliard to orzeszki ziemne. Zastanów się więc dwa razy, zanim zaczniesz rzucać złożone rozwiązania w zaskakująco proste zadania;)

Oszacowanie statystyk rzędu jak środkowej i 99. percentyla może być efektywnie rozprowadzany do algorytmów, takich jak t-trawienia lub P-strawienia .

Korzystając z obu algorytmów, każdy węzeł tworzy podsumowanie, które reprezentuje rozkład wartości przechowywanych lokalnie. Podsumowania są gromadzone w jednym węźle, łączone (skutecznie sumując rozkłady), a następnie można sprawdzić medianę lub inny percentyl.

Podejście to jest używane przez elastyczne wyszukiwanie i prawdopodobnie BigQuery (idąc za opisem funkcji KWANTYLE).

Mediana dla tego zbioru liczb

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97

jest 67.

Mediana dla tego zbioru liczb

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89

jest 40.

Zakładając, że pytanie dotyczyło około 1 000 000 000 liczb całkowitych (x), gdzie 0> = x <= 2 147 483 647 i że OP szukał (element (499 999 999) + element (500 000 000)) / 2 (jeśli liczby zostały posortowane). Zakładając również, że wszystkie 100 komputerów było równych.

używając mojego laptopa i GigE ...

Odkryłem, że mój laptop może posortować 10000000 Int32 w 1,3 sekundy. Tak więc zgrubne oszacowanie byłoby takie, że sortowanie miliardów liczb zajmie 100 x 1,3 sekundy (2 minuty 10 sekund);).

Szacunkowy jednokierunkowy transfer pliku 40 MB w sieci Gigabit Ethernet to 0,32 sekundy. Oznacza to, że posortowane wyniki ze wszystkich komputerów zostaną zwrócone w ciągu około 32 sekund (komputer 99 nie otrzymał swojego pliku do 30 sekund po uruchomieniu). Stamtąd nie powinno zająć dużo czasu, aby odrzucić najniższe 499 999 998 liczb, dodać następne 2 i podzielić przez 2.

Może to zaskoczyć ludzi, ale jeśli liczby są na tyle małe, że mieszczą się w 32-bitowych (lub mniejszych) - po prostu zrób sortowanie wiadro! Potrzebuje tylko 16 GB pamięci RAM dla dowolnej liczby 32-bitowych int i działa w trybie O (n), co powinno przewyższać wszelkie systemy rozproszone za rozsądne n, np. Miliard.

Gdy już masz posortowaną listę, wybranie mediany jest trywialne. W rzeczywistości nie musisz tworzyć posortowanej listy, ale wystarczy spojrzeć na segmenty.

Poniżej przedstawiono prostą implementację. Działa tylko dla 16-bitowych liczb całkowitych, ale rozszerzenie do 32-bitowych powinno być łatwe.

#include <stdio.h>
#include <string.h>

int main()
{
    unsigned short buckets[65536];
    int input, n=0, count=0, i;

    // calculate buckets
    memset(buckets, 0, sizeof(buckets));
    while (scanf("%d", &input) != EOF)
    {
        buckets[input & 0xffff]++;
        n++;
    }

    // find median 
    while (count <= n/2)
    {
        count += buckets[i++];
    }

    printf("median: %d\n", i-1);

    return 0;
}

Korzystanie z pliku tekstowego z miliardem (10 ⁹ ) liczb i bieganie z timepodobnymi

time ./median < billion

daje czas pracy na moim komputerze 1m49,293s. Najprawdopodobniej większość czasu działania to również operacje we / wy dysku.

Co dziwne, myślę, że jeśli masz wystarczająco dużo komputerów, lepiej jest sortować, niż używać O(n)algorytmów znajdowania mediany. (O ile twoje rdzenie nie są bardzo, bardzo wolne, O(n)użyłbym tylko jednego i użyłbym algorytmu znajdowania mediany dla zaledwie 1e9 liczb; gdybyś miał 1e12, może to być mniej praktyczne.)

W każdym razie, załóżmy, że mamy więcej niż log n rdzeni, aby poradzić sobie z tym problemem i nie dbamy o zużycie energii, po prostu szybko uzyskujemy odpowiedź. Załóżmy dalej, że jest to maszyna SMP ze wszystkimi danymi już załadowanymi do pamięci. (Na przykład 32-rdzeniowe maszyny firmy Sun są tego typu).

Jeden wątek ślepo tnie listę na równe kawałki i każe innym M wątków je posortować. Te wątki pilnie to robią, na (n/M) log (n/M)czas. Następnie zwracają nie tylko swoje mediany, ale także, powiedzmy, 25 i 75 percentyl (przewrotne najgorsze przypadki są lepsze, jeśli wybierzesz nieco inne liczby). Teraz masz 4 mln zakresów danych. Następnie sortujesz te zakresy i przechodzisz w górę przez listę, aż znajdziesz taką liczbę, że jeśli wyrzucisz każdy zakres, który jest mniejszy lub zawiera liczbę, wyrzucisz połowę danych. To jest twoja dolna granica mediany. Zrób to samo dla górnej granicy. Zajmuje to trochę M log Mczasu i wszystkie rdzenie muszą na to czekać, więc to naprawdę marnowanieM^2 log Mpotencjalny czas. Teraz masz pojedynczy wątek, który każe innym wyrzucić wszystkie dane poza zakres (powinieneś wyrzucić około połowy przy każdym przebiegu) i powtórzyć - jest to banalnie szybka operacja, ponieważ dane są już posortowane. Nie powinieneś powtarzać tego więcej niż log(n/M)razy, zanim szybciej będzie można po prostu pobrać pozostałe dane i użyć na nich standardowej O(n)wyszukiwarki median.

Tak więc całkowita złożoność jest czymś w rodzaju O((n/M) log (n/M) + M^2 log M log (n/M)). Jest to zatem szybsze niż O(n)sortowanie według mediany na jednym rdzeniu, jeśli M >> log(n/M)i M^3 log M < n, co jest prawdą w przypadku opisanego scenariusza.

Myślę, że to naprawdę zły pomysł, biorąc pod uwagę, jak nieefektywny jest, ale jest szybszy.

Można to zrobić szybciej niż algorytm głosowany (n log n)

- Algorytm wyboru rozproszonego statystyki porządku - O (n)
Uprość problem do pierwotnego problemu znalezienia k-tej liczby w nieposortowanej tablicy.
- Histogram sortowania zliczającego O (n)
Musisz założyć pewne własności dotyczące zakresu liczb - czy zakres ten mieści się w pamięci? - Zewnętrzne sortowanie przez scalanie - O (n log n) - opisane powyżej
W zasadzie sortujesz liczby na pierwszym przebiegu, a następnie znajdujesz medianę na drugim.
- Jeśli cokolwiek wiadomo o rozkładzie liczb, można stworzyć inne algorytmy.

Więcej szczegółów i implementacja można znaleźć pod adresem :
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

Do rozwiązania problemu wystarczy jeden komputer.

Ale załóżmy, że jest 100 komputerów. Jedyną złożoną rzeczą, którą powinieneś zrobić, jest posortowanie listy. Podziel go na 100 części, wyślij po jednej części do każdego komputera, pozwól im tam posortować, a następnie połącz części.

Następnie weź liczbę ze środka posortowanej listy (tj. Z indeksem 5 000 000 000).

To zależy od Twoich danych. W najgorszym przypadku są to równomiernie rozłożone liczby.

W tym przypadku medianę można znaleźć w czasie O (N), jak w tym przykładzie:

Załóżmy, że Twoje liczby to 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (zakres to 1-10) .

Tworzymy 3 wiadra: 1-3, 4-7, 8-10. Zwróć uwagę, że góra i dół mają taki sam rozmiar.

Wypełniamy wiadra liczbami, liczymy ile przypada w każdym, max i min

• niski (5): 2,1,1,3,3, min 1, max 3
• środek (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7
• wysoki (5): 10, 10, 8, 9, 9, min 8, max 10

Średnia wypada w środkowym wiadrze, resztę pomijamy

Tworzymy 3 segmenty: 4, 5-6, 7. Niski zaczyna się od liczby 5, a maksimum 3, a maksimum - 8 i 5.

Dla każdej liczby liczymy, ile z nich spadnie do segmentu niskiego i wysokiego, maksymalnego i minimalnego, i zachowujemy środkowy segment.

• stary niski (5)
• niski (5): 4, 4, 4, 4, 4, max 4
• środek (3): 5,6,6
• wysoki (2): 7, 7, min 7
• stary wysoki (5)

Teraz możemy bezpośrednio obliczyć medianę: mamy taką sytuację

old low    low          middle  high  old high
x x x x x  4 4 4 4 4 4   5 6 6  7 7   x x x x x

więc mediana wynosi 4,5.

Zakładając, że wiesz trochę o rozkładzie, możesz dostosować sposób definiowania zakresów, aby zoptymalizować prędkość. W każdym razie wydajność powinna iść z O (N), ponieważ 1 + 1/3 + 1/9 ... = 1,5

Potrzebujesz min i max ze względu na skrajne przypadki (np. Jeśli mediana jest średnią między maksimum starego doła a następnym elementem).

Wszystkie te operacje można zrównoleglać, możesz przekazać 1/100 danych do każdego komputera i obliczyć 3 segmenty w każdym węźle, a następnie rozdzielić trzymany pojemnik. To znowu sprawia, że ​​korzystasz z sieci wydajnie, ponieważ każda liczba jest przekazywana średnio 1,5 razy (więc O (N)). Możesz nawet pokonać to, jeśli przekażesz tylko minimalne liczby między węzłami (np. Jeśli węzeł 1 ma 100 numerów, a węzeł 2 ma 150 numerów, wówczas węzeł 2 może dać 25 numerów węzłowi 1).

O ile nie wiesz więcej o rozkładzie, wątpię, że poradzisz sobie lepiej niż O (N), ponieważ faktycznie musisz policzyć elementy przynajmniej raz.

Łatwiejszą metodą jest stosowanie liczb ważonych.

• Podziel duży zestaw między komputery
• Sortuj każdy zestaw
• iteruj przez mały zbiór i oblicz wagi dla powtarzających się elementów
• połącz każde 2 zestawy w 1 (każdy jest już posortowany) aktualizując wagi
• scalaj zestawy, aż uzyskasz tylko jeden zestaw
• iteruj przez ten zestaw, gromadząc wagi, aż osiągniesz OneBillion / 2

Podziel 10 ^ 9 liczb, 10 ^ 7 na każdy komputer ~ 80 MB na każdym. Każdy komputer sortuje swoje numery. Następnie komputer 1 łączy - sortuje własne liczby z numerami z komputera 2, komputera 3 i 4 itd. Następnie komputer 1 zapisuje połowę liczb z powrotem do 2, 3 do 4 itd. Następnie scalanie 1 sortuje liczby z komputerów 1,2,3,4, zapisuje je z powrotem. I tak dalej. W zależności od rozmiaru pamięci RAM na komputerach, możesz uciec od niepisania wszystkich liczb z powrotem do poszczególnych komputerów na każdym kroku, możesz być w stanie zgromadzić liczby na komputerze 1 przez kilka kroków, ale wykonasz obliczenia.

Och, w końcu uzyskaj średnią z wartości 500000000 i 500000001 (ale sprawdź, czy jest tam wystarczająco dużo 00, nie mam).

EDYCJA: @Roman - cóż, jeśli nie możesz w to uwierzyć, nawet jeśli to prawda, to nie ma sensu ujawniać prawdziwości lub fałszu zdania. Chciałem powiedzieć, że brutalna siła czasami bije sprytnie w wyścigu. Zajęło mi około 15 sekund, aby opracować algorytm, który - jestem przekonany - potrafię zaimplementować, który będzie działał i który będzie można dostosować do szerokiego zakresu rozmiarów wejść i liczby komputerów, a także dostroić do parametrów komputerów ustalenia sieciowe. Jeśli Tobie lub komukolwiek innemu zajmie 15 minut, aby opracować bardziej wyrafinowany algorytm, mam przewagę 14 minut i 45 sekund, aby zakodować moje rozwiązanie i uruchomić je.

Ale przyznaję, że to wszystko stwierdzenie, niczego nie mierzyłem.

Można to zrobić na węzłach przy użyciu danych, które nie są posortowane między węzłami (powiedzmy z plików dziennika) w następujący sposób.

Istnieje 1 węzeł nadrzędny i 99 węzłów podrzędnych. Węzły potomne mają dwa wywołania API:

• stats (): zwraca min, max i count
• Compare (median_guess): zwraca liczbę pasującą wartość, liczbę mniejszą niż wartość i liczbę większą niż wartość

Węzeł nadrzędny wywołuje funkcję stats () na wszystkich węzłach podrzędnych, zwracając uwagę na minimum i maksimum wszystkich węzłów.

Wyszukiwanie binarne można teraz przeprowadzić w następujący sposób:

1. Podziel minimalne i maksymalne zaokrąglenie w dół - to jest mediana „przypuszczenia”
2. Jeśli wartość większa niż liczba jest większa niż liczba mniejsza niż liczba, ustaw minimum na zgadnięcie
3. Jeśli wartość większa niż liczba jest mniejsza niż liczba mniejsza niż liczba, ustaw maksimum na zgadnięcie
4. Jeśli liczba jest nieparzysta, zakończ, gdy minimum i maksimum są równe
5. Jeśli zliczanie jest nawet zakończone, gdy maksimum <= minimum + guess.match_count Można to zrobić na węzłach przy użyciu nieposortowanych danych (powiedzmy z plików dziennika) w następujący sposób.

Istnieje 1 węzeł nadrzędny i 99 węzłów podrzędnych. Węzły potomne mają dwa wywołania API:

• stats (): zwraca min, max i count
• Compare (median_guess): zwraca liczbę pasującą wartość, liczbę mniejszą niż wartość i liczbę większą niż wartość

Węzeł nadrzędny wywołuje funkcję stats () na wszystkich węzłach podrzędnych, zwracając uwagę na minimum i maksimum wszystkich węzłów.

Wyszukiwanie binarne można teraz przeprowadzić w następujący sposób:

1. Podziel minimalne i maksymalne zaokrąglenie w dół - to jest mediana „przypuszczenia”
2. Jeśli wartość większa niż liczba jest większa niż liczba mniejsza niż liczba, ustaw minimum na zgadnięcie
3. Jeśli wartość większa niż liczba jest mniejsza niż liczba mniejsza niż liczba, ustaw maksimum na zgadnięcie
4. Jeśli liczba jest nieparzysta, zakończ, gdy minimum i maksimum są równe
5. Jeśli liczba jest równa, kończy się, gdy maksimum <= minimum + guess.match_count

Jeśli stats () i compare () mogą być obliczone wstępnie za pomocą sortowania O (N / Mlogn / M), wówczas wstępne obliczenie O (N / M) ze złożonością pamięci O (N) dla obliczenie. Wtedy mógłbyś porównać () w stałym czasie, więc całość (łącznie z obliczeniami wstępnymi) działałaby w O (N / MlogN / M) + O (logN)

Daj mi znać, jeśli popełniłem błąd!

Co powiesz na to: - każdy węzeł może przyjąć 1 miliard / 100 numerów. W każdym węźle można sortować elementy i znaleźć medianę. Znajdź medianę median. możemy, agregując zliczenia liczb mniejszych niż mediana-mediany we wszystkich węzłach, znaleźć podział x%: y%, jaki tworzy mediana-median. Teraz poproś wszystkie węzły o usunięcie elementów mniejszych niż mediana median (na przykładzie podziału 30%: 70%). 30% liczb jest usuwanych. 70% z 1 miliarda to 700 milionów. Teraz wszystkie węzły, które usunęły mniej niż 3 miliony węzłów, mogą wysłać te dodatkowe węzły z powrotem do głównego komputera. Główny komputer dokonuje redystrybucji w taki sposób, że teraz wszystkie węzły będą miały prawie taką samą liczbę węzłów (7 milionów). Teraz, gdy problem został zredukowany do 700 milionów liczb ... trwa do momentu, gdy mamy mniejszy zbiór, który można obliczyć na jednym komputerze.

Najpierw zastanówmy się, jak znaleźć medianę n liczb na jednym komputerze: w zasadzie używam strategii partycjonowania.

Problem: wybór (n, n / 2): Znajdź n / 2 liczbę z najmniejszej liczby.

Wybierasz, powiedzmy, środkowy element k i dzielisz dane na 2 tablice podrzędne. pierwszy zawiera wszystkie elementy <k, a drugi zawiera wszystkie elementy> = k.

jeśli sizeof (pierwsza podtablica)> = n / 2, wiesz, że ta podtablica zawiera medianę. Następnie możesz odrzucić drugą pod macierz. Rozwiąż ten problem wyboru (rozmiar pierwszej podtablicy, n / 2) .

W innym przypadku wyrzuć pierwszą podtablicę i rozwiąż zaznaczenie (druga podtablica, n / 2 - sizeof (1. podtablica))

Zrób to rekurencyjnie.

złożoność czasowa to O (n) oczekiwany czas.

Teraz, jeśli mamy wiele maszyn, w każdej iteracji musimy przetworzyć tablicę do podziału, rozdzielamy tablicę na maszyny różnicowe. Każda maszyna przetwarza swój fragment tablicy i odsyła podsumowanie do maszyny kontrolującej koncentrator, tj. Rozmiar pierwszej podtablicy i rozmiar drugiej podtablicy. Maszyny obsługujące koncentratory sumują podsumowania i decydują, która podtablica (pierwsza lub druga) ma przetwarzać dalej i drugi parametr wyboru i odsyła ją z powrotem do każdej maszyny. i tak dalej.

Ten algorytm można bardzo starannie zaimplementować za pomocą map redukuj?

Jak to wygląda?

Myślę, że odpowiedź Steve'a Jessopa będzie najszybsza.

Jeśli rozmiar transferu danych w sieci jest wąskim gardłem, oto inne podejście.

Divide the numbers into 100 computers (10 MB each). 
Loop until we have one element in each list     
    Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
    Send the medians to a central computer and find the median of medians. Then send the median back to each computer. 
    For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.

Zrobiłbym to tak:

na początku wszystkie 100 pracują, aby znaleźć najwyższą i najniższą liczbę; każdy komputer ma swoją część bazy danych / pliku, o którą pyta;

po znalezieniu największej i najniższej liczby jeden komputer odczytuje dane i rozdziela każdą liczbę równo na pozostałe 99; liczby są rozdzielane w równych odstępach; (jeden może wynosić od -100 milionów do 0, inny - od 0 do 100 milionów itd.);

Podczas odbierania numerów każdy z 99 komputerów już je sortuje;

Wtedy łatwo jest znaleźć medianę ... Zobacz, ile liczb ma każdy komputer, dodaj je wszystkie (suma liczby liczb, a nie samych liczb), podziel przez 2; obliczyć, w którym komputerze jest liczba i przy którym indeksie;

:) voilla

PS Wygląda na to, że jest tu wiele nieporozumień; MEDIAN - to LICZBA W ŚRODKU SORTOWANEJ LISTY LICZB!

Możesz użyć metody drzewa turnieju, aby znaleźć medianę. Możemy stworzyć drzewo z 1000 węzłów opuszczających, tak że każdy węzeł liścia jest tablicą. Następnie przeprowadzamy turnieje n / 2 między różnymi tablicami. Wynik jest wartością root po turniejach n / 2.

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/

Jeśli liczby nie są odrębne i należą tylko do pewnego zakresu, to znaczy są powtarzane, to prostym rozwiązaniem, które przychodzi mi do głowy, jest równe rozdzielenie liczb między 99 maszyn i utrzymanie jednej maszyny jako głównej. Teraz każda maszyna wykonuje iterację po podanych liczbach i zapisuje liczbę każdej liczby w zestawie skrótów. Za każdym razem, gdy liczba zostanie powtórzona w zestawie liczb przydzielonych temu konkretnemu komputerowi, aktualizuje on swoją liczbę w zestawie skrótów.

Następnie wszystkie maszyny zwracają swój zestaw mieszania do maszyny głównej. Maszyna główna łączy zestawy skrótów, sumując liczbę tego samego klucza znalezionego w zestawie skrótów. Na przykład zestaw hash maszyny # 1 miał wpis ("1", 7), a zestaw hash maszyny # 2 miał wpis ("1", 9), więc maszyna główna podczas czesania zestawów haszujących tworzy wpis („1”, 16) i tak dalej.

Po scaleniu zestawów skrótów po prostu posortuj klucze, a teraz możesz łatwo znaleźć (n / 2) tę pozycję i (n + 2/2) tę pozycję z posortowanego zestawu skrótów.

Ta metoda nie będzie korzystna, jeśli miliardy liczb są różne.

Cóż, załóżmy, że wiesz, że liczba różnych liczb całkowitych wynosi (powiedzmy) 4 miliardy, a następnie możesz podzielić je na 64 tys. Pojemników i uzyskać rozproszoną liczbę dla każdego segmentu z każdej maszyny w klastrze (100 komputerów). Połącz wszystkie te liczby. Teraz znajdź zasobnik, który ma medianę, i tym razem poproś tylko o zasobniki dla 64 tys. Elementów, które będą znajdować się w zasobniku docelowym. Wymaga to O (1) (a konkretnie 2) zapytań dotyczących Twojego „klastra”. :RE

Moja wartość grosza, po tym wszystkim, co wychowali już inni:

Znalezienie mediany na pojedynczym komputerze to O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

Wysyłanie N numerów do 100 maszyn to również O (N). Aby więc korzystanie ze 100 maszyn było interesujące, albo komunikacja musi być stosunkowo szybka, albo N jest tak duże, że pojedyncza maszyna nie może jej obsłużyć, podczas gdy N / 100 jest wykonalne, albo po prostu chcemy rozważyć problem matematyczny bez zawracania sobie głowy komunikacja danych.

Krótko mówiąc, przyjmuję zatem, że w rozsądnych granicach możemy wysyłać / dystrybuować liczby bez wpływu na analizę wydajności.

Rozważmy zatem następujące podejście, w którym jedna maszyna jest przypisana jako „główna” dla niektórych ogólnych operacji. Będzie to stosunkowo szybkie, więc „mistrz” uczestniczy również w typowych zadaniach wykonywanych przez każdą maszynę.

1. Każda maszyna otrzymuje N / 100 liczb, oblicza własną medianę i wysyła tę informację do mastera.
2. Master kompiluje posortowaną listę wszystkich różnych median i wysyła ją z powrotem do każdego komputera, definiując uporządkowaną sekwencję przedziałów (na każdym komputerze taka sama), po jednej dla każdej wartości mediany (przedział o pojedynczej wartości) i po jednej dla każdego przedziału między sąsiednie środkowe. Oczywiście istnieją również przedziały z niższej i wyższej półki dla wartości poniżej najniższej mediany i powyżej najwyższej.
3. Każda maszyna oblicza, ile liczb przypada w każdym segmencie i przekazuje te informacje do modułu głównego.
4. Moduł główny określa, który segment zawiera medianę, ile niższych wartości (łącznie) znajduje się poniżej tego segmentu, a ile powyżej.
5. Jeśli wybrany przedział jest segmentem o pojedynczej wartości (jedną z median) lub wybrany przedział zawiera tylko 1 (N nieparzyste) lub 2 (N parzyste) wartości, które wykonaliśmy. W przeciwnym razie powtarzamy powyższe kroki z następującymi (oczywistymi) modyfikacjami:
6. Tylko liczby z wybranego segmentu są (ponownie) rozdzielane z modułu głównego do 100 maszyn, a ponadto
7. Nie będziemy obliczać (na każdym komputerze) mediany, ale k-tą wartość, gdzie weźmiemy pod uwagę, ile wyższych liczb zostało odrzuconych z sumy, a ile niższych liczb. Koncepcyjnie każda maszyna ma również swój udział w odrzuconych niskich / wysokich liczbach i bierze to pod uwagę podczas obliczania nowej mediany w zestawie, który (koncepcyjnie) obejmuje (swój udział) odrzuconych liczb.

Złożoność czasowa:

1. Krótkie przemyślenie przekona Cię, że na każdym kroku łączna liczba analizowanych wartości zmniejsza się o współczynnik co najmniej dwa (2 byłoby raczej chorym przypadkiem; możesz spodziewać się znacznie lepszej redukcji). Z tego otrzymujemy:
2. Zakładając, że znalezienie mediany (lub k-tej wartości), która wynosi O (N), zajmuje czas c * N, w którym prefaktor c nie zmienia się zbyt gwałtownie z N, abyśmy mogli przyjąć ją jako stałą w danym momencie, możemy Ostateczny wynik uzyskamy co najwyżej 2 * c * N / 100 razy. Użycie 100 maszyn daje zatem współczynnik przyspieszenia równy 100/2 (przynajmniej).
3. Jak zauważono na początku: czas potrzebny na przekazywanie liczb między maszynami może sprawić, że po prostu robienie wszystkiego na jednej maszynie będzie bardziej atrakcyjne. Jednakże JEŻELI zdecydujemy się na podejście rozproszone, całkowita liczba liczb do przekazania we wszystkich krokach łącznie nie przekroczy 2 * N (N za pierwszym razem, <= N / 2 za drugim razem, <= połowa tego trzeci i tak dalej).

1. Podziel 1 miliard liczb na 100 maszyn. Każda maszyna będzie miała 10 ^ 7 liczb.

2. Dla każdego numeru przychodzącego do maszyny, zapisz numer w mapie częstotliwości, liczba -> liczba. Zachowaj również minimalną liczbę w każdej maszynie.

3. Znajdź medianę w każdej maszynie: zaczynając od liczby min w każdej maszynie, zsumuj zliczenia do osiągnięcia indeksu mediany. Mediana w każdej maszynie będzie wynosić ok. mniejsze i większe niż 5 * 10 ^ 6 liczb.

4. Znajdź medianę wszystkich median, która będzie mniejsza i większa niż ok. 50 * 10 ^ 7 liczb, co stanowi medianę 1 miliarda liczb.

Teraz pewna optymalizacja drugiego kroku: Zamiast przechowywać w mapie częstotliwości, przechowuj liczniki w zmiennej tablicy bitów. Na przykład: Powiedzmy, że zaczynając od liczby min w maszynie, są to liczniki częstotliwości:

[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count

Powyższe można zapisać w tablicy bitowej jako:

[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000

Zauważ, że łącznie będzie to kosztować około 10 ^ 7 bitów na każdą maszynę, ponieważ każda maszyna obsługuje tylko 10 ^ 7 liczb. 10 ^ 7 bitów = 1,25 * 10 ^ 6 bajtów, czyli 1,25 MB

Tak więc przy powyższym podejściu każda maszyna będzie potrzebować 1,25 MB miejsca na obliczenie lokalnej mediany. Medianę median można obliczyć na podstawie tych 100 lokalnych median, co daje medianę 1 miliarda liczb.

Proponuję metodę obliczania w przybliżeniu mediany. :) Jeśli te miliardy liczb są w losowej kolejności, myślę, że mogę losowo wybrać 1/100 lub 1/10 miliarda liczb, posortować je za pomocą 100 maszyn, a następnie wybrać medianę z nich. Albo podzielmy miliard liczb na 100 części, niech każda maszyna wybierze losowo 1/10 każdej części, obliczymy ich medianę. Po tym mamy 100 liczb i możemy łatwiej obliczyć medianę liczby 100. To tylko sugestia, nie jestem pewien, czy jest matematycznie poprawna. Ale myślę, że możesz pokazać wynik niezbyt dobremu menedżerowi z matematyki.

Odpowiedź Steve'a Jessopa jest błędna:

rozważ następujące cztery grupy:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

Mediana wynosi 21, co należy do drugiej grupy.

Mediana czterech grup to 6, 24, 30, 36. Całkowita mediana to 27.

Tak więc po pierwszej pętli cztery grupy staną się:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

21 jest już niesłusznie odrzucone.

Ten algorytm obsługuje tylko przypadek, gdy istnieją dwie grupy.