streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megtanuljuk, hogyan kell kiszámítani az egész számok áramának mediánját.

Folytatjuk a probléma példákkal való megfogalmazásával, majd elemezzük a problémát, végül megvalósítunk több megoldást a Java-ban.

2. Probléma-kimutatás

A medián a rendezett adatsor középső értéke. Egész számok esetén ugyanannyi elem van kevesebb, mint a medián, annál nagyobb.

Rendezett készletben:

• páratlan számú egész szám, a középső elem a medián - a rendezett halmazban { 5, 7, 10 }, a medián az 7
• páros egész szám, nincs középső elem; a medián a két középső elem átlagaként kerül kiszámításra - a rendezett halmazban {5, 7, 8, 10}, a medián az (7 + 8) / 2 = 7.5

Tegyük fel, hogy egy véges halmaz helyett egész számokat olvasunk le egy adatfolyamról. Meghatározhatjuk a az egész számok áramának mediánja az eddig leolvasott egészek halmazának mediánja.

Formalizáljuk a problémamegállapítást. Egy egész szám adatfolyamának bevitelével meg kell terveznünk egy osztályt, amely a következő két feladatot hajtja végre minden elolvasott egész szám esetében:

1. Adja hozzá az egész számot az egészek halmazához
2. Keresse meg az eddig elolvasott egész számok mediánját

Például:

add 5 // rendezett-halmaz = {5}, méret = 1 medián megszerzése -> 5 add 7 // rendezett-halmaz = {5, 7}, méret = 2 kap medián -> (5 + 7) / 2 = 6 add 10 // rendezett-halmaz = {5, 7, 10}, méret = 3 medián -> 7 add 8 // rendezett-halmaz = {5, 7, 8, 10}, méret = 4 kap medián -> ( 7 + 8) / 2 = 7,5 .. 

Bár az adatfolyam nem végleges, feltételezhetjük, hogy az adatfolyam összes elemét egyszerre tárolhatjuk a memóriában.

Feladatainkat a következő műveletekként jeleníthetjük meg kódban:

void add (int szám); kettős getMedian (); 

3. Naiv megközelítés

3.1. Rendezve Lista

Kezdjük egy egyszerű ötlettel - kiszámíthatjuk a rendezett mediánját lista egész számának elérésével a. középső eleméhez vagy két középső eleméhez lista, index szerint. Az idő összetettsége getMedian művelet az O (1).

Új egész szám hozzáadása közben meg kell határoznunk annak helyes pozícióját a lista olyan, hogy a lista rendezve marad. Ez a művelet a Tovább) idő, hol n mérete a lista. Tehát egy új elem hozzáadásának összköltsége a lista és az új medián kiszámítása az Tovább).

3.2. A naiv megközelítés fejlesztése

A hozzá a művelet lineáris időben fut, ami nem optimális. Próbáljuk meg foglalkozni ezzel a szakaszsal.

Fel tudjuk osztani a lista ketté rendezve listák – az egész számok kisebbik fele csökkenő sorrendben, az egész számok nagyobbik fele pedig növekvő sorrendben rendeződik. Hozzáadhatunk egy új egész számot a megfelelő feléhez úgy, hogy a méret listák legfeljebb 1-vel tér el:

ha az elem kisebb mint min. nagyobb fele eleme: helyezze be a kisebb fele a megfelelo indexbe, ha a kisebb fele sokkal nagyobb, mint a nagyobb fele: távolítsa el max. a kisebbik fele elemét, és a nagyobbik fele elején helyezze be (újrabalancolja), másképp helyezze a nagyobbik fele megfelelő index szerint: ha a nagyobbik fele sokkal nagyobb, mint a kisebb fele: távolítsa el min. a nagyobbik fele eleme, és helyezze be a kisebbik fele elejére (egyensúly) 

Most kiszámíthatjuk a mediánt:

ha a listák azonos számú elemet tartalmaznak: medián = (max. kisebb fele eleme + min. nagyobb fele eleme) / 2 más, ha a kisebb fele több elemet tartalmaz: medián = max. a kisebbik fele más része, ha a nagyobbik fele több elemet tartalmaz: medián = min. nagyobb fele eleme

Bár csak javítottuk a hozzá valamilyen állandó tényezővel működve, előrelépést tettünk.

