3. Tehokkaat algoritmit

Tässä ja kahdessa seuraavassa luvussa tutustumme tehokkaiden algoritmien suunnitteluun. Tavoitteemme on saada aikaan algoritmeja, jotka toimivat tehokkaasti myös silloin, kun syötteen koko \(n\) on suuri.

Tavallinen tilanne algoritmien suunnittelussa on, että on helppoa laatia suoraviivainen algoritmi, joka ratkaisee tehtävän kahdella silmukalla ajassa \(O(n^2)\). Tällaista algoritmia voidaan kutsua raa’an voiman (brute force) algoritmiksi. Tämä ei kuitenkaan riitä \(n\):n ollessa suuri, vaan tarvitaan tehokkaampi algoritmi.

Käytännössä tehokkaan algoritmin aikavaativuus on usein \(O(n)\) tai \(O(n \log n)\). Tutustumme ensin \(O(n)\)-algoritmeihin, jotka käyvät syötteen läpi yhdellä silmukalla ja pitävät muistissa sopivalla tavalla valittua tietoa. Aikavaativuus \(O(n \log n)\) liittyy usein järjestämiseen, jota käsittelemme luvussa 5.

Tehokkaan algoritmin runko

Tyypillinen tehokkaan algoritmin runko on seuraava:

# muuttujien määrittely
for ...
    # tehokas koodi
# vastauksen palautus

Tällaisessa algoritmissa on yksi for-silmukka, joka käy läpi algoritmille annetun syötteen vasemmalta oikealle. Silmukan sisällä tulee olla tehokasta koodia niin, että silmukan jokainen kierros vie aikaa \(O(1)\). Tällöin koko algoritmin aikavaativuus on \(O(n)\).

Tehokkaan algoritmin silmukan sisällä saa olla seuraavia:

• muuttujan arvon päivitys muiden muuttujien tai yksittäisten syötteen alkioiden perusteella
• laskutoimitus, joka liittyy muuttujan arvon päivittämiseen
• if-komento, joka vaikuttaa sihen, miten muuttujia päivitetään

Sen sijaan silmukan sisällä ei saa olla seuraavia:

• toinen silmukka, joka käy läpi syötteen alkioita
• hidas syötettä käsittelevä operaatio (esim. metodi count tai slice-operaatio [:])
• hidas funktiokutsu (esim. sum, min tai max koko syötteelle)

Monen algoritmin suunnittelussa keskeinen haaste on keksiä, miten algoritmin saa toteutettua niin, että silmukan sisällä on vain tehokasta koodia. Näemme seuraavaksi esimerkkejä siitä, miten silmukan sisällä oleva tehokas koodi voidaan toteuttaa.

Esimerkki: Osakekauppa

Tehtävä

Suoraviivainen algoritmi tehtävän ratkaisemiseen on käydä läpi kaikki vaihtoehdot osakkeen ostopäivän ja myyntipäivän valintaan kahdella silmukalla. Seuraava funktio best_profit toteuttaa algoritmin:

def best_profit(prices):
    n = len(prices)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, prices[j] - prices[i])
    return best

Ideana on, että muuttuja i valitsee ostopäivän ja muuttuja j valitsee myyntipäivän. Jokaiselle valinnalle lasketaan näin saatava tuotto osakekaupasta, ja muuttuja best pitää muistissa parasta tuottoa. Tämä on toimiva algoritmi, mutta ongelmana on, että algoritmin aikavaativuus on \(O(n^2)\) eli se on hidas, kun \(n\) on suuri. Algoritmia tulisi tehostaa niin, että siinä ei ole kahta silmukkaa vaan vain yksi silmukka.

Mietitään nyt, millainen algoritmin tulisi olla, jotta siinä olisi vain yksi silmukka. Kun olemme tietyn päivän kohdalla, miten suuri voitto on mahdollinen, jos myymme osakkeen kyseisenä päivänä? Voitto on suurin silloin, kun olemme ostaneet osakkeen aiemmin mahdollisimman halvalla. Niinpä meidän kannattaa valita ostohinnaksi osakkeen halvin hinta kyseiseen päivään mennessä.

Voimme toteuttaa tällaisen algoritmin seuraavasti:

