vypocet percentilu na distribuovanem serveru rubrika: Programování: Jiné
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).
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:
Nebo se přihlaste jménem a heslem:
Komentáře