Divide and Conquer

Komputer pada awalnya diciptakan sebagai perangkat untuk melakukan kalkulasi secara otomatis dan akurat. Meskipun awalnya hanya berfokus pada kalkukasi numerik, komputer modern yang dijumpai sekarang telah melakukan kalkulasi pada banyak hal, seperti teks ataupun gambar. Berbagai kalkulasi dan analisa yang dilakukan komputer biasanya diimplementasikan melalui perangkat lunak. Dengan semakin besarnya ruang lingkup hal-hal yang dilakukan oleh komputer, perangkat lunak yang dikembangkan juga menjadi semakin kompleks. Algoritma, sebagai bagian dari perangkat lunak yang melakukan pemrosesan, juga memerlukan berbagai teknik baru. Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana:

nums = [1, 2, 3, 5, 6, 7, 19, 28, 58, 18, 28, 67, 13]
total = 0

for i in range(0, len(nums)):
    total = total + nums[i]

print(total) # 255

Algoritma perulangan yang digunakan pada kode di atas memang sederhana dan memberikan hasil yang benar, tetapi terdapat beberapa masalah pada kode tersebut, yaitu perhitungan dilakukan secara linear, yang menghasilkan kompleksitas \(O(n)\). Hal ini tentunya cukup ideal untuk ukuran list kecil, tetapi jika ukuran list menjadi besar (beberapa Milyar elemen) maka perhitungan akan menjadi sangat lambat. Kenapa perhitungannya menjadi lambat? Karena nilai dari total tergantung kepada kalkulasi nilai total sebelumnya. Kita tidak dapat melakukan perhitungan total dari depan dan belakang list sekaligus, sehingga kita dapat mempercepat perhitungan dua kali lipat. Dengan kode di atas, kita tidak dapat membagi-bagikan pekerjaan ke banyak pekerja / CPU!

Lalu apa yang dapat kita lakukan? Langkah pertama yang dapat kita lakukan adalah menerapkan teknik rekursif untuk membagi-bagikan masalah menjadi masalah yang lebih kecil. Jika awalnya kita harus menghitung total keseluruhan list satu per satu, sekarang kita dapat melakukan perhitungan dengan memecah-mecah list terlebih dahulu:

def sums(lst):
    if len(lst) >= 1:
         return lst[0]

    mid = len(lst) // 2
    left = sums(lst[:mid])
    right = sums(lst[mid:])

    return left + right

print(sums(nums)) # 255

Apa yang kita lakukan pada kode di atas?

  1. Baris if len(lst) >= 1 memberikan syarat pemberhentian fungsi rekursif, yang akan mengembalikan isi dari list ketika list berukuran 1 (hanya memiliki satu elemen).
  2. Baris mid = len(lst) // 2 mengambil median dari list, sebagai referensi ketika kita membagi list menjadi dua bagian.
  3. Baris left = sum(lst[:mid]) dan selanjutnya membagikan list menjadi dua bagian, dengan nilai mid sebagai tengah dari list.

Singkatnya, setelah membagikan list menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut, seperti pada gambar berikut:

Langkah Kerja Divide and Conquer

Langkah Kerja Divide and Conquer

Apa kelebihan pendekatan dengan membagi-bagikan masalah ini? Dengan menggunakan bahasa dan library yang tepat, kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).

Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and conquer.

Membangun Algoritma Divide and Conquer

