streamalism.org

1. Overzicht

In deze tutorial we zullen leren hoe we de mediaan van een stroom gehele getallen kunnen berekenen.

We gaan door met het aangeven van het probleem met voorbeelden, analyseren het probleem en implementeren uiteindelijk verschillende oplossingen in Java.

2. Probleemstelling

Mediaan is de middelste waarde van een geordende dataset. Voor een reeks gehele getallen zijn er evenveel elementen kleiner dan de mediaan als groter.

In een geordende set van:

• oneven aantal gehele getallen, het middelste element is de mediaan - in de geordende set { 5, 7, 10 }, de mediaan is 7
• even aantal gehele getallen, er is geen middenelement; de mediaan wordt berekend als het gemiddelde van de twee middelste elementen - in de geordende set {5, 7, 8, 10}, de mediaan is (7 + 8) / 2 = 7.5

Laten we nu aannemen dat we in plaats van een eindige set, gehele getallen uit een datastroom lezen. We kunnen de mediaan van een stroom van gehele getallen als de mediaan van de reeks tot nu toe gelezen gehele getallen.

Laten we de probleemstelling formaliseren. Gegeven een invoer van een stroom gehele getallen, moeten we een klasse ontwerpen die de volgende twee taken uitvoert voor elk geheel getal dat we lezen:

1. Voeg het gehele getal toe aan de reeks gehele getallen
2. Zoek de mediaan van de tot nu toe gelezen gehele getallen

Bijvoorbeeld:

voeg 5 // sort-set = {5}, size = 1 haal mediaan toe -> 5 voeg 7 toe // sort-set = {5, 7}, size = 2 haal mediaan -> (5 + 7) / 2 = 6 add 10 // sort-set = {5, 7, 10}, size = 3 haal mediaan -> 7 add 8 // sort-set = {5, 7, 8, 10}, size = 4 haal mediaan -> ( 7 + 8) / 2 = 7,5 .. 

Hoewel de stroom niet eindig is, kunnen we aannemen dat we alle elementen van de stroom tegelijk in het geheugen kunnen bewaren.

We kunnen onze taken weergeven als de volgende bewerkingen in code:

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

3. Naïeve benadering

3.1. Gesorteerd Lijst

Laten we beginnen met een eenvoudig idee - we kunnen de mediaan van een gesorteerd lijst van gehele getallen door toegang te krijgen tot het middelste element of de middelste twee elementen van de lijst, op index. De tijdcomplexiteit van de getMedian operatie is O (1).

Bij het toevoegen van een nieuw geheel getal moeten we de juiste positie in de lijst zodanig dat de lijst blijft gesorteerd. Deze bewerking kan worden uitgevoerd in Aan) tijd, waar n is de grootte van de lijst. Dus de totale kosten voor het toevoegen van een nieuw element aan het lijst en het berekenen van de nieuwe mediaan is Aan).

3.2. Verbetering van de naïeve benadering

De toevoegen operatie verloopt in lineaire tijd, wat niet optimaal is. Laten we proberen dat in deze sectie aan te pakken.

We kunnen het lijst in twee gesorteerd lijsten – de kleinere helft van de gehele getallen in aflopende volgorde gesorteerd, en de grotere helft van de gehele getallen in oplopende volgorde. We kunnen een nieuw geheel getal aan de juiste helft toevoegen, zodat de grootte van de lijsten verschilt maximaal 1:

als element kleiner is dan min. element met grotere helft: steek in kleinere helft met de juiste index als de kleinere helft veel groter is dan de grotere helft: verwijder max. element van kleinere helft en invoegen aan het begin van grotere helft (opnieuw in evenwicht brengen) anders invoegen in grotere helft met de juiste index: als de grotere helft veel groter is dan de kleinere helft: verwijder min. element van grotere helft en invoegen aan het begin van kleinere helft (opnieuw in evenwicht brengen) 

Nu kunnen we de mediaan berekenen:

als lijsten een gelijk aantal elementen bevatten: mediaan = (max. element van kleinere helft + min. element van grotere helft) / 2 anders als kleinere helft meer elementen bevat: mediaan = max. element van kleinere helft anders als grotere helft meer elementen bevat: median = min. element van grotere helft

