Big-O dalam bahasa lazy

Model biaya yang mengejutkan naluri imperatif.

Daftar isi

Biaya sebuah operasi pada list Haskell tidak selalu sesuai naluri yang terbentuk dari bahasa imperatif, karena evaluasi lazy memindahkan momen pembayaran biayanya. Topik ini membahas model biaya operasi list pada bahasa lazy, mulai dari kompleksitas dasar penyambungan, penghitungan panjang, dan pengindeksan, sampai titik di mana biaya benar-benar dibayar, yaitu ketika evaluasi dipaksa. Setelah membacanya, pertumbuhan biaya operasi dasar dapat diperkirakan sebelum program dijalankan, dan pola penggunaan yang menyembunyikan pertumbuhan kuadratik dapat dikenali lebih dini.

Kompleksitas pertumbuhan#

Notasi Big-O menyatakan batas pertumbuhan banyaknya langkah sebuah operasi terhadap ukuran masukannya. Ukuran masukan pada operasi list umumnya adalah panjang list, yang ditulis $n$ . Operasi $O(1)$ membutuhkan langkah tetap berapa pun panjang listnya, operasi $O(n)$ tumbuh sebanding dengan panjang list, sedangkan operasi $O(n^2)$ tumbuh sebanding dengan kuadrat panjang list. Notasi ini tidak mengukur waktu absolut, melainkan bentuk pertumbuhannya, sehingga dua operasi $O(n)$ pada dua bahasa yang berbeda tetap dapat berbeda kecepatannya.

Tabel berikut merangkum biaya operasi list yang paling sering digunakan. Penentu utamanya adalah definisi rekursif setiap operasi, misalnya (++) melintasi list pertamanya sel demi sel sampai habis, sehingga biayanya ditentukan oleh panjang list pertama dan tidak bergantung pada panjang list kedua. Dokumentasi Data.List pada pustaka standar mencantumkan anotasi kompleksitas serupa untuk banyak fungsi lainnya, seperti sort yang dicatat $O(n \log n)$ dan nub yang dicatat $O(n^2)$ .

Ekspresi	Biaya	Alasan
`x : xs`	$O(1)$	satu sel list baru dibangun
`head xs`, `tail xs`	$O(1)$	cukup membaca sel pertama
`xs !! i`	$O(i)$	sel dilalui satu per satu sampai indeks ke-i
`length xs`	$O(n)$	seluruh sel dilalui untuk dihitung
`xs ++ ys`	$O(n)$	list pertama dilintasi sampai habis
`reverse xs`	$O(n)$	seluruh sel dilalui dan dibangun ulang
`sum xs`	$O(n)$	setiap sel dikunjungi sekali

Biaya dibayar ketika evaluasi dipaksa#

Pada bahasa lazy, membangun struktur dan menghitung isinya adalah dua kegiatan yang terpisah. Ekspresi map (* 10) [1 ..] segera menghasilkan list, tetapi perkaliannya baru dijalankan ketika sebuah elemen benar-benar diminta. Konsekuensinya, take 5 pada list tak hingga selesai dalam lima langkah, bukan dengan menghabiskan waktu untuk menghitung seluruh list lebih dahulu. Biaya yang tadinya tampak tak terhingga menjadi $O(k)$ terhadap banyaknya elemen yang diminta, dan sama sekali tidak bergantung pada panjang list sumbernya.

Program berikut mengukur biaya itu secara langsung. Fungsi indeksBerukur menghitung banyaknya sel yang dilalui untuk mencapai sebuah indeks, lalu melaporkannya sebagai pasangan berupa banyak langkah dan nilainya.

haskell biaya-take.hs

-- lima elemen pertama dari peta di atas list tak hingga
lima :: [Int]
lima = take 5 (map (* 10) [1 ..])

-- versi indeks yang melaporkan banyak sel yang dilalui (pasangan: langkah, nilai)
indeksBerukur :: Int -> [a] -> (Int, a)
indeksBerukur i (x : xs)
  | i == 0 = (0, x)
  | otherwise = let (n, v) = indeksBerukur (i - 1) xs in (n + 1, v)
indeksBerukur _ [] = error "indeks terlalu besar"

main :: IO ()
main = do
  print lima
  print (indeksBerukur 3 (map (* 10) [1 ..]))
  -- melintasi spine map tidak memaksa isinya
  print (fst (indeksBerukur 3 (map undefined [1 ..])))

text Keluaran

[10,20,30,40,50]
(3,40)
3

Baris kedua mengambil elemen berindeks 3, yaitu elemen keempat karena list diindeks mulai dari nol, dan laporannya menunjukkan tiga sel yang dilalui. Perkalian (* 10) pada setiap kepala sel baru dihitung ketika keluaran dicetak, bukan ketika listnya dilalui. Baris ketiga memperlihatkan sisi yang lebih tajam lagi: melintasi spine, yaitu rangkaian sel list tanpa menyentuh isinya, tidak memaksa kepala sel sama sekali, sehingga isi elemennya boleh berupa undefined dan program tetap selesai tanpa error.

Operasi yang menyembunyikan biaya#

Pengindeksan adalah sumber kejutan pertama bagi naluri imperatif. Pada array, mengakses indeks mana pun berbiaya $O(1)$ , sedangkan xs !! i pada list melintasi $i$ sel pada setiap pemanggilan. Perulangan yang mengindeks list dari indeks nol sampai akhir menghabiskan waktu secara kuadratik, padahal setiap pemanggilan terlihat murah. Solusinya bukan memperbaiki aksesnya, melainkan mengganti pola kerjanya dengan foldl, foldr, atau perulangan yang membawa elemen secara langsung tanpa mengindeks ulang.