def best_profit(prices):
    n = len(prices)
    best = 0
    for i in range(n):
        min_price = min(prices[0:i+1])
        best = max(best, prices[i] - min_price)
    return best

Ideana on laskea silmukassa muuttujaan min_price osakkeen halvin hinta päivään i mennessä. Tämä on toteutettu hakemalla pienin alkio min-funktiolla listan alkuosassa prices[0:i+1]. Tämän jälkeen saamme laskettua kaavalla prices[i] - min_price voiton, kun myymme osakkeen päivänä i.

Tämä on toimiva algoritmi ja siinä on vain yksi silmukka, mutta algoritmi ei ole vielä tehokas. Ongelmana on, että muuttujan min_price laskeminen on hidasta silmukassa, koska min-funktio käy läpi listan prices alkuosan. Tämä vie aikaa \(O(n)\), minkä vuoksi algoritmin aikavaativuus on edelleen \(O(n^2)\).

Voimme kuitenkin korjata ongelman seuraavasti:

def best_profit(prices):
    n = len(prices)
    best = 0
    min_price = prices[0]
    for i in range(n):
        min_price = min(min_price, prices[i])
        best = max(best, prices[i] - min_price)
    return best

Nyt muuttujaa min_price ei lasketa tyhjästä silmukan joka kierroksella, vaan uusi arvo lasketaan tehokkaasti edellisen arvon perusteella. Tämän muutoksen ansiosta silmukan jokainen kierros vie aikaa \(O(1)\), jolloin algoritmin aikavaativuus on \(O(n)\) ja algoritmi toimii tehokkaasti.

Huomaa, että funktion min käyttäminen voi olla sekä hidasta että tehokasta. Jos funktiolla haetaan listan pienin alkio, tämä on hidasta. Jos kuitenkin funktiolla valitaan pienempi kahdesta arvosta, tämä on tehokasta.

Toimiiko algoritmi?

Tehokkaan algoritmin toimintalogiikka on yleensä monimutkaisempi kuin suoraviivaisessa raa’an voiman algoritmissa. Tämän vuoksi voi olla vaikea tietää, onko toteutettu algoritmi varmasti toimiva.

Kätevä tapa saada tietoa tehokkaan algoritmin toimivuudesta on verrata sen toimintaa suoraviivaiseen algoritmiin. Tämä voidaan automatisoida niin, että algoritmeja testataan suurella määrällä satunnaisia syötteitä. Esimerkiksi voimme testata äskeisen tehtävän algoritmeja seuraavaan tapaan:

import random

def best_profit_brute(prices):
    ...

def best_profit_fast(prices):
    ...

while True:
    n = random.randint(1, 20)
    prices = [random.randint(1, 10) for _ in range(n)]

    result_brute = best_profit_brute(prices)
    result_fast = best_profit_fast(prices)

    print(prices, result_brute, result_fast)

    if result_brute != result_fast:
        print("ERROR")
        break

Tässä funktio best_profit_brute toteuttaa raa’an voiman algoritmin ja funktio best_profit_fast toteuttaa tehokkaan algoritmin. Pääohjelma testaa algoritmeja luomalla satunnaisia listoja, joissa \(n\) on välillä \(1 \dots 20\) ja hinnat ovat välillä \(1 \dots 10\). Jokaisen testin jälkeen ohjelma tulostaa listan sisällön sekä funktioiden palauttamat arvot. Ohjelman tulostus voisi alkaa seuraavasti:

[2, 4, 5, 4, 2, 4, 8, 7, 5] 6 6
[8, 8, 8, 3, 6, 4, 9, 3, 2, 5, 4, 5, 2] 6 6
[9, 3, 1, 5, 8, 9, 3] 8 8
[3, 6, 7] 4 4
[6, 8, 7, 10, 8, 6, 1, 1, 2, 2, 8, 9, 10] 9 9
[4, 5, 3, 4, 5] 2 2
[3, 6, 2] 3 3
[4, 3, 8, 10, 7, 3, 4, 7, 5, 1, 7, 8, 7] 7 7
...

