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