streamalism.org

1. Pregled

U ovom vodiču, naučit ćemo kako izračunati medijan toka cijelih brojeva.

Nastavit ćemo navodeći problem s primjerima, zatim analizirati problem i na kraju implementirati nekoliko rješenja u Javi.

2. Izjava o problemu

Medijan je srednja vrijednost uređenog skupa podataka. Za skup cijelih brojeva postoji jednako toliko elemenata manje od medijana koliko je veće.

U uređenom nizu:

• neparan broj cijelih brojeva, srednji je element medijan - u poredanom skupu { 5, 7, 10 }, medijan je 7
• paran broj cijelih brojeva, nema srednjeg elementa; medijan se izračunava kao prosjek dva srednja elementa - u uređenom skupu {5, 7, 8, 10}, medijan je (7 + 8) / 2 = 7.5

Pretpostavimo sada da umjesto konačnog skupa čitamo cijele brojeve iz toka podataka. Možemo definirati medijan struje cijelih brojeva kao do sada pročitana medijana skupa cijelih brojeva.

Formalizirajmo izjavu o problemu. S obzirom na ulaz protoka cijelih brojeva, moramo dizajnirati klasu koja izvodi slijedeća dva zadatka za svaki čitani broj:

1. Dodajte cijeli broj skupu cijelih brojeva
2. Pronađite medijanu do sada pročitanih cijelih brojeva

Na primjer:

dodaj 5 // sorted-set = {5}, size = 1 dobij medijanu -> 5 dodaj 7 // sorted-set = {5, 7}, size = 2 dobij medijanu -> (5 + 7) / 2 = 6 dodaj 10 // sorted-set = {5, 7, 10}, size = 3 get mediana -> 7 dodaj 8 // sorted-set = {5, 7, 8, 10}, size = 4 get mediana -> ( 7 + 8) / 2 = 7,5 .. 

Iako tok nije konačan, možemo pretpostaviti da možemo odjednom zadržati sve elemente toka u memoriji.

Naše zadatke možemo predstaviti kao sljedeće operacije u kodu:

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

3. Naivni pristup

3.1. Poredano Popis

Počnimo s jednostavnom idejom - možemo izračunati medijan sortiranja popis cijelih brojeva pristupom srednjem elementu ili dva srednja elementa popis, indeksom. Vremenska složenost getMedian operacija je O (1).

Dok dodajemo novi cijeli broj, moramo odrediti njegov točan položaj u popis takav da je popis ostaje razvrstano. Ova se operacija može izvesti u Na) vrijeme, gdje n je veličina popis. Dakle, ukupni troškovi dodavanja novog elementa u popis a izračunavanje nove medijane je Na).

3.2. Poboljšanje naivnog pristupa

The dodati rad se odvija u linearnom vremenu, što nije optimalno. Pokušajmo to riješiti u ovom odjeljku.

Možemo podijeliti popis u dvije sortirane popisa – manja polovica cijelih brojeva razvrstana prema opadajućem redoslijedu, a veća polovica cijelih brojeva prema rastućem redoslijedu. Možemo dodati novi cijeli broj u odgovarajuću polovicu tako da veličina popisa razlikuje se za najviše 1:

ako je element manji od min. element veće polovice: umetnite u manju polovicu s odgovarajućim indeksom ako je manja polovica puno veća od veće polovice: uklonite maks. element manje polovice i umetnite na početak veće polovice (rebalans), ostalo umetnite u veću polovicu s odgovarajućim indeksom: ako je veća polovica puno veća od manje polovice: uklonite min. element veće polovice i umetnite na početak manje polovice (rebalans) 

Sada možemo izračunati medijan:

ako popisi sadrže jednak broj elemenata: medijan = (maks. element manje polovice + min. element veće polovice) / 2 ostalo ako manja polovica sadrži više elemenata: medijan = maks. element manje polovice else ako veća polovica sadrži više elemenata: medijan = min. element veće polovice

