„Przeszukałem sieć i odwiedziłem stronę wiki dla mediany algorytmu mediany. Ale nie mogę znaleźć wyraźnego stwierdzenia w moim pytaniu:
Jeśli ma bardzo dużą listę liczb całkowitych(Rozmiar TB) i chce znaleźć medianę tej listy w sposób rozproszony, złamałby listę na podlisty o różnych rozmiarach (lub równych nie ma znaczenia), a następnie przystąpił do obliczenia median tych mniejszych -listy, a następnie obliczyć medianę tych median w medianie oryginalnej dużej listy?
Ponadto, czy to stwierdzenie jest również poprawne dla którejkolwiek z k-tych statystyk? Byłbym zainteresowany linkami do badań itp. W tej dziedzinie.
Odpowiedzi:
12 dla odpowiedzi № 1Odpowiedź na twoje pytanie brzmi: nie.
Jeśli chcesz zrozumieć, jak właściwie wybrać k-tego rzędu statystyk (w tym medianaoczywiście) w ustawieniu równoległym (ustawienie rozproszone oczywiście nie różni się zbytnio), spójrz na ten ostatni artykuł, w którym zaproponowałem nowy algorytm poprawiający poprzedni stan algorytmu wyboru równoległego:
Deterministyczne algorytmy wyboru równoległego na gruboziarnistych wielokomputerach
Tutaj używamy dwóch ważonych 3-median jako pivotów,i partycjonuj te elementy, używając partycjonowania pięciostopniowego. Zaimplementowaliśmy i przetestowaliśmy algorytm za pomocą MPI. Wyniki są bardzo dobre, biorąc pod uwagę, że jest to algorytm deterministyczny wykorzystujący najgorszy przypadek O(n) algorytm wyboru. Korzystanie z randomizacji O(n) Algorytm QuickSelect zapewnia niezwykle szybki algorytm równoległy.
7 dla odpowiedzi nr 2
Jeśli ma bardzo dużą listę liczb całkowitych(Rozmiar TB) i chce znaleźć medianę tej listy w sposób rozproszony, złamałby listę na podlisty o różnych rozmiarach (lub równych nie ma znaczenia), a następnie przystąpił do obliczenia median tych mniejszych -listy, a następnie obliczyć medianę tych median w medianie oryginalnej dużej listy?
Nie. Rzeczywista mediana całej listy niekoniecznie jest medianą którejkolwiek z podlist.
Średnie mediany mogą dać dobry wybórprzestaw, aby szybko wybrać, dzięki temu, że znajduje się bliżej rzeczywistej mediany niż losowo wybrany element, ale będziesz musiał wykonać resztę algorytmu szybkiego wyboru, aby zlokalizować rzeczywistą medianę większej listy.