Kävin eilen mielenkiintoisen keskustelun mediaanisuodatuksesta. Ongelma redusoituu laskennallisesti n-kokoisen ikkunan ns. liukuvan mediaanin löytämiseen.
Olen pitänyt tätä ongelmaa logaritmisena - siis kun ikkunaan tulee uusi alkio ja vanhin lähtee pois, niin uuden mediaanin laskeminen on logaritmista. Pahimmassa tapauksessa tämä pätee edelleen, koska liukuvaa ikuunaa voidaan käyttää aineiston järjestämiseen ja tämä on, vertailuun perustuvalla algoritmilla, aina &Omega (n log n).
Eilen tulin kuitenkin taivutelluksi uskomaan, että tämä voi onnistua satunnaisella aineistolla keskimäärin vakioajassa, siis riippumatta ikkunan koosta! Tällainen tulos on erittäin mielenkiintoinen ja tärkeä. Tietystikin ikkunan koon täytyy olla pieni koko aineiston kokoon verrattuna, mutta niin useimmissa käyttökohteissa onkin.
2 kommenttia:
Nuo O(1) mediaanifiltterit perustuvat histogrammin laatimiseen, histogrammin tekemiseksi tarvitaan ainakin ceil log2 N bittiä per jokainen mahdollinen sämppelin arvo.
Jos ikkunan koko on max 256 sämppeliä (eli per sämppelin arvo tarvitaan 8 bittiä), niin 8-bittisillä sämppeleillä menee 256 tavua, 24-bittisillä sämppeleillä menee 16 megaa ja 32-bittisillä 4 gigaa. Lisäksi tietty algoritmin vaatima tila.
Ei, tämä perustui kahdentasoiseen ikkunointiin.
Perusikkuna on se n:än mittainen. Se perusikkuna voi olla vaikka rengaspuskurissa. Kun yksi ikkunallinen dataa on sisällä, tehdään alustus.
Tehdään sqrt(n):n kokoinen "pikkuikkuna", jossa on sqrt(n) keskimmäistä alkiota suuruusjärjestyksessä, mediaani keskellä. Tämä voi olla vaikka lista.
Sen tekeminen on O(n), koska listan järjestäminen on neliöjuuri n * logaritmi, ja listan ensimmäinen ja viimeinen löytyvät lineaarisessa ajassa.
Kun ikkunaan tulee uusi, niin jos se on vanhaa mediaania suurempi ja poistuva alkio on sitä pienempi, uusi mediaani on nyt vanhan oikealla puolella. Jos uusi alkio ei kuulu "pikkuikkunaan", business as usual. Jos se kuuluu pikkuikkunaan - tämän todennäköisyys on karkeasti 1/sqrt(n) - lisätään se pikkuikkunaan vaikka selaamalla. Tämä on sqrt(n) (pikkuikkunan koko), mutta tapahtuu niin harvoin, että keskimäärin vakioaikaista.
Vanhan poistaminen on aina vakioaikaista. Sama juttu toisin päin.
Jos uusi alkio ja lähtevä alkio ovat mediaanin samalla puolella, mitään ongelmaa ei ole; vanha mediaani on edelleen mediaani.
Jos data on satunnaista, pikkuikkunasta poistuu alkioita yhtä usein kuin sinne tulee ja se pysyy keskimäärin sqrt(n):n kokoisena. Jos se kasvaa "liian suureksi", tai "liian pieneksi" se rakennetaan uudestaan. Tämä on O(n), mutta jos kyseessä on random walk, niin tämän todennäköisyys on 1/(pikkuikkunan neliö), mikä on 1/n, ja olemme jälleen keskimäärin vakioajassa.
Lähetä kommentti