Jos hakukone käyttää binääristä hakupuuta tulosten seulonnassa yhtenä ratkaisunaan tietorakenteista, niin aikakompleksisuus
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ä.
Algoritmin aikakompleksisuudesta
10
381
Vastaukset
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- engooglellatöissä
Aika suuria kyselet. Google ei ole tainnut julkistaa hakualgoritmeistansa juuri mitään yleiseen tietoon. Ilmeisesti käyttävät jonkinlaista koneoppimista.
- engooglellatöissä
Taisinpa puhua puuta heinää. Koneoppiminen ei taida liittyä itse hakemiseen vaikkakin sitä kai käytetään mm. kuvahaussa tunnistamaan mitä kuvissa esiintyy.
https://en.wikipedia.org/wiki/PageRank
Sen siitä saa kun kirjoittaa ennenkun ajattelee.
- arvelee
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?
- ihmettely
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? - pikkuvinkki
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ä
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
"Miko Bergbom, miksi euron bensa maksaa kaksi euroa?"
Valtakunnan suurin kaupallinen porvarimediakin kyselee nyt miksi perussuomalaisset ovat rikkoneet tärkeimmän vaalilupauk525406Maahanmuuttajien vaikutus Suomen valtiontalouteen positiivinen
Maahanmuuttajat maksavat enemmän tuloveroja kuin saavat tulonsiirtoja. Eroavat persuista tässä suhteessa. Persuista o4175069Olen Päivi Räsäsen puolella
En oe uskovainen enkä kristillisdemograattikaan mutta onhan tuo naurettavaa laittaa Päivi syylliseksi omasta mielipit5733433SDP: "On hyvä että bensiinin hinta nousee"
Suurin oppositiopuolue SDP on mielissään siitä, että bensan hinta nousee suomalaisille. https://www.iltalehti.fi/polit832906Ukrainan tiedustelun huippupotti - Iski ensin yhteen satamaan, sitten toiseen
Ukrainan tiedustelupalvelu SBU kertoo johtaneensa operaatiota, jossa on isketty drooneilla Venäjän tärkeimpiin satamiin1322730Nuhteettomia edustajia
Korkein oikeus tuomitsi Päivi Räsäsen kiihottamisesta kansanryhmää vastaan Kansanedustaja Päivi Räsästä (kd.) vastaan no2622694Ulkomaalaistaustaiset tulevat kalliiksi yhteiskunnalle.
Selvitys: Ulkomaalaistaustaiset saivat selvästi enemmän työttömyysetuuksia ja toimeentulotukea kuin suomalaistaustaiset.2012656"Mieheksi ja naiseksi hän heidät loi."
Räsäsen tuomio on iso harppaus woke-valtioksi. – Tässä maassa on nyt selvästi kiellettyjä sanoja ja ajatusrikoksia. –931794Päivi Räsänen tuomittiin rikoksesta...
...kiihottamisesta kansanryhmää vastaan. Tuskin tajuaa silti vieläkään, että raamattu ei ole lakikirja. https://yle.fi/a6561724Huumeliika mellastaa Suomussalmella
Varastanut S-marketissa, jopa kolme kertaa päivässä. Päätekijä pitänyt kuumeorjanaan naistaan useita vuosia. Mies potki181610