Oblicz medianę miliarda liczb

127

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?

anonia
źródło
4
@John Boker: właściwie problem składa się z dwóch podproblemów: 1) sortowania listy i 2) pobierania elementu o indeksie 5'000'000'000. Nie wierzę, że liczby są posortowane.
Roman
3
@Roman: problem nie musi składać się z dwóch podproblemów, które opisujesz, np. Szybkiego wyboru. Ale quickselect nie działa równolegle, przynajmniej nie trywialnie. I oczywiście masz rację, jeśli liczby są wstępnie posortowane, to całkiem bezcelowe pytanie.
Steve Jessop
5
@fmsf: Nie sądzę, aby jakikolwiek kraj anglojęzyczny używał długiego miliarda w języku angielskim do jakichkolwiek oficjalnych celów. Na przykład tutaj, w Wielkiej Brytanii, przestaliśmy go używać w 1974 roku. Uznałbym użycie słowa „miliard” w znaczeniu miliona milionów w języku angielskim za perwersyjne, trikowe pytanie, a nie za „prawdziwy miliard”. Oczywiście po francusku byłaby to zupełnie inna sprawa, ale pytanie nie jest po francusku.
Steve Jessop
5
Nie musisz sortować! en.wikipedia.org/wiki/…
glebm
2
1 miliard liczb to tylko kilka gigabajtów danych, nie potrzebujesz wielu komputerów ani skomplikowanych algorytmów do rozwiązania tego zadania. Nie komplikuj zbytnio.
user626528

Odpowiedzi:

53

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.

Steve Jessop
źródło
Proszę poprawić mnie, jeśli się mylę, dlaczego wykonujesz 99-stopniowe scalanie danych, które docierają tylko do późniejszego usunięcia. Zamiast tego, czy wystarczy liczyć liczby, gdy nadejdą?
sreeprasad
4
@SREEPRASADGOVINDANKUTTY: powtarzającym się krokiem jest odrzucenie najmniejszej wartości ze wszystkich 99 kandydatów i zwiększenie liczby. Nie ma sensu po prostu zliczać wszystkich przychodzących wartości bez tego 99-stopniowego kroku scalania. Jeśli nie porównasz ich na bieżąco, nie wiesz, że wartość, którą odrzucasz, jest poniżej mediany.
Steve Jessop,
Ale czy nie ma małej szansy, że którakolwiek z tych partycji zawiera tylko liczby wyższe niż mediana, a zatem każda niższa partycja, którą zwróci, będzie wyższa niż mediana, ale ponieważ kontrola nie wie o tym, odrzuci je jako niższe niż mediana i porażka ...?
Gullydwarf
@Gullydwarf: wielostronne scalanie odrzuca tylko najmniejszą z 99 posiadanych wartości, z których każda jest najmniejszą pozostałą wartością z jednej z pozostałych maszyn. Jeśli jedna z partycji jest całkowicie większa niż mediana, nie stanie się najmniejszą z tych 99 wartości, dopóki mediana nie minie (w tym momencie skończymy). Więc nie zostanie wyrzucony.
Steve Jessop,
51
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
DrPizza
źródło
3
LOL. Czy to naprawdę działa, czy też zabójca z OOM niszczy go przed zakończeniem? (na jakimkolwiek rozsądnym komputerze)
Isak Savo
5
Powinieneś zrobić. sort wie, jak wykonać sortowanie poza rdzeniem, więc nie zabraknie mu pamięci.
DrPizza
6
@Zagfai Nie sądzę, żeby zajęłoby to zbyt dużo czasu; miliard liczb to tylko 4 GB dla 32-bitowych int / float, 8 GB dla 64-bitowych int / double. Żaden z nich nie wydaje się ogromnie obciążający.
DrPizza
13
Właśnie wypróbowałem na Intel i5-4200M @ 3,1 GHz (4 rdzenie). Zgodnie z timepoleceniem zastosowanym do całego rurociągu zajęło to real=36m24s(„zegar ścienny”), user=113m15s („czas równoległy”, wszystkie rdzenie dodane). Najdłuższe polecenie, daleko wyprzedzające inne, było sort, nawet jeśli było połączone z moimi czterema rdzeniami w 100%. Zużycie pamięci RAM było bardzo akceptowalne.
Morgan Touverey Quilling
12
Następnie uruchom na 100 komputerach, więc możesz być 100 razy bardziej pewny, że wynik jest poprawny :)
dos
28

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.

