streamalism.org

1. Prehľad

V tomto návode Naučíme sa, ako vypočítať strednú hodnotu prúdu celých čísel.

Pokračujeme uvedením problému s príkladmi, potom problém analyzujeme a nakoniec implementujeme niekoľko riešení v Jave.

2. Vyhlásenie o probléme

Medián je stredná hodnota usporiadaného súboru údajov. Pre množinu celých čísel existuje práve toľko prvkov, ktoré sú menšie ako stredná hodnota a väčšie.

V objednanej sade:

• nepárny počet celých čísel, stredný prvok je medián - v usporiadanej množine { 5, 7, 10 }, medián je 7
• párny počet celých čísel, neexistuje stredný prvok; medián sa počíta ako priemer dvoch stredných prvkov - v usporiadanej množine {5, 7, 8, 10}, medián je (7 + 8) / 2 = 7.5

Teraz predpokladajme, že namiesto konečnej množiny čítame celé čísla z dátového toku. Môžeme definovať medián prúdu celých čísel ako stredná hodnota množiny celých čísel, ktorá sa doteraz čítala.

Formalizujme vyhlásenie o probléme. Na základe vstupu prúdu celých čísel musíme navrhnúť triedu, ktorá vykonáva nasledujúce dve úlohy pre každé celé číslo, ktoré čítame:

1. Pridajte celé číslo do množiny celých čísel
2. Nájdite medián celých čísel, ktoré boli doteraz načítané

Napríklad:

pridať 5 // setriedená sada = {5}, veľkosť = 1 získať strednú hodnotu -> 5 pridať 7 // triedenú množinu = {5, 7}, veľkosť = 2 získať strednú hodnotu -> (5 + 7) / 2 = 6 pridať 10 // setriedená množina = {5, 7, 10}, veľkosť = 3 získať strednú hodnotu -> 7 pridať 8 // triedenú množinu = {5, 7, 8, 10}, veľkosť = 4 získať strednú hodnotu -> ( 7 + 8) / 2 = 7,5 .. 

Aj keď prúd nie je konečný, môžeme predpokladať, že dokážeme uchovať všetky prvky prúdu v pamäti naraz.

Naše úlohy môžeme reprezentovať ako nasledujúce operácie v kóde:

void add (int num); double getMedian (); 

3. Naivný prístup

3.1. Zoradené Zoznam

Začnime jednoduchou myšlienkou - môžeme vypočítať medián zoradeného zoznam celých čísel prístupom k prostrednému prvku alebo k stredným dvom prvkom prvku zoznamindexom. Časová zložitosť getMedian prevádzka je O (1).

Pri pridávaní nového celého čísla musíme určiť jeho správnu pozíciu v zoznam také, ktoré zoznam zostáva triedený. Túto operáciu je možné vykonať v O (n) čas, kde n je veľkosť zoznam. Celkové náklady na pridanie nového prvku do zoznam a výpočet nového mediánu je O (n).

3.2. Zlepšovanie naivného prístupu

The pridať prevádzka beží v lineárnom čase, čo nie je optimálne. Pokúsme sa to vyriešiť v tejto časti.

Môžeme rozdeliť zoznam do dvoch triedených zoznamy – menšia polovica celých čísel je zoradená v zostupnom poradí a väčšia polovica celých čísel v zostupnom poradí. Môžeme pridať nové celé číslo do príslušnej polovice tak, aby mala veľkosť zoznamy sa líši najviac o 1:

ak je prvok menší ako min. prvok väčšej polovice: vložte do menšej polovice pri vhodnom indexe, ak je menšia polovica oveľa väčšia ako väčšia polovica: odstráňte max. prvok menšej polovice a vložte na začiatok väčšej polovice (vyváženie) inak vložte do väčšej polovice pri príslušnom indexe: ak je väčšia polovica oveľa väčšia ako menšia polovica: odstráňte min. prvok väčšej polovice a vložiť na začiatok menšej polovice (vyváženie) 

Teraz môžeme vypočítať medián:

ak zoznamy obsahujú rovnaký počet prvkov: medián = (max. prvok menšej polovice + min. prvok väčšej polovice) / 2 iné, ak menšia polovica obsahuje viac prvkov: medián = max. prvok menšej polovice inak, ak väčšia polovica obsahuje viac prvkov: medián = min. prvok väčšej polovice