Hoewel we alleen de tijdcomplexiteit van het toevoegen werking door een constante factor, hebben we vooruitgang geboekt.

Laten we de elementen analyseren waartoe we toegang hebben in de twee gesorteerd lijsten. We hebben mogelijk toegang tot elk element terwijl we ze verplaatsen tijdens de (gesorteerde) toevoegen operatie. Wat nog belangrijker is, we hebben toegang tot het minimum en maximum (extremums) van respectievelijk de grotere en kleinere helften tijdens de toevoegen operatie voor het opnieuw in evenwicht brengen en tijdens de getMedian operatie.

Dat kunnen we zien extremums zijn de eerste elementen van hun respectieve lijsten. Zodat we moet optimaliseren voor toegang tot het element op index 0 voor elke helft om de algehele looptijd van de toevoegen operatie.

4. Hoop-gebaseerde aanpak

Laten we ons begrip van het probleem verfijnen door toe te passen wat we hebben geleerd van onze naïeve benadering:

1. We moeten het minimum / maximum-element van een dataset binnenhalen O (1) tijd
2. De elementen hoeven niet in een gesorteerde volgorde te worden bewaard zolang we het minimum / maximum element efficiënt kunnen krijgen
3. We moeten een benadering vinden om een ​​element aan onze dataset toe te voegen dat minder kost dan Aan) tijd

Vervolgens kijken we naar de Heap-datastructuur die ons helpt onze doelen efficiënt te bereiken.

4.1. Heap-gegevensstructuur

Hoop is een datastructuur die meestal wordt geïmplementeerd met een array, maar kan worden gezien als een binaire boom.

Heaps worden beperkt door de heap-eigenschap:

4.1.1. Max. Hoogte–hoop eigendom

Een (kind) knooppunt kan geen waarde hebben die groter is dan die van zijn bovenliggende node. Vandaar dat in een max-heapheeft het hoofdknooppunt altijd de grootste waarde.

4.1.2. Min–hoop eigendom

Een (bovenliggend) knooppunt kan geen waarde hebben die groter is dan die van zijn kinderen. Dus in een min-hoopheeft het rootknooppunt altijd de kleinste waarde.

In Java is het Prioriteits-rij klasse vertegenwoordigt een hoop. Laten we verder gaan met onze eerste oplossing met behulp van hopen.

4.2. Eerste oplossing

Laten we de lijsten in onze naïeve benadering vervangen door twee hopen:

• Een min-heap die de grootste helft van de elementen bevat, met het minimumelement aan de wortel
• Een max-heap die de kleinere helft van de elementen bevat, met het maximale element bij de wortel

Nu kunnen we het inkomende gehele getal aan de relevante helft toevoegen door het te vergelijken met de root van de min-heap. Als vervolgens na het inbrengen de grootte van de ene hoop verschilt van die van de andere hoop met meer dan 1, kunnen we de hopen opnieuw in evenwicht brengen, waardoor een verschil in grootte van maximaal 1 behouden blijft:

if size (minHeap)> size (maxHeap) + 1: verwijder root-element van minHeap, plaats in maxHeap if size (maxHeap)> size (minHeap) + 1: verwijder root-element van maxHeap, voeg in minHeap in

Met deze benadering kunnen we de mediaan berekenen als het gemiddelde van de wortelelementen van beide hopen, als de grootte van de twee hopen gelijk is. Anders de wortelelement van de hoop met meer elementen is de mediaan.

We gebruiken de Prioriteits-rij klasse om de hopen te vertegenwoordigen. De standaardheap-eigenschap van een Prioriteits-rij is min-heap. We kunnen een max-heap maken door een Comparator.reverserOrder die het omgekeerde van de natuurlijke volgorde gebruikt:

class MedianOfIntegerStream {private Queue minHeap, maxHeap; MedianOfIntegerStream () {minHeap = nieuwe PriorityQueue (); maxHeap = nieuwe 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 (); } anders {median = (minHeap.peek () + maxHeap.peek ()) / 2; } mediaan teruggeven; }}