Iako smo samo poboljšali vremensku složenost dodati djelovanjem nekog stalnog čimbenika, postigli smo napredak.

Analizirajmo elemente kojima pristupamo u dva sortirana popisa. Potencijalno pristupamo svakom elementu dok ga pomičemo tijekom (sortirano) dodati operacija. Još važnije, pristupamo minimumu i maksimumu (ekstremuma) veće, odnosno manje polovice, tijekom dodati operacija za rebalans i tijekom getMedian operacija.

To možemo vidjeti ekstremi su prvi elementi njihovih popisa. Dakle, mi mora optimizirati za pristup elementu u indeksu 0 za svaku polovicu kako bi se poboljšalo ukupno vrijeme rada dodati operacija.

4. Hrpapristup na temelju

Pročistimo svoje razumijevanje problema, primjenjujući ono što smo naučili iz našeg naivnog pristupa:

1. Moramo dobiti minimum / maksimum elementa skupa podataka u O (1) vrijeme
2. Elementi se ne moraju čuvati u razvrstanom redoslijedu sve dok možemo učinkovito / minimalno dobiti element / maksimum
3. Moramo pronaći pristup za dodavanje elementa u naš skup podataka koji košta manje od Na) vrijeme

Dalje ćemo razmotriti strukturu podataka Heap koja nam pomaže da učinkovito postignemo svoje ciljeve.

4.1. Struktura podataka hrpe

Hrpa je struktura podataka koja se obično provodi s nizom, ali se može smatrati binarnim stablom.

Hrpe su ograničene svojstvom hrpe:

4.1.1. Maks–gomila Vlasništvo

(Podređeni) čvor ne može imati vrijednost veću od vrijednosti svog roditelja. Dakle, u a max-hrpa, korijenski čvor uvijek ima najveću vrijednost.

4.1.2. Min–gomila Vlasništvo

(Nadređeni) čvor ne može imati vrijednost veću od vrijednosti njegove djece. Dakle, u a min-hrpa, korijenski čvor uvijek ima najmanju vrijednost.

U Javi je PriorityQueue razred predstavlja hrpu. Krenimo na naše prvo rješenje koristeći gomile.

4.2. Prvo rješenje

Zamijenimo popise u našem naivnom pristupu s dvije hrpe:

• Minimalna hrpa koja sadrži veću polovicu elemenata, s minimalnim elementom u korijenu
• Maksimalna hrpa koja sadrži manju polovicu elemenata, s maksimalnim elementom u korijenu

Sada možemo dodati dolazni cijeli broj relevantnoj polovici uspoređujući ga s korijenom min-hrpe. Dalje, ako se nakon umetanja veličina jedne hrpe razlikuje od druge hrpe za više od 1, možemo hrpe uravnotežiti, održavajući tako razliku u veličini od najviše 1:

ako je veličina (minHeap)> veličina (maxHeap) + 1: uklonite korijenski element minHeap, umetnite u maxHeap ako je size (maxHeap)> size (minHeap) + 1: uklonite korijenski element maxHeap, umetnite u minHeap

Ovim pristupom možemo izračunati medijan kao prosjek korijenskih elemenata obje hrpe, ako je veličina dvije hrpe jednaka. Inače, korijenski element hrpe s više elemenata je medijan.

Koristit ćemo PriorityQueue razred koji predstavlja gomile. Zadana svojstva hrpe a PriorityQueue je min-hrpa. Maksimalnu hrpu možemo stvoriti pomoću a Usporednik.reverserOrder koji koristi obrnuto od prirodnog poretka:

klasa MedianOfIntegerStream {private Queue minHeap, maxHeap; MedianOfIntegerStream () {minHeap = novi PriorityQueue (); maxHeap = novi prioritetni red (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 medijana; if (minHeap.size () maxHeap.size ()) {medijana = minHeap.peek (); } else {medijana = (minHeap.peek () + maxHeap.peek ()) / 2; } medijan povrata; }}

Prije nego što analiziramo vrijeme izvođenja našeg koda, pogledajmo vremensku složenost operacija hrpe koje smo koristili:

find-min / find-max O (1) delete-min / delete-max O (log n) umetanje O (log n) 

Dakle, getMedian operacija se može izvesti u O (1) vrijeme kako to zahtijeva naći-min i pronađi-maks samo funkcije. Vremenska složenost dodati operacija je O (zapisnik n) - tri umetnuti/izbrisati poziva svaki zahtijevajući O (zapisnik n) vrijeme.

4.3. Nepromjenjivo rješenje veličine hrpe

U našem prethodnom pristupu usporedili smo svaki novi element s korijenskim elementima gomila. Istražimo drugi pristup korištenjem hrpe u kojem možemo iskoristiti svojstvo hrpe kako bismo dodali novi element u odgovarajuću polovicu.

Kao što smo učinili za naše prethodno rješenje, započinjemo s dvije hrpe - minimalnom hrpom i maksimalnom hrpom. Dalje, uvedimo uvjet: veličina max-hrpe mora biti (n / 2) cijelo vrijeme, dok veličina min-hrpe može biti bilo koja (n / 2) ili (n / 2) + 1, ovisno o ukupnom broju elemenata u dvije hrpe. Drugim riječima, možemo dopustiti da samo min-hrpa ima dodatni element, ako je ukupan broj elemenata neparan.

S našom invarijantom veličine hrpe možemo izračunati medijan kao prosjek korijenskih elemenata obje hrpe, ako su veličine obje hrpe (n / 2). Inače, korijenski element min-hrpe je medijan.

Kada dodamo novi cijeli broj, imamo dva scenarija:

1. Ukupno br. postojećih elemenata je parna veličina (min-hrpa) == veličina (max-heap) == (n / 2) 2. Ukupni br. postojećih elemenata je neparna veličina (max-heap) == (n / 2) size (min-heap) == (n / 2) + 1 

Invarijantu možemo održati dodavanjem novog elementa na jednu od hrpa i ponovnim uravnoteženjem svaki put:

Ponovno uravnoteženje djeluje premještanjem najvećeg elementa iz max-heap u min-heap ili pomicanjem najmanjeg elementa iz min-heap u max-heap. Ovim putem, doduše ne uspoređujemo novi cijeli broj prije nego što ga dodamo u hrpu, naknadno ponovno uravnoteženje osigurava poštivanje temeljne invarijante manjih i većih polovica.

Primijenimo svoje rješenje u Javi koristeći PriorityQueues:

klasa MedianOfIntegerStream {private Queue minHeap, maxHeap; MedianOfIntegerStream () {minHeap = novi PriorityQueue (); maxHeap = novi prioritetni red (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 medijana; if (minHeap.size ()> maxHeap.size ()) {medijana = minHeap.peek (); } else {medijana = (minHeap.peek () + maxHeap.peek ()) / 2; } medijan povrata; }}

Složenost vremena našeg poslovanja ostaje nepromijenjena: getMedian troškovi O (1) vrijeme, dok dodati trči u vremenu O (zapisnik n) s potpuno istim brojem operacija.

Oba rješenja temeljena na hrpi nude slične prostorne i vremenske složenosti. Iako je drugo rješenje pametno i ima čistiju implementaciju, pristup nije intuitivan. S druge strane, prvo rješenje prirodno slijedi našu intuiciju i lakše je rasuđivati ​​o ispravnosti dodati operacija.

5. Zaključak

U ovom smo tutorijalu naučili kako izračunati medijan struje cijelih brojeva. Procijenili smo nekoliko pristupa i implementirali nekoliko različitih rješenja u Javi PriorityQueue.

Kao i obično, izvorni kod za sve primjere dostupan je na GitHubu.