Tällaisen testauksen avulla saa hyvää varmuutta siitä, että tehokas algoritmi on toimiva. Jos löytyy syöte, jossa algoritmi antaa väärän tuloksen, ohjelma ilmoittaa tästä ja testaus päättyy. Tämän jälkeen ohjelman antaman syötteen avulla voi koettaa tutkia, miksi algoritmi ei toimi oikein.

Esimerkki: Bittijono

Tehtävä

Suoraviivainen tapa ratkaista tehtävä on käydä läpi kaikki tavat valita vasen ja oikea kohta ja laskea, monessako kohdassa vasen bitti on 0 ja oikea bitti on 1:

def count_ways(bits):
    n = len(bits)
    result = 0
    for i in range(n):
        for j in range(i + 1, n):
            if bits[i] == '0' and bits[j] == '1':
                result += 1
    return result

Tässä ongelmana on jälleen, että aikavaativuus on \(O(n^2)\) eli algoritmi on liian hidas.

Mietitään, miten selviäisimme yhdellä silmukalla. Kuten osakkeen hinnan laskemisessa, tässäkin tehtävässä hyvä lähestymistapa on käsitellä jokaisessa kohdassa kyseiseen kohtaan päättyvät ratkaisut. Tarkemmin voimme koettaa laskea kussakin bittijonon kohdassa i tehokkaasti tavat, joissa oikea bitti 1 on kohdassa i ja vasen bitti 0 on ennen kohtaa i.

Jos kohdassa i on bitti 1, tässä kohdassa voi olla oikea kohta. Tässä tapauksessa vasen kohta voi olla mikä tahansa kohta ennen kohtaa i, jossa on bitti 0. Niinpä saamme aikaan tehokkaan algoritmin, kun pidämme muistissa, montako bittiä 0 on tullut vastaan silmukan aikana. Voimme toteuttaa algoritmin näin:

def count_ways(bits):
    n = len(bits)
    result = 0
    zeros = 0
    for i in range(len(bits)):
        if bits[i] == '0':
            zeros += 1
        if bits[i] == '1':
            result += zeros
    return result

Silmukan sisällä suoritettava koodi riippuu siitä, onko bitti 0 vai 1. Jos bitti on 0, kasvatetaan muuttujan zeros arvoa. Tämän avulla joka kohdassa tiedetään, montako bittiä 0 on tullut vastaan tähän mennessä. Jos taas bitti on 1, lisätään muuttujaan result muuttujan zeros arvo. Tämä laskee tehokkaasti mukaan tulokseen kaikki tavat, joissa oikea bitti on kohdassa i.

Algoritmissa on yksi silmukka, joka käy syötteen läpi, ja silmukan sisällä olevan koodin aikavaativuus on \(O(1)\). Tämän ansiosta algoritmin aikavaativuus on \(O(n)\) ja se toimii tehokkaasti.

Esimerkki: Listan halkaisu

Tehtävä

Suoraviivainen algoritmi tehtävään on seuraava:

def count_splits(numbers):
    n = len(numbers)
    result = 0
    for i in range(n - 1):
        left_sum = sum(numbers[0:i+1])
        right_sum = sum(numbers[i+1:])
        if left_sum == right_sum:
            result += 1
    return result

Algoritmi käy läpi kaikki tavat halkaista lista ja laskee muuttujiin left_sum ja right_sum listan vasemman ja oikean osan summan halkaisun jälkeen. Jos summat ovat samat, muuttujan result arvo kasvaa yhdellä. Algoritmin aikavaativuus on \(O(n^2)\), koska muuttujien left_sum ja right_sum laskeminen vie aikaa \(O(n)\).

Koska silmukka käy listan läpi vasemmalta oikealle, voimme tehostaa algoritmia laskemalla summaa left_sum samaa tahtia silmukan kanssa:

def count_splits(numbers):
    n = len(numbers)
    result = 0
    left_sum = 0
    for i in range(n - 1):
        left_sum += numbers[i]
        right_sum = sum(numbers[i+1:])
        if left_sum == right_sum:
            result += 1
    return result

Tämä ei ole kuitenkaan riittävä tehostus, koska muuttujan right_sum laskeminen on edelleen hidasta eikä siihen voi tehdä vastaavaa muutosta, koska listaa käydään läpi vasemmalta oikealle. Vaikka muuttuja left_sum lasketaan tehokkaasti, algoritmi vie edelleen aikaa \(O(n^2)\).

