vypocet percentilu na distribuovanem serveru rubrika: Programování: Jiné

10 jiri.knesl
položil/-a 4.12.2014

Mějme třeba 5 serverů, každý drží v paměti obrovskou řadu čísel. Ta čísla mohou být seřazena. V žádném případě se ale nevejdou jen na 1 server. Jak byste vypočítali třeba 50, 75, 80. percentil? Servery mohou komunikovat mezi sebou, ale stihnou si předat max 1 mega dat (celkový objem dat může jít do stovek giga).

Komentáře

  • Jakub Macek : Prosím dodat orientační počet a rozsah jednoho čísla. Jinými slovy - jedná se o obrovskou řadu běžných čísel (long int/double/...), nebo obrovskou řadu obrovských čísel? 4.12.2014
odkaz
5 Havri
odpověděl/-a 5.12.2014

V rámci jednoduchosti budu počítat medián, budu předpokládat, že znám minimum a maximum napříč všemi servery (dejme tomu 0 a 1000) a že mám bokem koordinátora.

Koordinátor řekne všem serverům, ať mi vrátí hash tabulku, kde bude obsaženo, kolik mají uloženo čísel spadajících do intervalů <0, 100), <100, 200), …, <900, 1000>. Všechny odpovědi pak po klíčích sečtu, tím pádem dostanu něco jako

<0, 100):      57
<100, 200):    105
...
<900, 1000>:   12  

V tuto chvíli si umím spočítat, ve kterém intervalu se bude nacházet medián (například je jisté, že medián nebude v prvním ani v posledním intervalu). Pokud bych spočítal, že by medián byl v intervalu <600, 700), poslal bych opět stejný dotaz všem serverům, jen s intervaly <600, 610), …, <690, 700). Opět sečtu a zjistím, že se medián nachází v intervalu <600, 610). Udělám poslední kolečko, kdy se budu ptát na jednotlivá čísla.

Naprogramovat jsem si to nezkoušel, tak nevím, jestli to funguje, snad jo. Obecný percentil půjde spočítat stejně, minimum a maximum si můžu zjistit před spuštěním algoritmu a rychlost hledání lze konfigurovat počtem intervalů, na které se v každém dotazu ptám. Koordinátora se lze taky snadno zbavit, dotaz na medián může vyvolat jeden server a pak už si to můžou servery posílat v kolečku a průběžně sčítat.

Komentáře

  • onelook : Pro celá čísla z intervalu 0 až 1000 v pohodě. Ale pokud to budou čísla z velkého intervalu (třeba typu "double") a nebudeš znát jejich rozložení, tak tohle fungovat rozumně nebude. 5.12.2014
  • Havri : Trvalo by to, to jo. Pokud by na serverech bylo 10^600 různých čísel (cca rozsah doublu), tak by při použití 10^6 intervalů bylo potřeba až 100 koleček dotaz-odpověď. Kolik dotazů by se vlastně poslalo pro stejně velkou sadu dat u tvého algoritmu? 6.12.2014

Pro zobrazení všech 10 odpovědí se prosím přihlaste:

Rychlé přihlášení přes sociální sítě:

Nebo se přihlaste jménem a heslem:

Zadejte prosím svou e-mailovou adresu.
Zadejte své heslo.