Path: csiph.com!news.mixmin.net!news.unit0.net!news.nask.pl!news.nask.org.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail From: bartekltg Newsgroups: pl.comp.programming Subject: Re: Algorytmy rozproszone Date: Tue, 18 Oct 2016 00:03:22 +0200 Organization: ATMAN - ATM S.A. Lines: 60 Message-ID: References: <335392f2-c1ab-4be4-9250-7eb468c75ce5@googlegroups.com> NNTP-Posting-Host: 89-70-119-159.dynamic.chello.pl Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: node2.news.atman.pl 1476741802 11586 89.70.119.159 (17 Oct 2016 22:03:22 GMT) X-Complaints-To: usenet@atman.pl NNTP-Posting-Date: Mon, 17 Oct 2016 22:03:22 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.3.0 In-Reply-To: <335392f2-c1ab-4be4-9250-7eb468c75ce5@googlegroups.com> Xref: csiph.com pl.comp.programming:29124 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