Aj keď sme len zlepšili časovú zložitosť pridať fungovanie nejakým konštantným faktorom, dosiahli sme pokrok.

Poďme analyzovať prvky, ku ktorým pristupujeme v dvoch zoradených zoznamy. Potenciálne máme prístup ku každému prvku, keď ho posúvame počas (zoradené) pridať prevádzka. Dôležitejšie je, že počas minima získavame prístup k minimu a maximu (extrému) väčšej a menšej polovice pridať operácia na vyváženie a počas getMedian prevádzka.

To vidíme extrémy sú prvými prvkami ich príslušných zoznamov. Takže, my sa musí optimalizovať pre prístup k prvku v indexe 0 za každú polovicu zlepšiť celkový čas chodu systému pridať prevádzka.

4. Halda- prístup na základe

Poďme vylepšiť naše chápanie problému uplatnením toho, čo sme sa naučili z nášho naivného prístupu:

1. Musíme dostať minimálny / maximálny prvok množiny údajov O (1) čas
2. Prvky sa nemusia uchovávať v zoradenom poradí pokiaľ dokážeme efektívne získať minimálny / maximálny prvok
3. Musíme nájsť prístup na pridanie prvku do našej množiny údajov, ktorý stojí menej ako O (n) čas

Ďalej sa pozrieme na dátovú štruktúru haldy, ktorá nám pomáha efektívne dosiahnuť naše ciele.

4.1. Halda dátová štruktúra

Halda je a dátová štruktúra, ktorá je zvyčajne implementovaná s poľom, ale možno ju považovať za binárny strom.

Haldy sú obmedzené vlastnosťou haldy:

4.1.1. Max–halda Majetok

(Podradený) uzol nemôže mať väčšiu hodnotu ako jeho nadradený uzol. Preto v a max-halda, koreňový uzol má vždy najväčšiu hodnotu.

4.1.2. Min–halda Majetok

(Nadradený) uzol nemôže mať väčšiu hodnotu ako jeho podradené položky. Teda v a min. halda, koreňový uzol má vždy najmenšiu hodnotu.

V Jave sa PriorityQueue trieda predstavuje haldu. Prejdime k nášmu prvému riešeniu pomocou hromad.

4.2. Prvé riešenie

Nahraďme zoznamy v našom naivnom prístupe dvoma hromadami:

• Hromada min, ktorá obsahuje väčšiu polovicu prvkov a minimálny prvok v koreni
• Maximálna hromada, ktorá obsahuje menšiu polovicu prvkov a maximálny prvok v koreňovom adresári

Teraz môžeme pridať prichádzajúce celé číslo do príslušnej polovice porovnaním s koreňom min haldy. Ďalej, ak sa po vložení veľkosť jednej hromady líši od veľkosti druhej hromady o viac ako 1, môžeme vyvážiť hromady, čím sa zachová rozdiel veľkosti najviac 1:

if size (minHeap)> size (maxHeap) + 1: remove root element of minHeap, insert into maxHeap if size (maxHeap)> size (minHeap) + 1: remove root element of maxHeap, insert into minHeap

S týmto prístupom môžeme vypočítať medián ako priemer koreňových prvkov oboch hald, ak je veľkosť dvoch háld rovnaká. Inak by koreňový prvok haldy s viacerými prvkami je stredná hodnota.

Použijeme PriorityQueue triedy, aby zastupovali haldy. Predvolená vlastnosť haldy a PriorityQueue je min. Maximálnu hromadu môžeme vytvoriť pomocou a Comparator.reverserOrder ktorý využíva obrátený prirodzený poriadok:

trieda MedianOfIntegerStream {súkromná fronta minHeap, maxHeap; MedianOfIntegerStream () {minHeap = new PriorityQueue (); maxHeap = new PriorityQueue (Comparator.reverseOrder ()); } void add (int num) {if (! minHeap.isEmpty () && num minHeap.size () + 1) {minHeap.offer (maxHeap.poll ()); }} else {minHeap.offer (num); if (minHeap.size ()> maxHeap.size () + 1) {maxHeap.offer (minHeap.poll ()); }}} double getMedian () {int median; if (minHeap.size () maxHeap.size ()) {median = minHeap.peek (); } else {median = (minHeap.peek () + maxHeap.peek ()) / 2; } medián návratu; }}

