Download - Pertemuan 18 CODE OPTIMIZATION
Matakuliah : T0034 / Perancangan & Analisis AlgoritmaTahun : 2008
Pertemuan 18
CODE OPTIMIZATION
Bina Nusantara
MENGAPA PERLU OPTIMISASI?• Perbedaan algoritma dapat membawa perbedaan yang
sangat besar pada kinerja sebuah program.• Optimisasi algoritma adalah membuat sebuah algoritma
dapat bekerja secara lebih optimal.• Bisa dilakukan dari tingkat yang paling sederhana hingga
tingkat yang paling sulit.• Terkadang sebuah optimisasi yang kelihatan sepele dapat
menyebabkan perbedaan yang besar ketika sebuah algoritma diimplementasikan menjadi program komputer.
[buku utama, bab 10.1]
Bina Nusantara
LEVEL BAHASA PEMROGRAMAN• Bahasa pemrograman tingkat tinggi lebih dekat
ke bahasa manusia• Bahasa pemrograman tingkat rendah lebih
dekat ke bahasa mesin
• Komputer memproses peritnah kita dalam instruksi-instruksi sederhana yang terdiri atas kode instruksi dan data.
Bina Nusantara
INSTRUKSILOAD X = load accumulator dengan isi dari memori lokasi X
STORE X = Store isi dari accumulator ke memori lokasi X
OP X, OP mungkin ADD, SUB, MPY, atau DIV.
Definisi :Suatu terjemahan dari suatu ekspressi E ke dalam suatu mesin atau bahasa assembly pada suatu mesin tertentu, adalah optimal jika dan hanya jika mempunyai jumlah instruksi yang minimal.
Bina Nusantara
OPTIMISASI BAHASA TINGKAT RENDAHMisalkan suatu ekspressi matematik: ( a+ b ) / ( c + d ) akan diterjemahkan ke bahasa assembly, ada dua macam bentuk instruksi yang dapat di buat:
LOAD a LOAD cADD b ADD dSTORE T1 STORE T1LOAD c LOAD aADD d ADD bSTORE T2 DIV T1LOAD T1DIV T2
( a ) ( b )
Dapat dilihat bahwa instruksi (a) mempunyai dua instruksi lebih panjang dari instruksi (b). Jadi instruksi (b) adalah yang optimal.
Bina Nusantara
OPTIMISASI BAHASA TINGKAT TINGGI• Berfokus pada bagaimana menyederhanakan
Fungsi Kompleksitas
• Trik dasar– Mengurangi jumlah perulangan– Meningkatkan efektivitas kondisi dalam if– Menempatkan penyaringan kondisi di lokasi yang benar– Mencari pola pikir lain untuk menyelesaikan masalah
(kembali ke dasar)
Bina Nusantara
CONTOH KASUS 1 for i=1 to 10 do 2 for j=1 to 3 do 3 A[i,j]=7 4 end for 5 end for 6 for i=1 to 3 do 7 for j=1 to 5 do 8 A[i,j]=7 9 end for10 end for
[buku utama, pseudocode 10.1]
Bina Nusantara
ANALISIS
• Terdapat redundansi
7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7
7 7 7
7 7 7
Bina Nusantara
HASIL OPTIMISASI 1 for i=1 to 10 do 2 for j=1 to 3 do 3 A[i,j]=7 4 end for 5 end for 6 for i=1 to 3 do 7 for j=4 to 5 do 8 A[i,j]=7 9 end for10 end for
[buku utama, pseudocode 10.1b]
Bina Nusantara
CONTOH KASUS 21 for i=1 to 1000000 do2 for j=1 to 560000 do3 if (i mod 2)=0 then4 display A[i,j]5 end if6 end for7 end for
1 for i=1 to 1000000 do2 if (i mod 2)=0 then3 for j=1 to 560000 do4 display A[i,j]5 end for6 end if7 end for
[buku utama, pseudocode 10.2b][buku utama, pseudocode 10.2]
Bina Nusantara
LATIHAN• Metode Binary Search adalah teknik pencarian
data tertentu di dalam sebuah array yang sudah berurut. Pembahasan Binary Search sudah diberikan di Pertemuan 10. Adakah cara untuk meningkatkan kecepatan pencarian Binary Search? Coba lakukan optimisasi pada psesudocode 5.7 atau pseudocode 5.8 di buku utama !
Bina Nusantara
REVIEW• Apa yang sudah dipahami?• Apa yang akan dibahas selanjutnya?