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ä.