Elemezzük azokat az elemeket, amelyekhez hozzáférünk a kettőben listák. Minden elemhez hozzáférhetünk, amikor a (rendezett) hozzá művelet. Ennél is fontosabb, hogy elérjük a nagyobb és a kisebb felek minimumát és maximumát (extrémjeit) a hozzá a kiegyensúlyozás és a getMedian művelet.

Ezt láthatjuk a szélsőségesek a megfelelő listáik első elemei. Szóval, mi optimalizálnia kell az elem elérését az indexben 0 minden felére a teljes futási idő javítása hozzá művelet.

4. Halomalapú megközelítés

Tisztítsuk meg a probléma megértését azáltal, hogy alkalmazzuk a naiv megközelítésből tanultakat:

1. Be kell szereznünk egy adatkészlet minimális / maximális elemét O (1) idő
2. Az elemeket nem kell rendezett sorrendben tartani mindaddig, amíg hatékonyan megszerezhetjük a minimum / maximum elemet
3. Meg kell találnunk egy megközelítést, amellyel olyan elemet lehet hozzáadni az adatkészletünkhöz, amely kevesebb, mint Tovább) idő

Ezután megvizsgáljuk a Halom adatszerkezetet, amely segít a céljaink hatékony megvalósításában.

4.1. Halom adatstruktúra

Halom egy adatstruktúra, amelyet általában tömbökkel valósítanak meg, de bináris fának tekinthető.

A halmokat a halom tulajdonság korlátozza:

4.1.1. Max–kupac Tulajdon

Egy (gyermek) csomópont értéke nem lehet nagyobb, mint a szülője. Ezért a max-kupac, mindig a gyökércsomópontnak van a legnagyobb értéke.

4.1.2. Min–kupac Tulajdon

Egy (szülő) csomópont értéke nem lehet nagyobb, mint a gyermekeié. Így a min-halom, a gyökércsomópontnak mindig a legkisebb az értéke.

Java-ban az PriorityQueue osztály egy kupacot jelent. Haladjunk előre az első megoldásunkra halmokkal.

4.2. Első megoldás

Cseréljük le a listákat naiv megközelítésünkben két kupacra:

• Min-halom, amely az elemek nagyobbik felét tartalmazza, a gyökérnél a minimális elem
• Egy max-kupac, amely az elemek kisebbik felét tartalmazza, a gyökérnél a maximális elem

Most hozzáadhatjuk a bejövő egész számot a megfelelő feléhez, összehasonlítva azt a min-halom gyökerével. Ezután, ha behelyezés után az egyik kupac mérete 1-nél nagyobb mértékben különbözik a másik kupac méretétől, akkor újra egyensúlyba hozhatjuk a kupacokat, így legfeljebb 1-es méretkülönbség maradhat fenn:

if size (minHeap)> size (maxHeap) + 1: távolítsa el a minHeap gyökérelemét, helyezze be a maxHeap-be, ha size (maxHeap)> méret (minHeap) + 1: távolítsa el a maxHeap gyökérelemét, helyezze be a minHeap-be

Ezzel a megközelítéssel kiszámíthatjuk a mediánt mindkét kupac gyökérelemének átlagaként, ha a két kupac mérete egyenlő. Egyébként a a halom gyökéreleme több elemmel a medián.

Használjuk a PriorityQueue osztály képviseli a halmokat. A. Alapértelmezett kupac tulajdonsága PriorityQueue min-halom. Max. Kupacot hozhatunk létre az a használatával Comparator.reverserOrder amely a természetes sorrend fordítottját használja:

osztály MedianOfIntegerStream {privát várólista minHeap, maxHeap; MedianOfIntegerStream () {minHeap = new PriorityQueue (); maxHeap = new PriorityQueue (Összehasonlító.reverseOrder ()); } void add (int num) {if (! minHeap.isEmpty () && num minHeap.size () + 1) {minHeap.offer (maxHeap.poll ()); }} else {minHeap.offer (szám); if (minHeap.size ()> maxHeap.size () + 1) {maxHeap.offer (minHeap.poll ()); }}} kettős getMedian () {int medián; if (minHeap.size () maxHeap.size ()) {medián = minHeap.peek (); } else {medián = (minHeap.peek () + maxHeap.peek ()) / 2; } visszatérési medián; }}