DJClayworth
źródło
1
Myślę, że jest to coś pomiędzy medianą median a algorytmami szybkiego wyboru. en.wikipedia.org/wiki/Selection_algorithm
Dimath,
W kroku 4 zasobniki mogą zawierać nie tylko 10 000. Może się zdarzyć, że rozkład jest pochylony w kierunku środka, w którym może zawierać, powiedzmy, 80% danych, co nadal jest ogromne.
justhalf
Zredagowano, aby to uwzględnić.
DJClayworth,
4
W tym algorytmie wydajność nie wynosi O (n): większość liczb mogłaby trafić do segmentu „mediany” i mogłoby to działać tak źle, jak sortowanie wszystkiego.
Sklivvz
1
@WULF Doskonałe pytanie. Jest to klucz do algorytmu, a krok 1 dotyczy tego. Najlepszym rozwiązaniem, jakie wymyśliłem, jest próbkowanie liczb w celu ustalenia rozkładu.
DJClayworth
12

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;)

sfussenegger
źródło
to właśnie powiedziałem w mojej odpowiedzi tutaj :-) stackoverflow.com/a/31819222/363437
vidstige
1
@vidstige Szczerze mówiąc, tego nie czytałem, ale masz rację. moja odpowiedź jest z pewnością bardziej praktyczna, co ludzie zdają się bardziej doceniać;)
sfussenegger
To nie jest mediana chociaż mediana jest (numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2jeśli numbers.lengthnawet i numbers[numbers.length / 2]tylko wtedy, gdy numbers.lengthjest nieparzysta.
Sklivvz
@Sklivvz jest poprawne, ale nie powinno to znacząco wpływać na czas obliczania mediany.
vidstige
1
@Sklivvz masz oczywiście rację. Właśnie zaktualizowałem obliczenia mediany. Nie zmienia to jednak reszty odpowiedzi.
sfussenegger
11

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

Richard Poole
źródło
5

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.

dbasnett
źródło
3
Odrzucić komentarz wyborcy? Pomogłoby mi to zrozumieć, co mogę zrobić lepiej.
dbasnett
5
Nie jestem słabszym wyborcą, ale sortowanie miliarda liczb nie zajmie 100 razy więcej czasu niż sortowanie 10 milionów, ponieważ najgorsza złożoność sortowania listy to O (n log n). Sortowanie jest również wolniejsze o rząd wielkości, gdy zabraknie pamięci i musisz rozpocząć sortowanie na dysku.
Richard Poole
Myślę, że jesteś na dobrej drodze; Jeśli celem jest jak najszybsza odpowiedź raz, dobrym pomysłem może być sortowanie na wielu komputerach. Ale jeśli celem jest najniższy średni czas, każda maszyna przeprowadzająca własne wyszukiwanie ma większy sens.
Charlie
Zakładając, że mają ten sam czynnik (którego prawdopodobnie nie mają z powodu problemów z pamięcią), to a*(1e7)log(1e7) = 1.3sec=> a = 1.6e-9sec => a*(1e9)log(1e9) ~ 167sec, więc twoje oszacowanie nie było tak błędne.
bcorso
Twoje szacunki są zbyt zgrubne. Po pierwsze, niektóre algorytmy sortowania przyjmują wartość o (n ^ 2) w najgorszym przypadku (np. W przypadku powszechnie używanego szybkiego sortowania). Po drugie, wybrałeś testowy zestaw danych, który ma mniej więcej rozmiar twojej pamięci podręcznej L2. To wypacza wyniki. Po trzecie, ty (jak wielu innych odpowiadających) zakładasz, że „liczba” oznacza „liczbę całkowitą”. Może to oznaczać zmiennoprzecinkowe, podwójne lub dziesiętne, które mają bardzo różne charakterystyki wydajności.
Sklivvz,
5

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 9 ) 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.

