-
Data: 2016-10-18 00:03:22
Temat: Re: Algorytmy rozproszone
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On 17.10.2016 21:29, M.M. wrote:
> Mamy proste zadanie, najprościej można je wyrazić zapytaniem sql:
>
> select * from table offset N limit M order by kryteria;
>
> Czyli trzeba wyświetlić rekordy począwszy od N+1 do N+M włącznie
> licząc zgodnie z jakimś kierunkiem sortowania - łatwizna. Cała
> trudność jednak polega na tym, że dane są rozproszone na K
> maszynach. Jaki jest do tego najszybszy algorytm? M raczej będzie
> małe, N może być bardzo duże, K też może być bardzo duże, np.
> M < 200, N > 10^9, K > 50.
Zrzut myśli w stylu grupowym;-)
Można odpytywać komputer o liczbę elementów mniejszych od x.
Znajdujemy takie x, aby suma zwróconych liczb dawała N
(odpowiednio M+N dla y), wtedy pytamy o przesłanie elementów
większych od x a mniejszych od y.
Uwaga na < i <= (w poście się tym nie przejomwałem;>) oraz
na przypadek gdy elementy się powtarzają.
Takie zapytania można robić równolegle, na raz pytając o cały
zestaw różnych xów. Ciut mniej pytań.
Wymaga logatytmicznie wielu następujących po sobie
zapytań do kompów / odpowiedzi. Prawie na pewno wolne.
Wysyłając po 100 zapyrtań/liczb wystarczy 5 zapytań...
Wymaga pewnie jakiś założeń o statystycznym rozkładzie danych.
Jeśli wszytkie obeikty są skupione w neiwiellu wartośćiach,
leżymy.
Można poprosić kopmputery o rozkłąd danych, np wszystkie decyle,
percentyle (tak, wygoglalem, jak nazywają się kwantyle rzedzu 100)
Na ich podstawie centralny komputer wyznacza zakres, w którym
znajduje sie interesujacy przedział.
Jeśli z 50 komputerów dostaniemy percentyle, dostaję
50 ciągów liczb, z których możesz wyznaczyć licby x1 i x2,
takie ze conajmniej i co najwyżej N liczb jest na lewo.
pozycje x1 i x2 będą się różnić o co najwyżej
N/100*K
Hmm, znów mizernie,, chyba, że przesyłamy znacznie więcej danych
(np 1000 liczb).
Za to jedno ułatwienie się pokazuje. Nie trzeba znać przedziału
do wycięcia bardzo dokładnie, byleby wysłąne zapytanie
zawierało interesujący przedział i nie było zbyt duże,
nadmiar obetniesz na kompue pytającym.
pzdr
bartekltg
Następne wpisy z tego wątku
- 18.10.16 05:16 M.M.
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-16 Samo rozładowywanie baterii trakcyjnej w elektryku.
- 2024-05-16 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-05-16 Warszawa => Interactive/Experience Designer <=
- 2024-05-16 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-16 Zabrze => Junior HelpDesk <=
- 2024-05-16 Warszawa => Technical Lead ( (Java Background)) <=
- 2024-05-16 Szczecin => Senior DevOps Engineer <=
- 2024-05-16 Szczecin => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-16 Śledztwo bodnatury "jak wyrok"? ["likwidator" Polskiego Radia donosi]
- 2024-05-16 Citi... zmiany warunków umowy o kartę kredytową Citibank?
- 2024-05-16 prawo jazdy z Nepalu
- 2024-05-15 Mini Netykieta polskich grup i list dyskusyjnych
- 2024-05-15 Warszawa => Key Account Manager <=
- 2024-05-15 Millenium czyli DEBILE bankowości
- 2024-05-15 Warszawa => Frontend Developer - React <=