Range dan Iterator

Perulangan for di Julia bekerja pada objek apa pun yang mengikuti protokol iterasi, yaitu sepasang fungsi iterate, dan range merupakan contohnya yang paling sering digunakan. Topik ini membahas range dengan evaluasi malas (lazy), protokol iterate(iter) dan iterate(iter, state), serta pembuatan iterator kustom. Setelah topik ini dipraktikkan, mekanisme di balik for dapat dibaca secara eksplisit dan objek yang didefinisikan sendiri dapat dijadikan sumber perulangan.

Range yang dievaluasi malas#

Range menyatakan deret bilangan beraturan dengan bentuk awal:langkah:akhir, atau awal:akhir apabila langkahnya satu. Objek 1:5, 0:2:10, dan 1:0.5:2 bertipe range dan tidak menyimpan elemennya satu per satu, melainkan hanya titik awal, langkah, dan titik akhirnya. Inilah evaluasi malas, yaitu nilai elemen baru dihitung pada saat diminta, sehingga range panjang sekalipun tetap kecil di memori.

println(1:5)
println(0:2:10)
println(1:0.5:2)
println(length(0:2:10))
println(sum(1:100))
println((1:5)[3])

1:5
0:2:10
1.0:0.5:2.0
6
5050
3

Fungsi length, sum, dan pengindeksan pada range dihitung langsung dari rumus tanpa membentuk array, dan tipe elemennya mengikuti tipe titik awal, yaitu Int untuk 1:5. Perbedaan jumlah memori terlihat pada perbandingan berikut.

r = 1:1_000_000
println(length(r))
println(sizeof(r))
println(sizeof(collect(r)))

1000000
16
8000000

Range satu juta elemen hanya menempati 16 byte karena menyimpan dua bilangan, sedangkan collect(r) membentuk Vector berisi seluruh elemennya sehingga membutuhkan 8000000 byte. Gunakan range apa adanya selama nilainya cukup dibaca secara berurutan, dan panggil collect hanya apabila array yang dapat diubah memang diperlukan.

Tipe konkretnya pun berbeda menurut bentuknya. 1:5 merupakan UnitRange{Int64} dengan langkah pasti satu, sedangkan 0:2:10 merupakan StepRange karena langkahnya dua, dan 1:0.5:2 menyimpan langkah pecahan. Range juga menjadi bentuk paling lazim untuk mengisi perulangan for, misalnya for i in 1:n, karena jumlah iterasinya sudah diketahui dan tidak ada array yang perlu dibentuk terlebih dahulu.

Protokol iterate#

Protokol iterasi Julia terdiri atas dua fungsi. Panggilan iterate(iter) mengembalikan tuple berisi nilai pertama dan state awal, sedangkan iterate(iter, state) mengembalikan tuple nilai berikutnya dan state berikutnya. Apabila elemen telah habis, keduanya mengembalikan nothing. Fungsi berikut menelusuri range 1:3 persis sebagaimana perulangan for melakukannya.

function telusuri(it)
    state = iterate(it)
    while state !== nothing
        nilai, state = state
        println(nilai)
        state = iterate(it, state)
    end
end

telusuri(1:3)

1
2
3

Perulangan for memanggil iterate di balik layar dengan pola yang sama, tanpa ada mekanisme tambahan. Pada range bilangan bulat, state-nya berupa nilai elemen berikutnya, sehingga setiap langkah cukup menambah satu. Bentuk for v in it setara dengan kerangka berikut.

# tidak-dijalankan
# for v in it setara dengan panggilan iterate berulang:
# state = iterate(it)
# while state !== nothing
#     v, state = state
#     # badan perulangan
#     state = iterate(it, state)
# end

Konsekuensinya, setiap objek yang menyediakan sepasang metode iterate dapat langsung digunakan pada for, collect, sum, dan fungsi koleksi lainnya.

State pada protokol ini tidak terbatas pada bilangan tunggal. Pembuat iterator bebas menentukan bentuknya, misalnya indeks berikutnya, sisa nilai yang belum diproses, atau objek berkas yang sedang dibaca. Ketentuan satu-satunya adalah versi dua argumen harus dapat melanjutkan state tersebut dan mengembalikan nothing pada saat elemennya habis.

Iterator kustom Kuadrat#