vidstige
źródło
To tak naprawdę nie odpowiada na pytanie i opiera się na założeniach. Na przykład nie wiesz nawet, że są to liczby całkowite.
Sklivvz
W jaki sposób nie odpowiada na to pytanie? I tak, moja odpowiedź zakłada, że ​​liczby są liczbami całkowitymi. Starałem się jasno przedstawić swoje założenia.
vidstige
Wydaje się, że nie twierdzisz, że posiadanie liczb całkowitych jest założeniem, ani nie mówisz, jak używać 100 komputerów, o które pyta OP. Możesz obliczyć medianę w jednym węźle, ale nie jest to „najlepsze” rozwiązanie, chyba że pokażesz dlaczego. Ponadto sortowanie radix nie jest równe o (n), jeśli liczba cyfr jest różna, co w tym przypadku z pewnością ma, zgodnie z en.wikipedia.org/wiki/Radix_sort#Efficiency , jest to o (n log n)
Sklivvz
Zaczynam od stwierdzenia: „jeśli liczby całkowite są wystarczająco małe, aby zmieścić się w 32-bitowej liczbie całkowitej ” ... Sortowanie według radix wynosi O (n) dla stałego rozmiaru słowa w, zgodnie z opisem w zamieszczonym przez Ciebie linku. Tutaj zakładam stały rozmiar słowa 32.
vidstige
1
To, co robisz z 99 innymi komputerami, nie ma znaczenia w tej odpowiedzi. Możesz układać je jeden na drugim, tworząc piramidę lub spalać. Lub po prostu je zignoruj.
vidstige
3

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.

Rex Kerr
źródło
o (n / M log (n / M)) jest dosłownie o (n log n), ponieważ o (n / M log (n / M)) = 1 / M o (n (log n - log M) ) = o (n log n). Tak naprawdę nie można tego porównać z o (n) w ten sposób, ponieważ „o” w zasadzie oznacza „proporcjonalne do dla dużego bardzo n z pewną nieokreśloną stałą”. Jeśli nie znasz tych stałych, których nie możesz porównać, jednak dla wystarczająco dużego N stałe nie są dominujące. W przypadku niższych numerów wszystkie zakłady są wyłączone, o (1) może być z łatwością wolniejsze niż o (n!).
Sklivvz
@Sklivvz - ni Msą zmiennymi, które można dowolnie skalować, więc jedna obejmuje obie. W szczególności postulowałem, że M> log n, co oznacza, że ​​jeśli zależy ci na tym, żeby to było n log nzamiast po prostu n, musisz też się tym przejmować M.
Rex Kerr
3

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

user1712376
źródło
2

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

rzymski
źródło
3
W każdym razie teraz moja reprezentacja jest całkiem okrągła :)
Roman
Łączenie jest w najlepszym przypadku O (n), a medianę na pojedynczym rdzeniu można znaleźć w O (n), więc wydaje się, że tworzy to dużo dodatkowej pracy bez zysku.
Rex Kerr
2

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.

Sklivvz
źródło
1
Czy nie jest najgorszym przypadkiem (dla twojego algorytmu), gdy wszystkie liczby są równe? Jeśli mam rację, żadne z twoich wiader nigdy nie zostanie wypełnione poza środkowym, wszystkimi elementami. W ten sposób za każdym razem będziesz musiał przejść przez wszystkie elementy, postępując wykładniczo szybko do połowy interwału. Myślę, że O(n log n)w takim przypadku byłoby to . Czy ma sens ? Nawiasem mówiąc, podoba mi się twój pomysł
Dici
1
@Dici nie bardzo: po pierwsze, możesz łatwo skrócić scenariusz „wszystko to samo”, ponieważ znasz min i max. Jak powiedziałem w odpowiedzi, znajomość dystrybucji może wpłynąć na twoje wybory dotyczące zbierania; po drugie, nadal wymagałoby tego, o(n)+o(n/3)+o(n/9)+...co jest nadal, o(n)a co nie o(n log n).
Sklivvz
Z drugiej strony istnieje prawdopodobnie inny najgorszy scenariusz, dystrybucja w kształcie litery U. Muszę się trochę nad tym zastanowić, sformalizować najgorszy przypadek, ale prawdopodobnie mogłoby to być gorsze niż o(n)w tamtym przypadku z naiwnym podziałem.
Sklivvz
Mmm tak, wartości minimalne i maksymalne pomogłyby dość łatwo załatwić tę samą sprawę
Dici,
2

Ł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
Ziad Nasser
źródło
1

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.

