tag:blogger.com,1999:blog-2467724970188645480.post4963193186394875739..comments2023-11-15T11:12:15.983+02:00Comments on T13-d3-m135: Suodatus...Tiedemieshttp://www.blogger.com/profile/08307419899926184187noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-2467724970188645480.post-41853694058726861112008-11-21T19:33:00.000+02:002008-11-21T19:33:00.000+02:00Ei, tämä perustui kahdentasoiseen ikkunointiin. Pe...Ei, tämä perustui kahdentasoiseen ikkunointiin. <BR/><BR/>Perusikkuna on se n:än mittainen. Se perusikkuna voi olla vaikka rengaspuskurissa. Kun yksi ikkunallinen dataa on sisällä, tehdään alustus.<BR/><BR/>Tehdään sqrt(n):n kokoinen "pikkuikkuna", jossa on sqrt(n) keskimmäistä alkiota suuruusjärjestyksessä, mediaani keskellä. Tämä voi olla vaikka lista. <BR/>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. <BR/><BR/>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.<BR/>Vanhan poistaminen on aina vakioaikaista. Sama juttu toisin päin.<BR/><BR/>Jos uusi alkio ja lähtevä alkio ovat mediaanin samalla puolella, mitään ongelmaa ei ole; vanha mediaani on edelleen mediaani. <BR/><BR/>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.Tiedemieshttps://www.blogger.com/profile/08307419899926184187noreply@blogger.comtag:blogger.com,1999:blog-2467724970188645480.post-32609074100592243062008-11-21T17:48:00.000+02:002008-11-21T17:48:00.000+02:00Nuo O(1) mediaanifiltterit perustuvat histogrammin...Nuo O(1) mediaanifiltterit perustuvat histogrammin laatimiseen, histogrammin tekemiseksi tarvitaan ainakin ceil log2 N bittiä per jokainen mahdollinen sämppelin arvo.<BR/><BR/>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.Kuntsahttps://www.blogger.com/profile/03077142827171300503noreply@blogger.com