Algoritmien benchmarkkaaminen Julialla

Funktioiden benchmarkkaaminen Juliassa on tehty helpoksi erikseen asennttavalla BenchmarkTools-paketilla. Tarkastellaan seuraavanlaista ongelmaa: käyttäjälle annetaan kokonaislukulista arr, ja yksittäinen luku target. Implementoi funktio, joka palauttaa indeksiparin (i, j) siten, että listan alkioiden summa on target, siis arr[i] + arr[j] = target. Kannattaa käyttää hetki aikaa ja miettiä ratkaisua.

Eräs ratkaisu joka varmastikin tulee ensimmäisenä mieleen, on tuplalooppi. Käydään listan alkiot läpi kahdella sisäkkäisellä loopilla, ja mikäli niiden summa on target, tehtävä on ratkaisu.

function find_indices_1(arr, target)
    for i=1:length(arr)
        for j=i+1:length(arr)
            if arr[i] + arr[j] == target
                return (i, j)
            end
        end
    end
    error("not found.")
end
using Random
Random.seed!(1)
const N = 10
const arr = rand(1:N, 10)
@show arr
arr = [3, 8, 2, 6, 3, 3, 4, 5, 1, 4]

Nyt esimerkiksi find_indices_1(arr, 14) palauttaa indeksiparin (2, 4), koska $8 + 6 = 14$.

Sitten varsinaiseen aiheeseen. Algoritmista jo näkeekin, että sen kompleksisuus on $O(N^2)$. Juliassa asian voi empiirisesti todeta BenchmarkToolsilla. Tehdään muutama eripituinen lista ja varmistetaan, että indeksipari (i,j) ovat listan viimeiset alkiot, jolloin saadaan worst case scenario.

const M = 2^12
const arr1 = rand(1:N, 1*M)
const arr2 = rand(1:N, 2*M)
const arr3 = rand(1:N, 4*M)
const target = 4*N + 2
arr1[end-1] = arr1[end] = div(target, 2)
arr2[end-1] = arr2[end] = div(target, 2)
arr3[end-1] = arr3[end] = div(target, 2)

@show find_indices_1(arr1, target)
@show find_indices_1(arr2, target)
@show find_indices_1(arr3, target)
find_indices_1(arr1, target) = (4095, 4096)
find_indices_1(arr2, target) = (8191, 8192)
find_indices_1(arr3, target) = (16383, 16384)

Kaksikin tapausta kyllä riittäisi. Kolmas tuo varmuutta päättelyyn. Lisäksi tehdään sopiva apufunktio, joka ajaa benchmarkin kaikille kolmelle eri tapaukselle.

function benchmark(f, name)
    println("*** $name ***")
    println("Array 1, size = $(length(arr1))")
    @btime $f(arr1, target)
    println("Array 2, size = $(length(arr2))")
    @btime $f(arr2, target)
    println("Array 3, size = $(length(arr3))")
    @btime $f(arr3, target)
end

benchmark(find_indices_1, "find_indices_1")
*** find_indices_1 ***
Array 1, size = 4096
  4.149 ms (0 allocations: 0 bytes)
Array 2, size = 8192
  17.239 ms (0 allocations: 0 bytes)
Array 3, size = 16384
  69.105 ms (0 allocations: 0 bytes)

Nyt, log2-asteikolla

(log2(17.239) - log2(4.149)) / (log2(8192) - log2(4096))
2.0548405266707026

Kun $N$ kaksinkertaistuu, $t$ nelinkertaistuu.

17.239 * 4
68.956

Johtopäätös tästä on, että toimii hyvin pienillä $N$ arvoilla, mutta skaalautuu huonosti. Kaikenkaikkiaan, algoritmin tarkastelu BenchmarkToolsin avulla oli varsin suoraviivaista. Ennen sen suurempia optimointeja on varsin helppoa tarkastaa empiirisesti, mikä algoritmin aikakompleksisuus on.

Parempia algoritmeja

Voisiko algoritmia sitten jotenkin parantaa? Voisi.

Ei ole välttämättä tarpeen tehdä kahta sisäkkäistä ohjelmointisilmukkaa, jos tallennetaan listan arvot hajautustaulukon avaimina. Silloin on mahdollista tehdä yksinkertainen sanakirjahaku jolla selvittää, löytyykö sopiva indeksi hajautustaulusta, koska arr[i] + arr[j] = target mutta on myös niin, että arr[j] = target - arr[i].

function find_indices_2(arr, target)
    d = Dict{Int, Int}()
    for i=1:length(arr)
        d[arr[i]] = i
    end
    for i=1:length(arr)
        c = target - arr[i]
        if haskey(d, c)
            return (i, d[c])
        end
    end
   error("not found.")
end

Nythän tässä käydään sama lista kaksi kertaa läpi, joten algoritmin kompleksisuus onkin enää lineaarista. Hajautustauluun tallentaminen ja lukeminen tapahtuu vakioajassa.

benchmark(find_indices_2, "find_indices_2")
*** find_indices_2 ***
Array 1, size = 4096
  65.181 μs (7 allocations: 1.97 KiB)
Array 2, size = 8192
  133.816 μs (7 allocations: 1.97 KiB)
Array 3, size = 16384
  266.624 μs (7 allocations: 1.97 KiB)

69.105 millisekunnista 0.266 millisekuntiin.

log2(133.816) - log2(65.181)
1.0377272342180248

Tällä muutoksella päästiin $O(N)$ algoritmiin. Muita optimointeja voisi olla esimerkiksi hajautustaulun korvaaminen listalla, mikäli listassa arr esiintyvät luvut ovat suhteellisen hyvin klusteroituneita.

function find_indices_3(arr, target)
    d = zeros(Int, max(target, maximum(arr)))
    for i=1:length(arr)
        d[arr[i]] = i
    end
    for i=1:length(arr)
        c = target - arr[i]
        if d[c] != 0
            return (i, d[c])
        end
    end
   error("not found.")
end

benchmark(find_indices_3, "find_indices_3")
*** find_indices_3 ***
Array 1, size = 4096
  6.647 μs (1 allocation: 448 bytes)
Array 2, size = 8192
  13.274 μs (1 allocation: 448 bytes)
Array 3, size = 16384
  26.559 μs (1 allocation: 448 bytes)

On taas 10 kertaa nopeampi kuin edellinen algoritmi.

Algoritmia voi vielä hieman nopeuttaa ja yksinkertaistaa huomaamalla, että oikeastaan ei tarvita kahta silmukkaa, vaan kaikki voidaan tehdä yhdessä.

function find_indices_4(arr, target)
    arrsize = max(target, maximum(arr))
    d = zeros(Int, arrsize)
    for i=1:length(arr)
        c = target - arr[i]
        d[c] != 0 && return (i, d[c])
        d[arr[i]] = i
    end
   error("not found.")
end

benchmark(find_indices_4, "find_indices_4")
*** find_indices_4 ***
Array 1, size = 4096
  6.321 μs (1 allocation: 448 bytes)
Array 2, size = 8192
  12.607 μs (1 allocation: 448 bytes)
Array 3, size = 16384
  25.221 μs (1 allocation: 448 bytes)

Voimme määritellä arrsize funktion parametrina:

function find_indices_5(arr, target, arrsize=50)
    d = zeros(Int, arrsize)
    for i=1:length(arr)
        c = target - arr[i]
        d[c] != 0 && return (i, d[c])
        d[arr[i]] = i
    end
   error("not found.")
end

benchmark(find_indices_5, "find_indices_5")
*** find_indices_5 ***
Array 1, size = 4096
  5.606 μs (1 allocation: 496 bytes)
Array 2, size = 8192
  10.065 μs (1 allocation: 496 bytes)
Array 3, size = 16384
  20.105 μs (1 allocation: 496 bytes)

Lisäksi, voimme varata vektorin d funktion ulkopuolella jolloin saamme ensimmäisen algoritmin tapaisen ratkaisun johon ei sisälly muistin varauksia.

function find_indices_6!(d, arr, target)
    d = fill!(d, 0)
    for i=1:length(arr)
        c = target - arr[i]
        d[c] != 0 && return (i, d[c])
        d[arr[i]] = i
    end
   error("not found.")
end

function benchmark!(f, name)
    println("*** $name ***")
    println("Array 1, size = $(length(arr1))")
    @btime $f($d, arr1, target)
    println("Array 2, size = $(length(arr2))")
    @btime $f($d, arr2, target)
    println("Array 3, size = $(length(arr3))")
    @btime $f($d, arr3, target)
end

const d = zeros(Int, 50)
benchmark!(find_indices_6!, "find_indices_6!")
*** find_indices_6! ***
Array 1, size = 4096
  5.028 μs (0 allocations: 0 bytes)
Array 2, size = 8192
  10.061 μs (0 allocations: 0 bytes)
Array 3, size = 16384
  20.094 μs (0 allocations: 0 bytes)

Lopuksi, jos olemme varmoja siitä, että d on sopivan mittaisena varattu, voidaan poistaa bounds check, eli:

function find_indices_7!(d, arr, target)
    d = fill!(d, 0)
    @inbounds for i=1:length(arr)
        c = target - arr[i]
        d[c] != 0 && return (i, d[c])
        d[arr[i]] = i
    end
   error("not found.")
end

benchmark!(find_indices_7!, "find_indices_7!")
*** find_indices_7! ***
Array 1, size = 4096
  3.055 μs (0 allocations: 0 bytes)
Array 2, size = 8192
  6.026 μs (0 allocations: 0 bytes)
Array 3, size = 16384
  12.077 μs (0 allocations: 0 bytes)

Alamme jo olemaan aika hyvässä vauhdissa. Alkuperäinen algoritmi otti 16384 pitkällä listalla 69 millisekuntia, tämänhetkinen nopein implementaatio 12 mikrosekuntia. En usko että tästä enää paljoa voidaan parantaa, asiaa voisi empiirisesti tutkia implementoimalla jollakin toisella ohjelmointikielellä.