Laten we, voordat we de looptijd van onze code analyseren, kijken naar de tijdcomplexiteit van de heap-bewerkingen die we hebben gebruikt:

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

Dus de getMedian operatie kan worden uitgevoerd in O (1) tijd omdat het de vind-min en vind-max functies alleen. De tijdcomplexiteit van de toevoegen operatie is O (logboek n) - drie invoegen/verwijderen roept elk nodig O (logboek n) tijd.

4.3. Hoopgrootte invariante oplossing

In onze vorige benadering hebben we elk nieuw element vergeleken met de wortelelementen van de hopen. Laten we een andere benadering verkennen met heap waarin we de eigenschap heap kunnen gebruiken om een ​​nieuw element in de juiste helft toe te voegen.

Zoals we hebben gedaan voor onze vorige oplossing, beginnen we met twee hopen: een min-heap en een max-heap. Laten we vervolgens een voorwaarde introduceren: de grootte van de max-heap moet zijn (n / 2) te allen tijde, terwijl de grootte van de min-heap beide kan zijn (n / 2) of (n / 2) + 1, afhankelijk van het totale aantal elementen in de twee hopen. Met andere woorden, we kunnen alleen de min-heap toestaan ​​om een ​​extra element te hebben, als het totale aantal elementen oneven is.

Met onze heapgrootte-invariant kunnen we de mediaan berekenen als het gemiddelde van de wortelelementen van beide hopen, als de grootte van beide hopen (n / 2). Anders de hoofdelement van de min-heap is de mediaan.

Als we een nieuw geheel getal toevoegen, hebben we twee scenario's:

1. Totaal aantal. van bestaande elementen is even groot (min-heap) == size (max-heap) == (n / 2) 2. Totaal aantal. van bestaande elementen heeft een oneven grootte (max-heap) == (n / 2) grootte (min-heap) == (n / 2) + 1 

We kunnen de invariant handhaven door het nieuwe element aan een van de hopen toe te voegen en elke keer opnieuw in evenwicht te brengen:

Het opnieuw in evenwicht brengen werkt door het grootste element van de max-heap naar de min-heap te verplaatsen, of door het kleinste element van de min-heap naar de max-heap te verplaatsen. Maar op deze manier we vergelijken het nieuwe gehele getal niet voordat we het aan een hoop hebben toegevoegd, het daaropvolgende opnieuw in evenwicht brengen zorgt ervoor dat we de onderliggende invariant van kleinere en grotere helften respecteren.

Laten we onze oplossing in Java implementeren met PriorityQueues:

class MedianOfIntegerStream {private Queue minHeap, maxHeap; MedianOfIntegerStream () {minHeap = nieuwe PriorityQueue (); maxHeap = nieuwe PriorityQueue (Comparator.reverseOrder ()); } void add (int num) {if (minHeap.size () == maxHeap.size ()) {maxHeap.offer (num); minHeap.offer (maxHeap.poll ()); } anders {minHeap.offer (num); maxHeap.offer (minHeap.poll ()); }} double getMedian () {int median; if (minHeap.size ()> maxHeap.size ()) {median = minHeap.peek (); } anders {median = (minHeap.peek () + maxHeap.peek ()) / 2; } terugkeer mediaan; }}

De tijdscomplexiteit van onze operaties blijft ongewijzigd: getMedian kosten O (1) tijd, terwijl toevoegen loopt op tijd O (logboek n) met exact hetzelfde aantal bewerkingen.

Beide heap-gebaseerde oplossingen bieden vergelijkbare complexiteit in ruimte en tijd. Hoewel de tweede oplossing slim is en een schonere implementatie heeft, is de aanpak niet intuïtief. Aan de andere kant volgt de eerste oplossing natuurlijk onze intuïtie, en het is gemakkelijker om over de juistheid ervan te redeneren toevoegen operatie.

5. Conclusie

In deze zelfstudie hebben we geleerd hoe we de mediaan van een stroom gehele getallen kunnen berekenen. We hebben een paar benaderingen geëvalueerd en een aantal verschillende oplossingen in Java geïmplementeerd met behulp van Prioriteits-rij.

Zoals gewoonlijk is de broncode voor alle voorbeelden beschikbaar op GitHub.