Iterator kustom dibuat dengan mendefinisikan struct, kemudian memperluas fungsi Base.iterate untuk struct tersebut. Struct Kuadrat berikut menghasilkan kuadrat bilangan 1 sampai n. Metode pertama memulai iterasi dengan state awal 1, sedangkan metode kedua menguji state, yaitu mengembalikan nothing apabila state melewati n atau tuple berisi kuadrat dan state berikutnya.

# kuadrat-iterator.jl
# Iterator kustom yang menghasilkan kuadrat 1 sampai n.

struct Kuadrat
    n::Int
end

Base.iterate(k::Kuadrat) = iterate(k, 1)
Base.iterate(k::Kuadrat, i::Int) = i > k.n ? nothing : (i^2, i + 1)

Base.length(k::Kuadrat) = k.n
Base.eltype(::Type{Kuadrat}) = Int

for v in Kuadrat(6)
    print(v, " ")
end
println()

println("length = ", length(Kuadrat(6)))
println("collect = ", collect(Kuadrat(6)))
println("sum = ", sum(Kuadrat(6)))

1 4 9 16 25 36
length = 6
collect = [1, 4, 9, 16, 25, 36]
sum = 91

Dua metode iterate sudah cukup untuk membuat Kuadrat(6) dapat diperulangkan. Perluasan Base.length dan Base.eltype bersifat opsional tetapi berguna, karena collect dan sum memanfaatkan keduanya untuk menyiapkan ukuran hasil dan tipe elemennya sejak awal. Apabila iterator menghasilkan tipe selain Int, nilai Base.eltype perlu disesuaikan agar array hasilnya bertipe yang tepat.

Iterator semacam ini bersifat malas pula, karena kuadrat berikutnya baru dihitung ketika diminta. Pola yang sama berlaku untuk iterator yang menghasilkan deret Fibonacci, pembacaan berkas per baris, atau pembacaan sensor yang dihitung sewaktu-waktu. Ketiga contoh itu sama-sama tidak perlu menampung seluruh isinya di memori.

Kesalahan umum#

Kesalahan berikut sering muncul saat protokol iterasi dipraktikkan. Yang pertama dapat direproduksi dan ditangkap pada contoh berikut.

struct TanpaIterasi
    x::Int
end

try
    for v in TanpaIterasi(1)
        println(v)
    end
catch e
    println(typeof(e))
end

MethodError

• Melakukan perulangan pada objek yang belum menyediakan metode iterate. Perulangan for berhenti dengan MethodError karena tidak ada metode yang cocok. Perbaikannya dengan memperluas Base.iterate sebagaimana pada struct Kuadrat, atau menggunakan struktur yang sudah dapat diiterasi seperti array dan tuple bila hanya penelusuran yang dibutuhkan.
• Menyediakan satu metode iterate saja sehingga iterasi berhenti setelah elemen pertama. Gejalanya, perulangan hanya menghasilkan satu nilai lalu berhenti tanpa pesan apa pun. Protokolnya menuntut sepasang metode, yaitu versi satu argumen untuk memulai dan versi dua argumen untuk melanjutkan.
• Memanggil collect pada iterator yang tidak terhingga atau sangat panjang. Prosesnya baru berhenti setelah memori habis, sehingga iterator semacam itu perlu dibatasi dengan pengambilan sejumlah elemen teratas, misalnya melalui Iterators.take(it, n), bukan dikumpulkan seluruhnya.

Ringkasan#

• Range seperti 1:5 dan 0:2:10 hanya menyimpan titik awal, langkah, dan titik akhir, sehingga memori yang digunakannya tetap kecil berapa pun panjangnya.
• Protokol iterasi terdiri atas iterate(iter) dan iterate(iter, state) yang mengembalikan tuple nilai dan state, atau nothing setelah elemen habis.
• Perulangan for memanggil iterate di balik layar, sehingga objek apa pun yang menyediakan sepasang metode tersebut dapat diperulangkan.
• Iterator kustom dibuat dengan memperluas Base.iterate, dan perluasan Base.length serta Base.eltype membuat collect dan sum bekerja lebih efisien.

Referensi#

• Interfaces — The Julia Language — Mendokumentasikan protokol iteration beserta contoh iterator kustomnya.
• Collections and Data Structures — The Julia Language — Mendaftar fungsi koleksi seperti collect, length, dan sum yang bekerja pada objek dapat diiterasi.