eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingAlgorytmy rozproszone
Ilość wypowiedzi w tym wątku: 4

  • 1. Data: 2016-10-17 21:29:45
    Temat: Algorytmy rozproszone
    Od: "M.M." <m...@g...com>

    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.

    Pozdrawiam


  • 2. Data: 2016-10-17 21:53:39
    Temat: Re: Algorytmy rozproszone
    Od: bartekltg <b...@g...com>

    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;

    Mów mi jeszcze ;p



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

    A jak są w tych maszynach te dane ułożone?

    Na każdej posortowane, ale zawartość każdego komputera jest "losowa"?
    Czy posortowane na komputerrach, do tego są posortowane pomiedzy
    komputerami, tzn komputer $n$ ma rekordy mniojesze niż dowolny rekord
    z $n+1$.

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

    10^9 ? Indeks zmieści się na jednym kompie;-)



    pzdr
    bartekltg




  • 3. Data: 2016-10-18 00:03:22
    Temat: Re: Algorytmy rozproszone
    Od: bartekltg <b...@g...com>

    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


  • 4. Data: 2016-10-18 05:16:32
    Temat: Re: Algorytmy rozproszone
    Od: "M.M." <m...@g...com>

    On Monday, October 17, 2016 at 9:53:40 PM UTC+2, bartekltg wrote:
    > A jak są w tych maszynach te dane ułożone?

    Struktura danych może być dowolna, ale powinna
    umożliwiać szybkie wykonywanie innych operacji, takich jak
    wstawianie, wyszukiwanie, usuwanie, modyfikowanie.


    > Na każdej posortowane, ale zawartość każdego komputera jest "losowa"?
    > Czy posortowane na komputerrach, do tego są posortowane pomiedzy
    > komputerami, tzn komputer $n$ ma rekordy mniojesze niż dowolny rekord
    > z $n+1$.

    Hmmm, myślę że z powodu zachowania uniwersalnej struktury dane
    będą rozrzucone losowo pomiędzy komputerami.


    > 10^9 ? Indeks zmieści się na jednym kompie;-)
    Racja, trochę za mało danych wymyśliłem :) To powiedzmy że


    > Można odpytywać komputer o liczbę elementów mniejszych od x.
    > [...]
    Tak, to jest jakaś metoda, ale wydaje się wolna i skomplikowana.
    Gdy na każdym komputerze jest N danych, to trzeba wszystkie
    komputery zmusić LogN razy do podania ilości większych
    elementów. Gdy już mamy konkretny element, to łatwo, wystarczy
    połączyć wyniki z każdego komputera.


    > Takie zapytania można robić równolegle, na raz pytając o cały
    > zestaw różnych xów. Ciut mniej pytań.
    Dobry pomysł.


    > [...]
    > 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.
    Też jest to jakaś optymalizacja. Większy transfer, ale mniej
    odpytań - powinno się opłacać. Wygląda na to, że jest to do
    zrobienia w kilku odpytaniach wszystkich komputerów z klastra.


    Pozdrawiam


strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: