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?