Free Software Stuff

BarCamp, XSS, random quote algorithm

Sutra je BarCamp Zagreb. Sva su mjesta popunjna, raspored je krcat zanimljivim predavanjima.

Moje će biti u 17.00 u bijeloj (manjoj) sobi, na temu među-domenskog JavaScripta (ili kako kreirati JS widgete koji pristupaju podacima na jednom serveru, a ugrađuju se u stranicama na drugim). Pomalo senzacionalistički, predavanje sam naslovio XSS, iako na njemu neće biti riječi o malicioznim exploitima (samo usputni spomen) nego o korisnim tehnikama primjene u svakodnevnim Web aplikacijama. Vidjet ćemo sutra koliko je ljudima to zanimljivo…

Registracija je zatvorena, ako ste se uspjeli registrirati, super, vidimo se, ako ne, nadajmo se da će biti još ovakvih događaja, a moguće je i da će snimke s događaja naći neko mjesto na webu pa će se naknadno moći vidjeti.

Potpuno nevezano s ovim, neki dan sam se prisjetio vrlo jednostavnog algoritma za izdvajanje random quotea iz nekog (velikog) niza stringova zapisanih u datoteci, koju je moguće čitati samo sekvencijalno. Naivni algoritam bi ili prvo sve učitao u memoriju, odredio random broj od 0 do N-1 te odabrao traženi string (što ima vremensku kompleksnost O(N) ali i memorijsko zauzeće O(N) pa je nepoželjan za vrlo velike nizove stringova), ili prvo prošao cijeli niz, odredio koliko je velik, odredio random broj od 0 do N-1, te u novom prolazu odabrao random. Ova varijanta ima vremensku kompleksnost O(2N) a memorijsku O(1), što znači da je duplo sporiji.

Nešto pametniji način je (pseudo):

    trenutni = učitaj_prvi_string()
    n = 1
    sve dok ima još stringova:
        n = n + 1
        novi = učitaj_slijedeći_string()
        # slučajno(X) -> broj iz [0 .. X-1]
        ako slučajno(n) == 0:
            trenutni = novi
    vrati trenutni

Stvar funkcionira tako da se u svakom koraku računa vjerojatnost da se za string odabere novi. U svakom koraku je ta vjerojatnost 1/N. To znači da je vjerojatnost da se zadrži stari string (koji je u prethodnom koraku izabran s vjerojatnošću 1/(N-1)) (N-1)/N, odnosno ukupna “nova” vjerojatnost starog stringa je (N-1) / N * 1 / (N-1) = 1 / N. Po indukciji, vidi se da će u svakom koraku vjerojatnost pojave svakog stringa biti 1/N, što znači da je vjerojatnost ravnomjerno raspoređena, i konačni rezultat stvarno je random string iz skupa stringova. Kompleksnost ovog algoritma je O(N), a memorijsko zauzeće O(2).

Eto, fora :-)