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, Set1
aw Set2
powstał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?
algorithm
distributed-computing
anonia
źródło
źródło
Odpowiedzi:
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.
źródło
źródło
time
poleceniem zastosowanym do całego rurociągu zajęło toreal=36m24s
(„zegar ścienny”),user=113m15s
(„czas równoległy”, wszystkie rdzenie dodane). Najdłuższe polecenie, daleko wyprzedzające inne, byłosort
, nawet jeśli było połączone z moimi czterema rdzeniami w 100%. Zużycie pamięci RAM było bardzo akceptowalne.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.
źródło
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.
Wyjście na moim komputerze:
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;)
źródło
(numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2
jeślinumbers.length
nawet inumbers[numbers.length / 2]
tylko wtedy, gdynumbers.length
jest nieparzysta.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).
źródło
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.
źródło
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.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
time
podobnymidaje czas pracy na moim komputerze 1m49,293s. Najprawdopodobniej większość czasu działania to również operacje we / wy dysku.
źródło
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 M
czasu i wszystkie rdzenie muszą na to czekać, więc to naprawdę marnowanieM^2 log M
potencjalny 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 standardowejO(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śliM >> log(n/M)
iM^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.
źródło
n
iM
są zmiennymi, które można dowolnie skalować, więc jedna obejmuje obie. W szczególności postulowałem, żeM
>log n
, co oznacza, że jeśli zależy ci na tym, żeby to byłon log n
zamiast po prostun
, musisz też się tym przejmowaćM
.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
źródło
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).
źródło
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
Ś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.
Teraz możemy bezpośrednio obliczyć medianę: mamy taką sytuację
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.
źródło
O(n log n)
w takim przypadku byłoby to . Czy ma sens ? Nawiasem mówiąc, podoba mi się twój pomysło(n)+o(n/3)+o(n/9)+...
co jest nadal,o(n)
a co nieo(n log n)
.o(n)
w tamtym przypadku z naiwnym podziałem.Łatwiejszą metodą jest stosowanie liczb ważonych.
źródło
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.
źródło
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:
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:
Istnieje 1 węzeł nadrzędny i 99 węzłów podrzędnych. Węzły potomne mają dwa wywołania API:
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:
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!
źródło
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.
źródło
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?
źródło
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.
źródło
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!
źródło
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/
źródło
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.
źródło
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
źródło
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ę.
Złożoność czasowa:
źródło
Podziel 1 miliard liczb na 100 maszyn. Każda maszyna będzie miała 10 ^ 7 liczb.
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.
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.
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:
Powyższe można zapisać w tablicy bitowej jako:
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.
źródło
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.
źródło
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.
źródło