Kejutan kedua ada pada penyambungan di akhir list. Menyambung x di akhir list berarti melintasi seluruh list yang sudah ada lebih dahulu, sehingga operasi yang kelihatannya semurah (:) sebenarnya berbiaya $O(n)$ . Apabila penyambungan di akhir diulang $k$ kali, banyak langkahnya menjadi

0 + 1 + 2 + \cdots + (k-1) = \frac{k(k-1)}{2}

yang tumbuh kuadratik terhadap $k$ . Program berikut membuktikannya dengan versi penyambungan yang melaporkan banyak sel yang dilalui. Perbandingan tambahBelakang 6 dan tambahDepan 6 menunjukkan selisihnya untuk list yang isinya sama.

haskell biaya-sambung.hs

-- sambung versi berukur: melaporkan banyak sel list pertama yang dilalui
sambungBerukur :: [Int] -> [Int] -> (Int, [Int])
sambungBerukur [] ys = (0, ys)
sambungBerukur (x : xs) ys =
  let (n, hasil) = sambungBerukur xs ys
  in (n + 1, x : hasil)

-- menyambung satu elemen di akhir list, diulang k kali
tambahBelakang :: Int -> (Int, [Int])
tambahBelakang k = foldl langkah (0, []) [1 .. k]
  where
    langkah (n, xs) x = let (m, ys) = sambungBerukur xs [x] in (n + m, ys)

-- menyambung satu elemen di depan list, diulang k kali
tambahDepan :: Int -> (Int, [Int])
tambahDepan k = foldl langkah (0, []) [1 .. k]
  where
    langkah (n, xs) x = let (m, ys) = sambungBerukur [x] xs in (n + m, ys)

main :: IO ()
main = do
  print (fst (sambungBerukur [1 .. 5] [6 .. 10]))
  print (fst (sambungBerukur [1 .. 10] [6 .. 10]))
  print (tambahBelakang 6)
  print (tambahDepan 6)

text Keluaran

5
10
(15,[1,2,3,4,5,6])
(6,[6,5,4,3,2,1])

Dua baris pertama menegaskan bahwa biaya (++) ditentukan oleh list pertamanya, sebab hasil gabungannya sama, tetapi langkahnya 5 untuk list pertama sepanjang 5 dan 10 untuk list pertama sepanjang 10. Dua baris terakhir menunjukkan 15 langkah untuk penyambungan di akhir dibandingkan dengan 6 langkah untuk penyambungan di depan pada list yang sama. Selisih ini melebar cepat, sebab banyak langkah penyambungan di akhir tumbuh seperti $\frac{k(k-1)}{2}$ , sedangkan penyambungan di depan selalu $k$ langkah.

Model biaya yang lebih mengejutkan lagi justru berupa kabar baik. Pada bahasa imperatif, map atas sebuah list mengalokasikan seluruh list hasilnya di memori sebelum langkah berikutnya berjalan. Pada Haskell, sum (map f xs) mengalirkan satu elemen pada satu waktu, sehingga list antara tidak pernah ada secara utuh dan puncak memorinya tetap kecil.

Angka-angka pada bagian ini dapat dijelajahi dengan demo berikut. Geser slider untuk mengubah ukuran masukan $n$ , kemudian bandingkan jumlah langkah dari ketiga pola biaya tersebut.

Kesalahan umum#

Menganggap length dan akses indeks berbiaya $O(1)$ adalah kesalahan yang paling sering terjadi. Naluri dari array membuat panjang list dianggap tersimpan, padahal length xs harus melintasi seluruh list, dan xs !! i harus melintasi $i$ sel. Perbaikannya ada dua, yaitu menghitung panjang sekali di awal lalu menyimpannya dalam variabel, atau memindahkan datanya ke struktur yang panjangnya $O(1)$ seperti Data.Sequence pada paket containers.

Kesalahan kedua adalah menyambung di akhir list di dalam perulangan. Pola xs ++ [x] yang diulang untuk membangun list hasil membuat setiap iterasi melintasi seluruh hasil sebelumnya, sehingga total biayanya kuadratik meskipun data yang diproses tidak besar. Perbaikannya berupa menyambung di depan dengan x : acc selama perulangan, kemudian reverse sekali di akhir, sehingga total biayanya kembali menjadi $O(n)$ .

Ringkasan#

Biaya operasi list mengikuti definisi rekursifnya, yaitu (:) dan head berbiaya $O(1)$ , sedangkan (++), length, !!, dan reverse melintasi list sehingga berbiaya linier.
Evaluasi lazy memindahkan pembayaran biaya ke momen pemaksaan, sehingga take 5 pada list tak hingga hanya menghitung lima elemen.
Melintasi spine list tidak memaksa isi selnya, dan (++) hanya melintasi list pertamanya.
Penyambungan berulang di akhir list tumbuh kuadratik, sedangkan penyambungan di depan tetap linier.

Referensi#

Data.List — Hackage — Dokumentasi modul list pustaka standar yang mencantumkan anotasi kompleksitas pada banyak fungsinya.
Data.Sequence — Hackage — Dokumentasi struktur data urut dengan penghitungan panjang $O(1)$ sebagai alternatif list.
6.2 Strict Evaluation — Haskell 2010 Language Report — Spesifikasi semantik non-strict pada aplikasi fungsi Haskell.