Algoritmin aikakompleksisuudesta

Kirjotiin blogiini artikkelin otsikolla "Googlen hakualgoritmi ja sen aikakompleksisuus", kun kerta käytin sunnuntai-iltani aika tehokkaasti tuon binääripuuhaun tutkimiseen. Kaiken lisäksi Google ei käy kaikkia 30 triljoonaa sivua läpi joka hakukerralla, ja näyttääkin vain 10 tulosta per sivu. Eli se voi hakea uusia sivuja omasta tietokannastaan ja omilla mentelmillään säikeistettynä samalla, kun asiakas lukee aiempia hakutulossivuja.

https://tietokoneblogi.wordpress.com/2017/08/27/googlen-hakualgoritmi-ja-sen-aikakompleksisuus/

Tein Twitter-kyselynkin aiheesta, käyttääkö lukijoideni mielestä modernit hakukoneet edes osaksi tietorakenne, tai hyödyntää jonain ilmentymänä binääristä puuhakua, kun tutustuin Ericin kaaviokuvaan.

Lyhytosoite kyselyyn olisi
https://goo.gl/tHMpHu

Aika suuria kyselet. Google ei ole tainnut julkistaa hakualgoritmeistansa juuri mitään yleiseen tietoon. Ilmeisesti käyttävät jonkinlaista koneoppimista.

En tiedä mitä tietorakenteita tai hakualgoritmeja hakukoneet käyttävät. Mutta tuskin mitää niin alkeellista kuin binääripuu. Veikkaisin jonkinllaista sumeaa hash-tekniikkaa ensimmäiseksi datan rajaukseksi sekä ehkä rinnakkaisprosessointia syvempään analyysiin. Hakutuloksilla on prioriteetit, ja 1. haku hakee ilmeisesti vain korkeimman prioroteetin tulokset.

No joo, mutta binäripuu, jos se on tasapainossa, suoritusaika kasvaa logaritmifunktion mukaan, eli todella nopeasti on käytävissä läpi. Sori, "tasapaino":isella tarkoitan kokonaista tai aitoa binääripuuta. Tuo luku 64 ja risat, jonka sain laskimestani blogiartikkelini taustatietoja kaivaessani viittaa varmaankin puun kokoon 30 triljoonan sivuolion hakutietokantaan, joka Googlella on, eli kyseessä olisi ainoastaan 64 solmuinen binääripuu?

Millähän perusteella meinasit lajitella kaikki internetsivut binääripuuhun? Internetin rakenne taitaa olla hieman monimutkaisempi graafi.

>log2(30 triljoonaa) laskimeni antaa tulokseksi 64.7015963 tarkalleen ottaen tasan, niin kertooko tuo luku tarvittavien hakujen määrän, jotta kaikki puun solmut tulevat käydyksi läpi, jos jokaisella isäsolmulla on kaksi lapsisolmua, eikä puu sisällä yhtään lehteä.

Ei. Tuo kertoo maksimivertailujen määrän jolla jokin solmu binääripuusta löytyy. Lehtiähän binääripuussa on väkisinkin mutta ilmeisesti tarkoitat sitä että puu on täydellisesti järjestetty eli toisinsanoen puun korkeus on niin matala kuin voi olla?

Suosittelisin myös käyttämään kotisivusi bannerissa png-tiedostotyyppiä jpg:n sijasta. Antaa aika amatöörimäisen ensivaikutelman noin huonolaatuinen kuva tietokoneaiheisella sivulla.

No joo, onhan konekuvani hieman retro niinkuin olen vähän itsekin kait.

No meinasin sitä, että kun N log(n) on nopein keino etsiä suuresta datajoukosta jotain tietoa, jos Googlen hakurobotit hyödyntää kyseistä tietorakennetta jollain tasolla?

Google perustettiin vuonna 1998, eli toisin sanoen hakubotit käynnistettiin joko silloin ja aikaisemmin, ja ajan mittaan tietomäärä tosiaan paisunut aika moiseksi ja koko ajan tulee lisää lajiteltavaa tietoa tietokantoihin.

Joo, niin kai antaa, muttet ottanut huomioon "tekoälyä", rutiineja, jotka pyyhkivät pölyt random kyselyistä