Predtým, ako analyzujeme čas chodu nášho kódu, pozrime sa na časovú zložitosť haldy, ktorú sme použili:

find-min / find-max O (1) delete-min / delete-max O (log n) vložiť O (log n) 

Takže getMedian operáciu je možné vykonať v O (1) čas, ako to vyžaduje nájsť-min a nájsť-max iba funkcie. Časová zložitosť pridať prevádzka je O (log n) - tri vložiť/vymazať volá každý vyžaduje O (log n) čas.

4.3. Invariantné riešenie haldy

V našom predchádzajúcom prístupe sme porovnali každý nový prvok s koreňovými prvkami háld. Poďme preskúmať iný prístup využívajúci haldu, v ktorej môžeme využiť vlastnosť haldy na pridanie nového prvku do príslušnej polovice.

Ako sme urobili pre naše predchádzajúce riešenie, začíname dvoma hromadami - minimálnou hromadou a maximálnou hromadou. Ďalej si predstavíme podmienku: veľkosť maximálnej haldy musí byť (n / 2) veľkosť haldy môže byť vždy (n / 2) alebo (n / 2) + 1, v závislosti od celkového počtu prvkov v dvoch hromadách. Inými slovami, môžeme povoliť, aby iba min halda mala ďalší prvok, keď je celkový počet prvkov nepárny.

S našou invariantou veľkosti haldy môžeme vypočítať medián ako priemer koreňových prvkov oboch háld, ak sú veľkosti oboch háld (n / 2). Inak by koreňovým prvkom min haldy je medián.

Keď pridáme nové celé číslo, máme dva scenáre:

1. Spolu č. existujúcich prvkov je párna veľkosť (min. halda) == veľkosť (max. halda) == (n / 2) 2. Celkové č. existujúcich prvkov je nepárna veľkosť (max. halda) == (n / 2) veľkosť (min. halda) == (n / 2) + 1 

Invariant môžeme udržať tak, že do jednej z háld pridáme nový prvok a zakaždým vyvažujeme:

Vyváženie funguje presunutím najväčšieho prvku z maximálnej haldy do minimálnej haldy alebo presunutím najmenšieho prvku z minimálnej haldy do maximálnej haldy. Týmto spôsobom však neporovnávame nové celé číslo pred jeho pridaním do haldy, následné vyváženie zaručuje, že ctíme podkladový invariant menších a väčších polovíc.

Implementujme naše riešenie v Jave pomocou Prioritné fronty:

trieda MedianOfIntegerStream {súkromná fronta minHeap, maxHeap; MedianOfIntegerStream () {minHeap = new PriorityQueue (); maxHeap = new PriorityQueue (Comparator.reverseOrder ()); } void add (int num) {if (minHeap.size () == maxHeap.size ()) {maxHeap.offer (num); minHeap.offer (maxHeap.poll ()); } else {minHeap.offer (num); maxHeap.offer (minHeap.poll ()); }} double getMedian () {int median; if (minHeap.size ()> maxHeap.size ()) {median = minHeap.peek (); } else {median = (minHeap.peek () + maxHeap.peek ()) / 2; } medián návratu; }}

Časová zložitosť našich prevádzok zostáva nezmenená: getMedian náklady O (1) čas, zatiaľ čo pridať beží v čase O (log n) s úplne rovnakým počtom operácií.

Obe hromadné riešenia ponúkajú podobné priestorové a časové zložitosti. Aj keď je druhé riešenie chytré a má čistejšiu implementáciu, prístup nie je intuitívny. Na druhej strane, prvé riešenie sleduje našu intuíciu prirodzene a o jeho správnosti je ľahšie uvažovať pridať prevádzka.

5. Záver

V tomto tutoriáli sme sa naučili, ako vypočítať strednú hodnotu prúdu celých čísel. Vyhodnotili sme niekoľko prístupov a implementovali sme niekoľko rôznych riešení v prostredí Java pomocou PriorityQueue.

Ako obvykle je zdrojový kód všetkých príkladov k dispozícii na serveri GitHub.