Znak wysokiej wydajności
źródło
tutaj po prostu scalamy wszystkie liczby. Czy możemy to zrobić w lepszy sposób używając: - "możemy znaleźć medianę dwóch posortowanych list w czasie logowania. N to długość każdej listy."
anony
1
@anony - odpowiadając na swoje pytanie, ja zaprosię moje rozwiązanie do kodowania, przetestowania i wykonania. Spodziewam się, że są lepsze sposoby, ale czasami równoległe proste sposoby pozwalają mi podrapać się po głowie o naprawdę trudnych problemach.
Znak wysokiej wydajności
czy naprawdę zrobiłeś to w 7 minut? Nie mogę w to uwierzyć, nawet jeśli to prawda. Zrobiłem podobne zadanie (było to zadanie uniwersyteckie) i wdrożenie i przetestowanie wszystkich rzeczy związanych z obsługą zdalną zajęło mi około 2 godzin (użyłem Java RMI).
Roman
Rozumiem, o czym mówisz, ale z tego samego powodu DrPizza ma jeszcze szybsze rozwiązanie, które polega na sortowaniu wszystkich danych w jednym węźle i ignorowaniu pozostałych 99. Nikt z nas nie wie, jak drogie są dane. należy rozważyć przeniesienie, więc wszyscy wybieramy kompromis, który brzmi mało wiarygodnie. Twoje rozwiązanie przesyła wszystkie dane wielokrotnie, więc jestem wobec niego nieco podejrzliwy, ale z pewnością jest to rozwiązanie.
Steve Jessop
„niewyraźnie wiarygodne” - to wystarczy dla mnie @Steve! Szczególnie w odpowiedzi na niejasno nieprawdopodobne pytanie.
Znak wysokiej wydajności
1

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!

teambob
źródło
tak, po prostu zrobię wyszukiwanie binarne. Oszczędziłoby przepustowość sieci, dzwoniąc do każdego komputera tylko kilka razy. Ponadto każda maszyna może mieć „oś obrotu”, w której zamienia numery po obu stronach osi, aby zaoszczędzić czas. (pivot byłby poprzednim oszacowaniem mediany, więc następnym razem wystarczy przejść przez wszystkie liczby po jednej stronie osi)
robert king
0

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.

anonia
źródło
Zasadniczo zawsze zmniejszamy postawiony problem o co najmniej 30% i dzięki temu uzyskujemy wiele obliczeń równoległych. Każdy węzeł zaczyna się od 10 milionów i zmniejsza zestaw danych o 30% w każdej iteracji.
anony
W pierwszej iteracji szukamy liczby 500 milionów. W drugiej iteracji - jeśli liczba usuniętych liczb wynosi 300 milionów, to szukamy 200 milionów i tak dalej ...
anonia
2
Wygląda na to, że jest na dobrej drodze, ale nie wyjaśniasz zbyt jasno, jak uniknąć przypadkowego wyrzucenia mediany przy podziale 30% / 70%. Weźmy następujący kontrprzykład: załóżmy, że twoje pierwsze 29% to same zera, a wszystkie pozostałe bloki są liczone w górę o 1000, a każdy zestaw bloków jest o jeden więcej niż ostatni. Mediana 30. centyla spowoduje odrzucenie wszystkich 29% danych i nieco poniżej połowy 61% danych, czyli 29 + 30% = 59% danych. Ups, właśnie wyrzuciliśmy prawdziwą medianę! Więc najwyraźniej nie masz tego na myśli, a przynajmniej masz na myśli sprytniej, niż zinterpretowałem.
Rex Kerr
0

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?

xyz
źródło
0

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.
Cem
źródło
Masz na myśli 32 MB każdy?
Dici
Co masz na myśli, mówiąc „kontynuuj” w dolnej części listy?
Ruthvik Vaila
0

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!

Johny
źródło
0

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/

karan kapoor
źródło
0

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.

Eric B.
źródło
0

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

gandharv garg
źródło
0

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).
Bert te Velde
źródło
-1
  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.

Shiv
źródło
Co jeśli liczby są zmiennoprzecinkowe?
Sklivvz
-1

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.

leniwy chłopak
źródło
To oczywiście nieprawda i zdecydowanie odradzam, abyś nigdy nie zakładał, że prowadzący rozmowę jest głupią świnią, którą można oszukać
Dici
Haha ok, choć nie zmienia to faktu, że Twoja odpowiedź jest nieprawidłowa. Bardzo łatwo to udowodnić
Dici
OK, po przeczytaniu wykładu o statystykach myślę, że pomysł losowego wybrania 1/100 lub nawet 1/1000 z miliarda liczb i obliczenia ich mediany nie jest taki zły. To tylko przybliżona kalkulacja.
lazyboy,
-3

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.

Czarny Pan
źródło