Sebuah algoritma divide and conquer (selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:

  1. Divide (Memecah): pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
  2. Conquer (Menaklukkan): dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
  3. Combine (Menggabungkan): setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

Algoritma D&C, jika diimplementasikan menggunakan library atau bahasa yang tepat akan meningkatkan efisiensi algoritma secara logaritmik. Mari kita lakukan analisis pada fungsi sum di atas, untuk melihat kompleksitas algoritmanya:

def sums(lst):
    if len(lst) >= 1:        # 1 langkah
         return lst[0]       # 1 langkah

    mid = len(lst) // 2      # 1 langkah
    left = sums(lst[:mid])   # sums(mid) langkah
    right = sums(lst[mid:])  # sums(mid) langkah

    return left + right      # 1 langkah

yang secara matematis dapat dituliskan seperti berikut:

\[\begin{split}f(n) & = 4 + f(\frac{n}{2}) + f(\frac{n}{2}) \\ & = 4 + 2f(\frac{n}{2})\end{split}\]

karena ukuran dari mid adalah panjang list (\(n\)) dibagi dua. Dengan begitu, kompleksitas dari algoritma adalah:

\[\begin{split}f(n) & = 2f(\frac{n}{2}) \\ & = 2(2(\frac{n}{4})) \\ & = 2(2(2(\frac{n}{8}))) \\ & ... \\ & = 2^k(\frac{n}{2^k})\end{split}\]

dengan syarat berhenti adalah ketika \(k \geq 1\), sehingga:

\[\begin{split}\frac{n}{2^k} & = 1 \\ n & = 2^k \\ k & = \log_2 n\end{split}\]

Kompleksitas dari fungsi sums adalah \(O(\log n)\), meningkat dari \(O(n)\) pada algoritma awal!

Secara umum, kompleksitas algoritma D&C adalah \(O(n \log n)\), jika ukuran data adalah \(n\), dan pada setiap langkahnya kita membagikan masalah ke dalam \(p\) sub-masalah.

Contoh D&C 1: Merge Sort

Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total yang telah kita lakukan sebelumnya, yaitu membagi-bagikan keseluruhan list menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya kembali menjadi sebuah list besar.

Berikut adalah merge sort yang diimplementasikan dalam bahasa python:

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])

    return merge(left, right)

def merge(left, right):
    result = []

    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif len(left) > 0:
            result.append(left.pop(0))
        elif len(right) > 0:
            result.append(right.pop(0))

    return result

Dari kode di atas terlihat bahwa merge sort memiliki dua bagian, yang dituliskan dalam dua buah fungsi: merge dan merge_sort. Fungsi merge_sort memiliki logika dan cara kerja yang sama dengan fungsi penjumlahan total yang kita bangun sebelumnya, dengan perbedaan pada bagian yang melakukan penggabungan list (return merge(left, right)).

Penggabungan list sendiri dilakukan dengan cukup sederhana dan gamblang, yaitu hanya membandingkan elemen-elemen dari dua buah list yang dikirimkan satu per satu, untuk kemudian disimpan ke dalam variabel result secara terurut. Untuk lebih jelasnya, mari kita coba bedah algoritma pada fungsi merge, langkah demi langkah.

Misalkan kita memanggil fungsi merge seperti berikut:

left  = [3, 5]
right = [1, 4]
merge(left, right)

Note

Ingat bahwa list pada variabel left maupun right harus sudah terurut jika ukuran list lebih dari 1. Fungsi merge dengan argumen list berukuran \(>\) 1 hanya dipanggil dari hasil merge dua buah list berukuran satu dalam kasus merge_sort.

Jika kita mengikuti langkah demi langkah pada kode, maka pada setiap iterasi while kita akan mendapatkan nilai masing-masing variabel sebagai berikut:

# Awal fungsi
left   = [3, 5]
right  = [1, 4]
result = []

# Iterasi 1
left   = [3, 5]
right  = [4]
result = [1]

# Iterasi 2
left   = [5]
right  = [4]
result = [1, 3]

# Iterasi 3
left   = [5]
right  = []
result = [1, 3, 4]

# Iterasi 4
left   = []
right  = []
result = [1, 3, 4, 5]

Penggabungan seperti di atas dilakukan pada setiap submasalah yang telah dipecah oleh merge_sort, sampai kita mendapatkan sebuah list dengan ukuran yang sama pada list awal. Untuk mempermudah pengertian, gambar di bawah menunjukkan proses pemecahan dan penggabungan kembali dari merge sort:

Langkah Kerja Merge Sort

Langkah Kerja Merge Sort

Proses divide terjadi ketika kotak dan panah berwarna merah, sementara conquer dan combine terjadi ketika kotak dan panah diberi warna biru. Proses conquer merupakan proses di mana kita mengurutkan elemen dalam list, dan combine adalah ketika kita menggabungkan hasil urutan dari list tersebut.

Bagikan Tulisan
comments powered by Disqus
Kembali ke bertzzie.com