Mielőtt elemeznénk kódunk futási idejét, nézzük meg a felhalmozott műveletek időbeli összetettségét:

find-min / find-max O (1) törlés-min / törlés-max O (log n) beillesztés O (log n) 

Így a getMedian művelet elvégezhető O (1) idő, mivel megköveteli a megtalálás-min és megtalálni-max csak funkciók. Az idő összetettsége hozzá művelet az O (log n) - három betét/töröl hívja mindegyik igénylőt O (log n) idő.

4.3. Halom méretű változatlan megoldás

Korábbi megközelítésünkben minden egyes új elemet összehasonlítottunk a halmok gyökérelemeivel. Fedezzünk fel egy másik megközelítést a kupac segítségével, amelyben a kupac tulajdonságot felhasználva új elemet adhatunk a megfelelő feléhez.

Ahogy az előző megoldásunknál tettük, két halommal kezdjük - egy min-kupac és egy max-kupac. Ezután mutassunk be egy feltételt: a max-kupac méretének meg kell lennie (n / 2) mindenkor, miközben a min-kupac mérete bármelyik lehet (n / 2) vagy (n / 2) + 1, a két kupacban lévő elemek összes számától függően. Más szavakkal, csak a min-halomban engedélyezhetünk extra elemet, ha az elemek teljes száma páratlan.

A halomméret-invariánsunkkal kiszámíthatjuk a mediánt mindkét kupac gyökérelemének átlagaként, ha mindkét kupac mérete (n / 2). Egyébként a a min-halom gyökéreleme a medián.

Új egész szám hozzáadásakor két forgatókönyvünk van:

1. Összesen a meglévő elemek egyenletes mérete (min-kupac) == méret (max-kupac) == (n / 2) 2. Összesen sz. a meglévő elemek páratlan mérete (max-kupac) == (n / 2) méret (min-kupac) == (n / 2) + 1 

Fenntarthatjuk az invariánst azáltal, hogy hozzáadjuk az új elemet az egyik kupachoz, és minden alkalommal egyensúlyba hozzuk:

A kiegyensúlyozás úgy működik, hogy a legnagyobb elemet mozgatja a max-halomból a min-kupacba, vagy a legkisebb elemet mozgatja a min-kupacból a max-kupacba. Így is nem hasonlítjuk össze az új egész számot, mielőtt hozzáadnánk egy halomhoz, az ezt követő újbóli kiegyensúlyozás biztosítja, hogy tiszteletben tartsuk a kisebb és nagyobb felek mögöttes invariánsát.

Vezessük végre megoldásunkat a Java használatával PriorityQueues:

osztály MedianOfIntegerStream {privát várólista minHeap, maxHeap; MedianOfIntegerStream () {minHeap = new PriorityQueue (); maxHeap = new PriorityQueue (Összehasonlító.reverseOrder ()); } void add (int szám) {if (minHeap.size () == maxHeap.size ()) {maxHeap.offer (szám); minHeap.offer (maxHeap.poll ()); } else {minHeap.offer (szám); maxHeap.offer (minHeap.poll ()); }} kettős getMedian () {int medián; if (minHeap.size ()> maxHeap.size ()) {medián = minHeap.peek (); } else {medián = (minHeap.peek () + maxHeap.peek ()) / 2; } visszatérési medián; }}

Műveleteink időbeli összetettsége változatlan marad: getMedian költségek O (1) idő, míg hozzá fut az időben O (log n) pontosan ugyanannyi művelettel.

Mind a kupac alapú megoldások hasonló térbeli és időbeli összetettséget kínálnak. Míg a második megoldás okos és tisztább megvalósítású, a megközelítés nem intuitív. Másrészt az első megoldás természetesen követi az intuíciónkat, és könnyebb okot adni annak helyességére hozzá művelet.

5. Következtetés

Ebben az oktatóanyagban megtanultuk, hogyan kell kiszámítani az egész számokfolyam mediánját. Kiértékeltünk néhány megközelítést, és néhány különböző megoldást implementáltunk a Java-ban PriorityQueue.

Szokás szerint az összes példa forráskódja elérhető a GitHubon.