Voimme kuitenkin tehostaa algoritmia lisää hyödyllisen havainnon avulla: jos tiedämme vasemman osan summan lisäksi koko listan summan, voimme laskea näiden tietojen avulla tehokkaasti oikean osan summan.

def count_splits(numbers):
    n = len(numbers)
    result = 0
    left_sum = 0
    total_sum = sum(numbers)
    for i in range(n - 1):
        left_sum += numbers[i]
        right_sum = total_sum - left_sum
        if left_sum == right_sum:
            result += 1
    return result

Koska koko listan summa ei muutu silmukan aikana, voimme laskea sen ennen silmukkaa muuttujaan total_sum. Tämä vie aikaa \(O(n)\) mutta se tehdään vain kerran ennen silmukkaa. Tämän jälkeen silmukassa right_sum saadaan laskettua tehokkaasti kaavalla total_sum - left_sum. Tuloksena on algoritmi, jonka aikavaativuus on \(O(n)\).

Esimerkki: Osalistat

Tehtävä

Tämä tehtävä on selvästi vaikeampi kuin aiemmat käsitellyt tehtävät, mutta tässäkin toimii aiemmin hyväksi havaittu tekniikka: käydään läpi lista ja lasketaan jokaisessa kohdassa, montako ratkaisua päättyy kyseiseen kohtaan.

Esimerkkitapauksessa tulisi saada laskettua seuraavat tulokset:

Esimerkiksi kohdassa 5 haluttu tulos on 3, koska kohtaan 5 päättyvät osalistat ovat \([2,3,3,2,2]\), \([3,3,2,2]\) ja \([3,2,2]\).

Voimme laskea kohtaan i päättyvien osalistojen määrän tehokkaasti kahden muuttujan avulla: a osoittaa edelliseen kohtaan, jossa on eri luku kuin kohdassa i, ja b osoittaa edelliseen kohtaan, jossa on eri luku kuin kohdissa i ja a. Nämä muuttujat ovat hyödyllisiä, koska osalistan tulee alkaa kohdan b jälkeen ja viimeistään kohdassa a. Niinpä kohtaan i päättyvien osalistojen määrä saadaan laskettua kaavalla a - b.

Esimerkiksi kun i on kohdassa 5, tilanne on seuraava:

Tässä tapauksessa a on kohdassa 3, jossa on luku 3, ja b on kohdassa 0, jossa on luku 1. Osalistojen määrä saadaan laskettua kaavalla 3 – 0 = 3.

Silmukan edetessä muuttujia a ja b täytyy päivittää sopivasti aina, kun kohdassa i on eri luku kuin kohdassa i - 1. Tässä on kaksi tapausta:

1. Jos kohdassa i on eri luku kuin kohdassa a, b siirtyy kohtaan a ja a siirtyy kohtaan i - 1.
2. Jos kohdassa i on sama luku kuin kohdassa a, vain a siirtyy kohtaan i - 1.

Katsotaan nyt, miten muuttujat päivittyvät äskeisessä esimerkissä. Kun i siirtyy kohdasta 5 kohtaan 6, kohdassa i on eri luku kuin kohdassa a. Niinpä kyseessä on tapaus 1, jolloin a siirtyy kohtaan 6 – 1 = 5 ja b siirtyy kohtaan 3:

Kun i siirtyy kohdasta 6 kohtaan 7, kohdassa i on sama luku kuin kohdassa a. Niinpä kyseessä on tapaus 2, jolloin vain a siirtyy kohtaan 7 – 1 = 6:

Tämän idean avulla saadaan tehokas algoritmi, joka voidaan toteuttaa seuraavasti:

def count_lists(numbers):
    n = len(numbers)
    a = b = -1
    result = 0
    for i in range(1, n):
        if numbers[i] != numbers[i - 1]:
            if numbers[i] != numbers[a]:
                b = a
            a = i - 1
        result += a - b
    return result

Tässä toteutuksessa a ja b ovat alussa -1 tarkoittaen, että ne eivät vielä osoita mihinkään listan kohtaan. Tämän ansiosta algoritmi laskee oikein osalistojen määrän myös listan alkuosassa.