Hei! Olen vihdoin palannut yli 2 kuukauden jälkeen, kun en ole kirjoittanut/koskettanut koodia. Jäin kiinni kaikkien häävalmistelujen ja -suunnittelun kanssa. On vaikea vetää ulkomaisia häitä ilman hääsuunnittelijaa. Mutta se oli kaiken sen arvoista, sillä häämme olivat kirjoihin kirjattavat! Hääkuume on ohi, ja nyt on aika kerätä ajatukseni ja palata koodaamaan (edelleen Swiftillä).
Oli vaikea päättää, mitä tarkistaa ensin ennen kuin aloitan työnhaun. Ajattelin aloittaa klassikoista – algoritmeista ja tietorakenteista, ohjelmoinnin ytimestä. Missä tahansa järjestelmässä datan kasvaessa suorituskyvyn ei pitäisi olla ongelma, jos on käytetty oikeaa algoritmia.
Tänään kirjoitan nopean blogin kahdesta erityyppisestä Big O -merkinnästä, lineaarisista ja logaritmisista algoritmeista.
Hieman taustaa Big O -merkinnöistä ensin.
Asymptoottinen analyysi
Asymptoottinen analyysi perustuu matemaattisiin laskutoimituksiin, jotka periaatteessa mittaavat algoritmin tehokkuutta syötetiedoston kasvaessa (kiitos Wikipedia!). On olemassa muitakin asymptoottisen analyysin muotoja riippuen siitä, missä sitä sovelletaan, mutta tietojenkäsittelytieteessä se on yleisesti muotoiltu Big O Notationa.
Lineaarinen vs. logaritminen
Voidaksemme helposti ymmärtää Big O Notationin, vertaamme näitä kahta algoritmia: Lineaarinen – O(n) ja Logaritminen – O(log n).
Esimerkiksi yritämme etsiä numeroa lajitellusta joukosta.
let numberList =
Lineaarinen O(n) – suorituskyky heikkenee datan kasvaessa.
Lineaarisessa eli ”raa’an voiman” tekniikassa suorituskyky riippuu syötteen koosta. Esimerkkimme tapauksessa luemme läpi jokaisen joukon kohteen ja etsimme tarvitsemamme numeron. Helppo homma!
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
Tämä tietysti toimii pienelle tietokokonaisuudellemme, mutta se ei ole kovin tehokasta, kun tietoja on tuhansia, jopa miljoonia.
Logaritminen O(log N) – kaventaa hakua puolittamalla toistuvasti datajoukon, kunnes kohdearvo löytyy.
Käyttämällä binäärihakua – joka on eräänlainen logaritminen algoritmi, löytää mediaanin joukosta ja vertaa sitä tavoitearvoon. Algoritmi kulkee joko ylös- tai alaspäin riippuen siitä, onko tavoitearvo suurempi, pienempi vai yhtä suuri kuin mediaani.
func binarySearch(key: Int, iminIndex: Int, imaxIndex: Int) {let midIndex = round(Double(iminIndex + imaxIndex)/2)
let midNumber = numberList
var result = ""//using recursion, we can go up or down the array and reduce the range
if midNumber > key { //target is less than the median so traverse downwards binarySearch(key: key, iminIndex: iminIndex, imaxIndex: Int(midIndex) - 1) } else if midNumber < key { //target is greater than the median so traverse upwards binarySearch(key: key, iminIndex: Int(midIndex) + 1, imaxIndex: imaxIndex) } else if midNumber == key { //Found it!
print("Found it at index \(midIndex)")} else {
print("Value \(key) not found")
}
}
Tämän algoritmin pääosa on alussa, mutta se tasaantuu hitaasti, kun hylkäämme epäolennaisen alueen joukosta ja jatkamme puolitusta, kunnes löydämme tavoitearvon.
Oheisen kuvaajan avulla voimme helposti verrata, kuinka useimpien algoritmien suorituskyky on samanlainen pienemmillä datajoukoilla, mutta eroaa jatkuvasti datan kasvaessa.
Kuten huomaatte, on olemassa muitakin Big O -merkintätapoja, joita käsittelen seuraavina päivinä. Ciao toistaiseksi!