ALGORITME PEMROGRAMAN
Kompleksitas waktu T(n) atau ruang S(n), untuk jumlah data n yang sangat banyak pada kasus terjelek dinotasikan dengan O(1), O(n), O(n log n), O(n2), O(2n) untuk kompleksitas konstan, linear, linear logaritmik, kuadratik, eksponensial. Bagaimana caranya proses dilakukan disebut algoritma.
Brute Force Algorithm
Algoritme ini 'menebak' jawaban lalu menguji betul tidaknya sesuai definisi. Algoritme jenis ini biasanya ditempuh bila kita tidak dapat membuat langkah prosedur yang cerdik untuk memecahkan suatu persoalan selain mengikuti definisinya.
Contoh, mencari akar pangkat tiga dari suatu angka X dengan cara mengumpulkan semua angka tebakan dan mengujinya satu per satu apakah angka tersebut jika dipangkatkan 3 sama dengan angka X.
# finding a cube root of a perfect cube
x = int(input("enter an integer ")) # for example 1957816251
# menebak berulang ulang
ans = 0
while ans**3 < x :
ans = ans + 1
# kesimpulan
if ans**3 != x:
print(x, 'is not a perfect cube')
else:
print(f'Cube root of {x} is {ans}')
Rentang (range) tebakan kita dimulai dari nol sampai suatu angka yang jika dipangkatkan dengan 3 sama atau melampaui angka X, artinya kompleksitas waktu iterasi linear.
Cara menebak sangat sederhana, dimulai dari angka nol, lalu angka tebakan selanjutnya adalah tebakan saat ini ditambah satu. Algoritma ini memastikan bahwa kita akan mendapatkan kesimpulan berupa bilangan bulat yang merupakan jawaban yang tepat atau bahwa angka X bukan merupakan pangkat 3 dari suatu bilangan bulat.
Algoritma ini dapat diperbaiki dengan mengatur rentang awal dan tebakan pada posisi di tengah rentang lalu dari hasil sementara dapat di pastikan bahwa tebakan itu terlalu tinggi atau terlalu rendah sehingga rentang selanjutnya akan berada pada setengah di bawah atau setengah di atas dari rentang awal. Demikian berulang ulang sehingga proses pencarian diefisienkan dari linear menjadi sub-linear, logaritmik. Namun ada yang perlu kita perhatikan bahwa penambahan metode ini akan melibatkan nilai pecahan dan hal ini dapat berlanjut tanpa mendapatkan hasil, makanya perlu digunakan suatu angka kecil, epsilon sebagai batas bahwa hasil yang didapatkan sudah cukup mendekati.
# bisection search
x = 1957816251.0
assert x > 0, 'dibatasi untuk nilai positif'
# tentukan rentang pencarian
ren_bawah = 0
if x >= 1:
ren_atas = x
else:
ren_atas = 1
tebak = (ren_bawah + ren_atas) / 2
epsilon = 0.001
while abs(x - tebak ** 3) > epsilon:
if tebak ** 3 > x:
ren_atas = tebak
else:
ren_bawah = tebak
tebak = (ren_bawah + ren_atas) / 2
print(tebak)
Aplikasi algoritme brute force sangat luas, dapat digunakan pada berbagai bidang, namun karena umumnya berat untuk dilaksanakan maka orang mencari optimasi untuk perbaikan kinerjanya, misalnya yang disebut dynamic programming atau program dinamis, menebak dengan suatu cara yang lebih cerdik, memecah masalah menjadi sub masalah dan menyelesaikan masalah utama secara rekursif, iteratif, dengan pendekatan memoize, bottom-up, atau lainnya.
Sieve of Eratosthenes
Eratosthenes menemukan algoritma untuk mendaftarkan bilangan prima dengan operasi penjumlahan saja, dimulai dari angka 2 sampai akar 2 limit yang dimasukkan. Misalnya kita akan mencari semua bilangan prima lebih kecil dari 10,000. Siapkan array 1 byte sebesar 10,000 dan asumsikan semuanya True sebagai bilangan prima. Algoritmanya adalah dengan dua putaran bersusun, putaran pertama melakukan scanning dari 2 sampai 100 sebagai indeks start, dan putaran kedua mencoret semua sel item yang indeksnya kelipatan dari indeks start, mulai dari start kuadrat sampai mencapai 10,000. Lakukan perulangan pada putaran pertama untuk nilai berikutnya yang belum dicoret.
# sieve of eratosthenes.py
from array import array
from time import time
def timer(fn):
def inner(*args, **kwargs):
start = time()
answer = fn(*args, **kwargs) # fn is free variable
end = time()
print(f'time elapsed {end - start:.2f} seconds')
return answer
return inner
@timer
def primes_sieve(limit: int) -> tuple:
# byte array allocation, 1 byte per item for boolean result each
sieve = array('b', [True] * limit)
iterasi = 0
sieve[0] = sieve[1] = False # zero and one are not prime numbers.
for start in range(2, int(limit ** 0.5) + 1):
if not sieve[start]:
continue
idx = start ** 2
while idx < limit:
sieve[idx] = False
iterasi += 1
idx += start
return (i for i, prime in enumerate(sieve) if prime), iterasi
x = int(input("enter a number "))
primes, count = primes_sieve(x)
# make use of a generator to store output values
print(type(primes))
print(f'iterasi = {count :,}')
for i,p in enumerate(primes): pass #print(p, end=' ')print()
print(f'jumlah bilangan prima {i+1:,}')
Algoritme saringan/tapis Eratosthenes cukup bagus kompleksitas waktunya O(n log log n). Dalam kode di atas kita menghemat memori dengan pertama, menggunakan array byte untuk menyimpan hasil boolean, dan kedua, tidak memakai buffer lagi untuk outputnya. Kita juga menyisipkan decorator timer untuk mencatat indikasi waktu relatif yang dibutuhkan untuk eksekusi sesuai kecepatan CPU, dan besar angka limit. Hasil run tanpa print bil primanya:
enter a number 10_000_000
time elapsed 6.06 seconds
<class 'generator'>
iterasi = 22,850,049
jumlah bilangan prima 664,579
Jika dimaui pencetakan bilangan primanya, tinggal dihapus statement pass dan comment #, sehingga badan for..loop berisi perintah print(p, end=' ')
ALGORITME EUKLIDES
Salah satu algoritma yang dibuat Euclides adalah tentang mencari bilangan pembagi persekutuan terbesar (Greatest Common Divisor). PPB dari dua bilangan adalah bilangan terbesar yang dapat habis membagi kedua bilangan. Contoh ppb dari 24 dan 42 adalah 6. Kita dapat saja melakukan brute force dengan membagi nilai yang lebih besar dengan nilai yang lebih kecil, melihat apakah habis membagi, lalu mengurangi nilai pembagi satu per satu sampai ketemu nilai yang habis membagi kedua angka. Untuk angka yang besar brute force seperti ini tidak efisien, lebih baik menggunakan cara/algoritma Euclidean.
- Jika ada dua angka a dan b, a lebih besar dari b:
- maka a = qb + r , yang mana q adalah pembagi, r adalah sisa, dan b > r
- jika ada bilangan x yang mana a dan b habis dibagi x,
- maka b dan r juga habis dibagi x
- jelasnya, jika a dan b adalah kelipatan dari x, maka (a-b) juga adalah kelipatan x, demikian juga jika a' adalah qb+r, sama saja r adalah kelipatan x.
- reduksi dari a,b menjadi b,r yang mana r adalah a mod b
- gcd(a,b) = gcd(b,a%b)
- sampai tercapai kondisi bahwa sisanya nol
# Greatest Common Divisor
def gcd(a,b):
while b != 0:
a, b = b, a%b
return a
print(f'{gcd(24,42) = }')
gcd(24,42) = 6
Kompleksitas waktu algoritma gcd diperkirakan logaritmik dan terkait dengan suatu angka yang disebut golden ratio. Referensi menyebutkan bahwa iterasi gcd terpanjang adalah antar dua angka fibonacci berurutan. Berikut kita lihat contoh programnya.
# GCD, Fibonacci, Golden ratio, O(log a)
from math import log
def gcd(a, b):
i = 0
while b != 0:
a, b, i = b, a % b, i + 1
return a, i
def fib_tail(n, a=0, b=1):
if n == 0:
return a
if n == 1:
return b
return fib_tail(n - 1, b, a + b)
x = fib_tail(402)
y = fib_tail(401)
print(f'{x = }\n{y = }')
phi = x / y
golden_ratio = (1 + 5 ** 0.5) / 2
print(f'{golden_ratio = }\n{ phi = }')
ans = gcd(x, y)
print(f'gcd antar fib : {ans[0]}')
print(f'iterasi: {ans[1]}')
print(f'{log(x,golden_ratio) = }')
print('T(n) gcd(a,b) = O(log a)')
y = 284812298108489611757988937681460995615380088782304890986477195645969271404032323901
golden_ratio = 1.618033988749895
phi = 1.618033988749895
gcd antar fib : 1
iterasi: 400
log(x,golden_ratio) = 400.3277240618154
T(n) gcd = O(log a)
Pada percobaan di atas kita sudah menggunakan angka angka yang besar sehingga dapat menyimpulkan (tanpa pembuktian) bahwa kompleksitas algoritma gcd() adalah sub-linear yaitu:
T(n) = O(logphi a)
Sums of continuous range
Untuk melengkapi pembahasan ragam kompleksitas waktu eksekusi, kita akan melihat contoh kecil yang di dalamnya terdapat 'algoritma' atau rumusan sehingga waktu eksekusi tidak tergantung kepada besarnya data, tetapi terlihat konstan.
Suatu penjumlahan deret angka sinambung dari 1, 2,.. sampai n, harus dihitung secara satu per satu dengan kompleksitas O(n), kalau kita belum tahu caranya. Mari kita perhatikan
n (n-1) (n-2) ..... 1
------------------------------ +
(n+1) (n+1) (n+1) ..... (n+1)
Sedemikian sehingga jumlah angka di rentang 1 sampai n, adalah n * (n+1) / 2, berapa pun besar nilai n. Kompleksitas waktu adalah O(1), konstan, bila proses perkalian dianggap konstan.
Karatsuba algorithm
Bila kita bekerja dengan angka-angka kecil maka perkalian dua angka akan memakan waktu yang sama saja. Anggap CPU atau co-processor komputer kita memiliki kemampuan perkalian 64 bits, maka selama angkanya di dalam rentang itu, perkalian dilakukan secara hardware dalam sekejap tanpa iterasi software. Nilai 64-bit itu adalah 2^64 sekitar 20 digit saja, = '18,446,744,073,709,551,616'.
Jika angka kita misalnya 40 digit, maka kita perlu melakukan proses perkalian tangan atau algoritma sekolah menengah dengan iterasi 40 digit x 40 digit = 1600 kali perkalian dan beberapa penjumlahan.
Jika angka kita misalnya 70-an digit, maka iterasi perkalian ≈ 5000 maka kita perlu menggunakan algoritma perkalian yang ditemukan Anatoly Alexeyevich Karatsuba. Python menggunakannya untuk angka yang besar (di atas 70 digit).
Kita tidak akan membahas algoritma Karatsuba kali ini, cukup mengatakan bahwa iterasi tradisional n2 diperbaiki menjadi n1.58 adalah sungguh suatu terobosan, dari 5041 (71^2) iterasi menjadi 841 (71^1.58) iterasi, khoroso!
Selection Sort
Algoritma mengurutkan angka yang biasa biasa berada dalam kompleksitas O(n2) seperti contoh kita ini. Jika algoritma kita mengandung dua loop bertingkat, maka terindikasi sebagai kompleksitas kuadratis, yaitu n * n.
Selection sort menyiapkan dua daerah kiri kanan, yang kiri adalah yang sudah diurutkan, yang kanan belum. Ada dua loop bersusun disini, pertama yang memisahkan daerah kiri dan kanan, yang kedua mencari nilai yang lebih kecil untuk ditukar tempat dengan posisi awal saat ini. Lihat penjelasan dengan animasi di kanal ini selectionsort
def select_sort(nums):
for i in range(len(nums)):
awal = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[awal]:
awal = j
nums[i], nums[awal] = nums[awal], nums[i] # swap!
numbers = [randint(11,99) for x in range(20)]
print(*numbers)
select_sort(numbers)
print(*numbers)
Program kita kali ini cukup singkat, ada dua for..loop bertingkat (nested) dengan satu perbandingan nilai, pembaruan indeks array, dan swap atau bertukar tempat. Mari kita relaks sedikit membahas swap.
Objek dan Nama dalam Python
Dalam bahasa pemrograman lainnya umumnya untuk melakukan swap diperlukan suatu variabel sementara karena assignment akan menimpa nilai sebelumnya. C++ memiliki library fungsi swap() khusus, tetapi Python melakukan swap seperti tanpa kesulitan. Hal ini karena makna suatu variabel dalam Python berbeda dengan pada bahasa lain. Bila kita terbiasa mengartikan variabel adalah tempat untuk menyimpan suatu nilai, objek, maka Python akan memberikan suatu konsep yang berbeda.
Python tidak memiliki variabel (yang kita kenal), Python hanya mencatat nama suatu pointer dari sebuah objek. Pada waktu kita melakukan assignment, maka prosesnya adalah objek ekspresi dibuat dulu di suatu tempat perkumpulan objek, lalu nama yang kita definisikan dicatat bersama pointer objeknya dalam suatu scope namespace tertentu. Catatan nama beserta pointer itu dapat diubah sewaktu dilakukan assignment baru, pointer-nya yang diganti. Nama 'variabel' itu sendiri dapat hilang jika program mencapai titik di luar scope tempat nama itu didefinisikan, atau kita sengaja membuang nama itu dengan statement del. Nama itu pada dasarnya terpisah dari objek. Dalam objek tidak ada link balik ke nama yang memegang objek itu; objek hanya memiliki catatan berapa banyak nama, alias yang digunakan untuk pointer objek itu. Jika suatu nama mengalihkan pointer-nya maka catatan jumlah pemegang dalam objek sebelumnya berkurang, dan jika jumlah pemegang tersebut menjadi nol, maka objek itu menjadi kandidat untuk didaur ulang menjadi objek lainnya atau ruang memori bebas. Suatu nama hanya memegang satu objek saja, tetapi tidak eksklusif, beberapa nama alias dapat mengacu kepada objek yang sama.
Kembali ke kasus swap, objek di sisi kanan disiapkan dulu masing-masing pointer-nya, lalu dicatatkan ulang ke beberapa nama, tidak peduli nama bekas atau baru. Hanya saja jika suatu nama diberikan pointer baru, maka catatan jumlah nama pemilik pada objek yang sebelumnya dikurangi satu, dan pada objek yang baru bertambah satu. Tidak ada cerita suatu nilai ditimpa dengan nilai lain, tidak ada perpindahan alamat, lokasi objek. Pemindahan kepemilikan tidak mengubah alamat atau nilai objek; catatan jumlah pemilik dapat berubah dan catatan tipe/nilai objek mana yang dimiliki nama pemilik dapat berubah secara dinamis. (jaman dulu banget nama ABC$ adalah khusus untuk tipe string, dan nama ABC _tanpa $_ untuk tipe angka)
Satu hal lagi yang perlu dipahami bahwa dalam Python, objek tidak pernah diedit nilainya. Jika suatu ekspresi menghasilkan nilai baru yang berbeda, maka dibuatkan objek yang baru, lalu objek yang lama dilepas dengan sedikit perubahan catatan kepemilikan.
RADIX-COUNTING SORT
Mari kita kenali suatu algoritma pengurutan yang sama sekali tidak membandingkan angka angkanya lebih besar atau lebih kecil. Wah, gimana cara?
Kita lihat dulu programnya, baru dibahas algoritmanya, atau simak
penjelasan https://youtu.be/Il45xNUHGp0
# radix-counting sort.py
from random import randint
from array import array
from time import time
def timer(fn):
def inner(*args, **kwargs):
start = time()
answer = fn(*args, **kwargs) # fn is free variable
end = time()
print(f'time elapsed {end - start:.2f} seconds')
return answer
return inner
@timer
def radix_count_sort(values, radix=256):
def last_digit():
# note: do not use log formula for this calculation
biggest = max(values)
n = 0
while True:
n += 1
if biggest // radix ** n == 0:
return n
def on_dgt_sort(current_digit: int):
nonlocal values, buffer, counter
# menggunakan dua array data bergantian
values, buffer = buffer, values # SWAP !
# reset counter, menggunakan array counter yang sama
for x in range(radix):
counter[x] = 0
# minimalkan kalkulasi di dalam loop
weight = radix ** current_digit
print(f'loop {weight=}')
for v in buffer:
idx = (v // weight) % radix
counter[idx] += 1
for i in range(1,len(counter)):
counter[i] = counter[i] + counter[i-1]
for v in reversed(buffer):
idx = (v // weight) % radix
counter[idx] -= 1
values[counter[idx]] = v
buffer = array('L', [0] * len(values))
print(f'{radix=}, digit counts:{last_digit()}, data length:{len(values):,}')
counter = array('L', [0] * radix)
for csd in range(last_digit()):
on_dgt_sort(csd)
return values
@timer
def merge(data_list):
return sorted(data_list)
print('randomise..')
data = array('L', [randint(1000, 10_000_000) for x in range(5_000_000)])
copy = data[:]
print('radix sort, start...')
data = radix_count_sort(data, 256)
print(*data[-15:])
print('merge sort, start...')
data2 = merge(copy)
print(*data2[-15:])
Algoritma ini digolongkan pada jenis pengurutan berdasarkan distribusi berbeda dengan selection sort yang berdasarkan pembandingan.
Contoh radix sort di atas mengurutkan digit per digit dimulai dari LSD digit satuan. Inti radix sort adalah mengurutkan digit per digit dengan tetap memperhatikan stability yaitu urutan awal untuk nilai yang sama tetap dipertahankan. Ketika akhirnya digit terbesar selesai diurutkan maka ditemukanlah hasilnya, sudah terurut. Dalam mengurutkan per digitnya dapat digunakan algoritma sort yang lain yang stabil, biasanya digabungkan dengan counting sort, makanya dinamakan radix-counting sort.
Dalam mengurutkan satu digit maka diperlukan hanya 10 sel array counter untuk radix desimal 10, atau tepatnya sebesar radix yang akan digunakan, 16 untuk hexadesimal, atau lainnya.(contoh di atas menggunakan radix 256 atau 1 byte)
Konsepnya begini, array counter itu indeksnya kan sudah otomatis terurut, jadi kita hanya perlu menghitung berapa banyak adanya nilai yang sama pada sel counter sesuai indeksnya, dan voila sudah terurut sebenarnya, untuk digit satuan itu, tinggal di print berapa banyak angka 0,1,2..sampai 9., sudah selesai kalau hanya satu digit. Andai kita punya sederetan angka random dari 0 sampai 999 yang posisinya acak, maka dengan counter array 1000, kita hitung per angkanya untuk setiap nilai n maka counter indeks n ditambah satu, lalu digelar dari indeks 0, print angka indeks sebanyak isi sel-nya. Jadi panjang array counter tergantung nilai paling besar dari angka acak. Dengan mengambil digit per digit maka counter dapat dibatasi sepanjang radix.
Karena angka per digit tidak mencerminkan nilai aslinya, maka perlu diulang dengan digit berikutnya, dan counter ditambahkan sedikit metoda untuk menyesuaikan.
Pertama isi counter diakumulasikan counter[i] = counter[i] + counter[i-1], sehingga pada akhir sel kita mendapatkan jumlah banyaknya ragam angka dan jika dikurangi satu maka akan menunjuk kepada indeks array nilai posisi urutannya.
Kedua, penggelaran dimulai dari akhir array nilai supaya menjaga stabilitas urutannya.
Ketiga, ambil digit saat ini dari nilai, lihat di indeks counter sesuai digit itu, kurangi satu isi selnya, maka hasilnya akan menjadi indeks array nilai, masukan nilai asli ke indeks tersebut.
Keempat, ulangi sampai nilai paling awal dari array nilai.
Kelima, ulangi proses di atas untuk digit berikutnya sampai digit terbesar dari nilai terbesar., dan selesai proses pengurutan.
Pada implementasi di atas kita melihat beberapa for..loop berurutan bukan bersusun sehingga kompleksitas waktunya adalah O(nk) yang mana k ialah jumlah digit tergantung dari nilai terbesar dan n adalah jumlah data.
Pemakaian ruang memori dihemat dengan menggunakan dua array nilai dan satu array counter. Untuk nilai input digunakan array bernama buffer sedang untuk output array bernama values. Setiap kali mengulang proses untuk digit berikut, kedua array tersebut bertukar nama. Untuk array counter prosesnya menggunakan mutasi item sehingga mencegah penggunaan array baru yang menambah beban garbage collector atau fluktuasi penggunaan memori, walaupun panjangnya tidak terlalu besar (256 x 4 bytes). Untuk menampung nilai angka acak digunakan class array long supaya membatasi ukuran per itemnya, lebih ringan memprosesnya daripada list yang fleksibel.
Untuk 5 juta data, array long menggunakan 20 juta bytes atau 4 bytes per itemnya sedangkan List menggunakan struktur 8 bytes per itemnya, 40 juta bytes.
Baik, sampai di sini dulu, terima kasih atas perhatiannya.
Salam,
Comments
Post a Comment