Sabtu, 18 Januari 2014

Teknik Optimisasi Konstanta

Akhir-akhir ini saya sering berlatih di SPOJ, dan seringkali sudah menggunakan algoritma optimal, tetapi tetap TLE. Akibatnya saya harus melakukan optimisasi konstanta habis-habisan hingga akhirnya mendapat AC.

Pada competitive programming, konstanta sering dianggap menjadi hal yang kecil. Karena kecil, dianggap tidak mempengaruhi performa secara keseluruhan. Memang benar, saya termasuk yang berpikiran seperti itu. Namun hal ini tidak selalu berlaku apabila konstanta yang kecil itu ada dalam jumlah yang besar. Bayangkan jika harga beras awalnya Rp 1,00 per butir, lalu tiba-tiba naik menjadi Rp 1,12 per butir. Mungkin memang kenaikannya hanya Rp 0.12, tetapi bila kita membeli 1 ton beras yang isinya ada 36.590.000 butir beras, kenaikannya menjadi Rp 4.390.800,00. Hal yang sama juga berlaku pada program, bila konstanta yang kecil itu muncul pada looping yang bisa dilakukan ratusan ribu kali, bisa saja akan mempengaruhi performa program secara signifikan.

Biasanya, Anda hanya memerlukan optimisasi konstanta pada kompetisi ACM-ICPC (biasanya bukan Jakarta) atau mengerjakan soal di online judge. Untuk kompetisi seperti OSN atau IOI, sang pembuat soal sudah menentukan time limit secara bijaksana sehingga solusi dengan perbedaan konstanta yang bisa dimaklumi tetap mendapatkan AC. Bisa jadi time limit yang ditentukan berasal dari 10 dikali waktu eksekusi solusi si pembuat soal.

Pengalaman saya dalam pemrograman terus menambah pengetahuan dalam melakukan optimisasi konstanta. Berikut ini saya jabarkan teknik-teknik yang saya ketahui, dan siapa tahu dapat membantu Anda di kemudian hari. Sebagai catatan, berkat optimisasi konstanta (dan keberuntungan) saya berhasil menyelesaikan soal Alien Abduction Again, soal ICPC Jakarta 2013 dan berkat itu tim saya (Vidina 2.0) berhasil menjadi best local team :)

Beberapa contoh optimisasi di awal merupakan teknik yang umum, sementara contoh di bagian bawah adalah teknik khusus.

Rutinitas IO harus cepat

Merupakan hal yang mendasar bagi para pengguna C++ ketika menghadapi soal yang banyaknya input/output hingga ratusan ribu. Hindari cin/cout karena jauh lebih lambat dari scanf/printf. Sebagai perbandingan, soal dengan input ratusan ribu bilangan akan mendapat TLE dengan cin, dan AC 0.002 detik dengan scanf (pengalaman pribadi). Memang ada teknik sinkronisasi sehingga cin/cout bisa menjadi sangat cepat, tetapi saran saya tetap gunakan scanf/printf karena memiliki kelebihan dalam membaca input yang bervariasi.

Dalam C++, scanf/printf bukan yang paling cepat karena masih ada gets/puts yang luar biasa cepatnya. Gunakan gets/puts terutama dalam membaca/mencetak string yang sangat panjang (ratusan ribu hingga jutaan).


Inline function dan macro

Pernahkah Anda mendengar istilah overhead dalam pemanggilan fungsi? Dalam pemrograman, pemanggilan fungsi memerlukan overhead waktu yang akan digunakan misalnya untuk passing parameter dan alokasi memori. Oleh karena itu, pemanggilan fungsi membutuhkan waktu yang sedikit lebih banyak daripada langsung menulis isi fungsi dalam program utama yang memanggilnya. Tentunya, bila fungsi sering dipanggil, overhead ini menjadi signifikan.

Solusi yang dapat digunakan pengguna C++ adalah membuat fungsi inline, atau dijadikan macro. Untuk fungsi inline, cukup tambahkan kata kunci "inline" sebelum return type dari fungsi tersebut. Seluruh fungsi yang tidak rekursif bisa dijadikan fungsi inline. Ketika fungsi dijadikan inline, compiler akan menyalin hasil kompilasi fungsi ke dalam hasil kompilasi program yang memanggilnya. Hasilnya, Anda seakan-akan menulis ulang isi fungsi ke program yang memanggilnya.

Untuk macro, konsepnya mirip seperti inline. Preprocessor C++ akan melakukan "find and replace" pada kata kunci yang ditemukan pada program, baru dilakukan kompilasi. Sama seperti inline, macro juga hanya bisa diterapkan pada fungsi non-rekursif. Biasanya, macro hanya digunakan untuk fungsi yang sederhana seperti abs(), ceil(), atau lower_bound().


Modulo dan pembagian merupakan operasi yang berat

Operasi tambah, kurang, dan kali merupakan operasi yang cukup ringan. Sementara modulo dan pembagian merupakan operasi yang berat. Kadang-kadang, soal menuntut kita melakukan modulo untuk menghitung hasilnya karena hasil akhir bisa jadi sangat besar. Sebaiknya, gunakan operasi modulo sebijaksana mungkin (jangan asal meletakkan operasi modulo di setiap akhir operasi aritmetik lainnya). Bahkan untuk beberapa kasus khusus, Anda mungkin tidak memerlukan modulo; cukup kurangi hasil akhirnya dengan nilai modulo untuk mendapatkan hasil modulonya.


Pahami berat-ringannya fungsi yang Anda eksekusi

Misalkan dalam sieve or Eratosthenes, digunakan fungsi sqrt(N) untuk mendapatkan hasil akar dari N, lalu periksa apakah nilai iterasi i saat ini masih lebih kecil dari sqrt(N). Bila ya, maka lanjutkan proses mengeleminasi seluruh kelipatan dari i.

Penggunaan sqrt pada contoh di atas sebenarnya kurang baik, karena fungsi sqrt(N) memiliki konstanta yang besar. Ketimbang begitu, simpan nilai sqrt(N) dalam suatu variabel dan setiap pemeriksaan tinggal melibatkan variabel tersebut (tidak perlu menghitung nilai sqrt(N) lagi). Bahkan, lebih baik lagi jika diimplementasikan tanpa fungsi berat seperti itu (misalnya dengan memeriksa apakah i*i < N). Contoh-contoh fungsi berat lainnya adalah fungsi trigonometri.


Integer 32 bit merupakan tipe data yang cepat dalam pemrosesannya

Tipe data bilangan bulat merupakan tipe data primitif yang lebih cepat dibandingkan bilangan riil. Selain itu, tipe data bilangan bulat 32 bit lebih cepat daripada 64 bit. Menurut informasi yang saya terima, hal ini disebabkan karena mesin-mesin masih berbasis 32 bit, sehingga komputasi 64 bit memerlukan operasi yang lebih banyak (memecahnya, menghitung, lalu menggabungkan kembali). Oleh karena itu, gunakan longint/int sebisa mungkin daripada int64/long long.


Operasi bitwise cepat seperti kilat

Operasi bitwise lebih cepat lagi dari operasi aritmetika. Hal ini disebabkan karena operasi bitwise bekerja dalam level biner, yang mana sangat disukai mesin. Bandingkan dengan operasi artimatika, yang mana mesin harus mensimulasikan operasi penjumlahan dalam level biner. Contoh implementasinya adalah menggunakan operasi >> ketimbang / dalam membagi bilangan dengan suatu bilangan pangkat dua. Biasanya hal itu dilakukan pada pembagian dengan dua (N>>1 dan N/2 maknanya sama, tetapi N>>1 lebih cepat).

Operasi bitwise juga dapat mengurangi kompleksitas secara keseluruhan. Misalkan Anda memiliki sejumlah nilai boolean, yaitu b1, b2, ..., bN (tidak lebih dari 64 buah). Lalu Anda harus melakukan negasi pada elemen ke a1, a2, ..., ak. Solusi biasa adalah dengan looping O(k) untuk melakukan negasinya. Jika Anda representasikan b1, b2, ..., bN dalam sebuah integer (misalkan A), maka operasi negasi dapat dilakukan cukup dengan melakukan xor pada A dengan mask elemen-elemen yang ingin Anda negasikan. Misalnya A = 110102, dan yang ingin dinegasikan adalah elemen ke-0, 1, dan 4. Yang perlu dilakukan cukup 110102 xor 010112. Kompleksitasnya O(1) dan sangat cepat!


Bijaksana dalam memset/fillchar

Bila Anda memiliki tabel yang ukurannya bisa sampai jutaan elemen, dan terdapat banyak kasus pada satu berkas kasus uji (multiple case), hati-hati dengan penggunaan memset. Jika kasusnya ada banyak (sampai ribuan kasus), tetapi ukurannya kecil-kecil dan kasus yang besar hanya sedikit di bagian akhir, maka banyak waktu yang terbuang dalam melakukan memset (tidak semua indeks tabel digunakan, tetapi diinisialisasi). Kompleksitas memset atau fillchar memang O(1), tetapi bila dilakukan berkali-kali pada tabel yang besar, hasilnya sangat signifikan!

Percaya tidak percaya, looping manual untuk inisialisasi tabel bisa jadi lebih cepat pada kasus seperti itu. Solusi saya untuk soal Teaching Hazard - ICPC Phuket 2013 mendapat TLE bila menggunakan memset, dan AC bisa menggunakan looping manual (perhatikan baris 122 - 125). Setelah saya periksa, bedanya sampai 100 kali lebih cepat!


Hindari rekursi, gunakan iterasi

Untuk yang ini, perbedaannya akan sangat terasa dan bisa sampai 10 kali lebih cepat. Seperti yang sudah dijelaskan sebelumnya, pemanggilan fungsi memerlukan overhead, apalagi untuk fungsi rekursif!

Perubahan dari rekursi ke bentuk iterasi biasanya dilakukan untuk optimisasi konstanta DP (dari top-down menjadi bottom-up). Untuk kasus yang jarang terjadi, algoritma DFS (flood-fill, finding SCC, finding articulation point) juga perlu dioptimisasi.

Selain untuk memperkecil konstanta, perubahan ini juga meniadakan resiko stack overflow. Sekali dayung, dua pulau terlampaui!


STL map/set memiliki konstanta yang tebal

Ketika hendak melakukan grid compression, setidaknya ada 2 cara yang sering dilakukan:
  1. Menampung seluruh kemungkinan koordinat dalam map, lalu dinomori ulang dari 1 dan dibuat pemetaannya.
  2. Menampung seluruh kemungkinan koordinat dalam array, lalu diurutkan dan di-unique. Pemetaan dilakukan dengan binary search pada array yang unik tersebut.
Secara mengejutkan, cara kedua lebih cepat dari cara pertama. Hal ini dipengaruhi oleh struktur map atau set yang menggunakan Red-Black Tree, yang mana konstantanya lebih besar daripada binary search. Beberapa soal di SPOJ hanya bisa diselesaikan bila menggunakan cara kedua daripada cara pertama.


Gunakan row major ketimbang column major untuk array multidimensi

Biasanya tabel[i][j] digunakan dengan i sebagai indeks baris dan j sebagai kolom. Hal ini memang lebih baik dilakukan, ketimbang tabel[i][j] dengan i sebagai indeks kolom dan j sebagai indeks baris. Kecepatan opsi yang pertama lebih baik dibandingkan opsi kedua!

Dengan demikian, kode berikut:
lebih baik daripada:
Mungkin Anda bertanya-tanya mengapa hal ini bisa terjadi. Penjelasan mengapa opsi pertama bisa lebih cepat memiliki kaitan dengan sistem operasi, dan akan saya coba jelaskan dengan konsep yang *mudah*. Karena array multidimensi sebenarnya dilinearisasi dan disimpan dalam sebuah blok memori yang bisa jadi besar, sistem hanya "membuka" sebagian kecilnya saja dan yang menutup kembali yang Least Recently Used (LRU). Jika yang ingin diakses berada di luar yang sedang dibuka, maka akan terjadi page fault dan bagian yang diperlukan itu akan "dibuka", "menggantikan" bagian yang sebelumnya "terbuka".

Perhatikan contoh berikut:
Row major
a b c d
e f g h
i j k l
Hasil linearisasi: a b c d e f g h i j k l
Misalkan sistem operasi hanya bisa membuka 3 elemen berurutan pada setiap waktunya (sekali lagi, hanya misalnya). Jika kita mengaksesnya secara row major, page fault hanya akan terjadi 4 kali:
  1. Saat hendak mengakses a, tidak ada yang "terbuka". Oleh karena itu terjadi page fault dan "dibuka": a b c.
  2. Saat mengakses b dan c, tidak ada masalah. Namun ketika hendak mengakses d, terjadi page fault dan kini yang "terbuka" adalah: d e f.
  3. Sama seperti sebelumnya, kali ini terjadi saat hendak mengakses g.
  4. Sama seperti sebelumnya, kali ini terjadi saat hendak mengakses j.

Bandingkan dengan:
Column major
a e i
b f j
c g k
d h l
Hasil linearisasi: a e i b f j c g k d h l
Page fault terjadi 12 kali!
  1. Saat hendak mengakses a, terjadi page fault dan "dibuka": a e i.
  2. Berikutnya saat hendak mengakses b, terjadi page fault lagi dan "dibuka": b f j.
  3. Berikutnya saat hendak mengakses c, terjadi page fault lagi dan "dibuka": c g k.
  4. Berikutnya saat hendak mengakses d, terjadi page fault lagi dan "dibuka": d h l.
  5. Berikutnya saat hendak mengakses e, terjadi page fault lagi dan "dibuka" kembali: a e i.
  6. dan seterusnya...

Jadi, karena lebih sering page fault, overhead yang ada menjadi lebih besar. Pengertian ini dapat dikembangkan untuk array yang lebih dari dua dimensi, terutama untuk DP. Kuncinya adalah tempatkan indeks yang paling sering diubah di bagian kanan, dan yang lebih jarang berubah di sebelah kiri. Hal ini akan memperkecil kemungkinan page fault!


Kurangi parameter pada rekursi

Secara mengejutkan, hal ini dapat memperkecil runtime yang cukup signifikan. Kurangi beberapa parameter yang bisa dijadikan global, atau jadikan dia passing by references. Deklarasi parameter dengan passing by value sepertinya telah menghabiskan waktu untuk mengalokasikan memori dan menyalin nilai parameternya.


Lakukan prekomputasi

Misalkan Anda memerlukan nilai dari x2 + (x+1)2 + ... + (y)2. Salah satu cara yang dapat Anda gunakan adalah menghitung nilai 12 + 22 + ... + y2, lalu kurangi dengan 12 + 22 + ... + (x-1)2. Perhitungan jumlahan itu dapat dilakukan dengan rumus deret.

Menghitung dengan rumus deret memerlukan komputasi yang lebih rumit (pemangkatan, pembagian). Untuk mempercepat, Anda dapat melakukan prekomputasi di awal dan disimpan dalam array. Tentunya hal ini dapat dilakukan bila nilai-nilai tersebut muat disimpan dalam array.


Pilih struktur data yang konstantanya ringan

Untuk menyimpan jutaan bilangan, penggunaan array lebih disarankan daripada vector (pada C++). Hal ini disebabkan karena kompleksitas push_back pada vector memiliki kompleksitas amortized O(1). Pada beberapa fase, vector memerlukan array doubling dan kompleksitasnya O(N). Oleh karena itu, total waktu yang diperlukan bila menggunakan vector lebih banyak daripada array.

Biasanya, yang lebih perlu diperhatikan adalah penggunaan struktur data untuk melayani suatu kebutuhan tertentu. Misalnya untuk mendapatkan nilai maksimum dari sebuah data stream, penggunaan heap/priority queue lebih dianjurkan daripada AVL Tree yang dimodifikasi (pencarian elemen maksimum dapat dilakukan dalam O(1)). Keduanya memang dapat melayani kebutuhan tersebut dan kompleksitasnya sama, tetapi konstanta heap lebih kecil untuk operasi tersebut. Contoh lainnya adalah penggunaan BIT vs segment tree. Bila memang BIT cukup, gunakanlah BIT.


Apakah keteracakan membantu mengurangi kompleksitas?

Kadang-kadang kita memerlukan algoritma yang sensitif terhadap urutan masukan. Ketika mengacak konfigurasinya tidak mempengaruhi kebenaran solusi, bisa jadi mengacak urutan konfigurasi masukan dapat mempercepat solusi. Misalnya pada backtracking, menurut pengalaman pribadi, saya pernah menghadapi soal backtracking yang bisa dibuat kasus buruknya dan pasti TLE. Namun ternyata mengacak urutan masukkannya tidak merubah kebenaran solusi. Kebetulan, banyaknya konfigurasi kasus buruk itu jauh lebih sedikit daripada banyaknya konfigurasi kasus rata-rata (kasus yang bisa diselesaikan dengan cepat). Oleh karena itu dengan mengacak konfigurasi, besar kemungkinan kita akan sering mendapatkan kasus rata-rata.


Menghitung banyaknya bit 1 pada integer dalam O(1)

Hal ini sering menjadi subbagian dalam algoritma, dan seringkali perlu dilakukan dengan cepat. Cara paling mudah adalah melakukan looping dan menghitung apakah bit ke-i bernilai 1. Jika ya, tambahkan jawaban dengan 1. Sayangnya solusi ini berjalan dalam O(log N), dengan N adalah integer yang ingin dihitung banyak bit 1-nya.

Cara yang lebih baik diajarkan oleh Pak Suhendry, caranya:

Perhatikan bahwa dalam setiap proses loop, sebanyak satu bit yang bernilai 1 dari x akan berkurang. Dengan demikian, kompleksitasnya adalah O(K) dengan K adalah banyaknya bit 1 pada x awalnya.

Cara yang lebih efisien adalah melakukan prekomputasi di awal. Misalnya dari 0 sampai 216-1, lalu disimpan dalam tabel bernama bit1. Untuk mengetahui banyaknya bit 1 dari N, tinggal lihat bit1[N]. Sayangnya, cara ini tidak dapat dilakukan untuk N yang besar (misalnya 20 bit). Hal ini disebabkan karena prekomputasi memerlukan waktu O(D*2D), dan memori sebanyak O(2D) dengan D adalah banyaknya bit.

Beruntungnya, kita tidak perlu menghitung seluruh kemungkinan 2D untuk D yang besar. Misalkan N bisa sampai 260, maka cukup prekomputasi sampai 216, lalu banyaknya bit 1 pada N bisa dihitung dengan:
mask = (1>>16)-1
count1(N) = bit1[N & mask] 
          + bit1[(N >> 16) & mask] 
          + bit1[(N >> 32) & mask] 
          + bit1[(N >> 48) & mask]
Intinya, N dipartisi menjadi 4 bilangan 16 bit, lalu dihitung masing-masing banyak bit 1-nya, baru dijumlahkan. Kini perhitungan dapat dilakukan dalam O(1)!


Gunakan teknik segmen bit

Saya tidak tahu apa nama teknik ini, tetapi biarlah saya namakan segmen bit.

Misalkan kita dihadapkan pada kejadian:
Diberikan dua buah sekuens dengan panjang N yang hanya terdiri dari angka 1 dan 0. Cari banyaknya posisi yang mana setidaknya salah satu dari kedua sekuens itu bernilai 1 pada posisi tersebut!

Cara sederhana adalah looping O(N). Namun sebenarnya solusi ini dapat dipercepat menjadi O(N/K), dengan K adalah konstanta mulai dari 1 sampai 64. Caranya adalah melakukan segmentasi setiap K bit dari setiap sekuens dan direpresentasikan dalam integer K bit. Hasilnya, didapatkan N/K potongan bilangan K bit. Permasalahannya selanjutnya tinggal melakukan or pada kedua potongan bilangan yang saling berkorespondensi, lalu menghitung banyaknya bit 1 yang dimilikinya. Biasanya, saya memilih K=60.

Sepengalaman saya, optimisasi ini bisa memungkinkan algoritma O(N3) dengan N sampai 1000 AC, dengan pilihan K=60 sehingga konstanta kompleksitasnya 1/60.


O(log N) untuk setiap pencarian terlalu lambat? Gunakan teknik bucketing!

Saya juga tidak tahu apa nama teknik ini, biarlah dia dinamakan teknik bucketing.

Misalkan kita dihadapkan pada kejadian: diberikan N bilangan, masing-masing bisa sampai 2 milyar. Bilangan itu datang satu per satu (tidak semuanya sekaligus). Sewaktu-waktu, bisa ada pertanyaan yang berbunyi: apakah bilangan X ada di antara N bilangan itu? Tugas Anda adalah mensimulaskan hal itu sefisien mungkin!

Kadang-kadang, solusi dengan set/map yang kompleksitasnya O(log N) per operasi tidak cukup untuk mendapatkan AC (kejam juga sang pembuat soal). Cara yang biasa saya gunakan adalah dengan melakukan bucketing, membuat K buah ember penampung. Dalam hal ini, ember tersebut adalah set. Jadi terdapat K buah set.

Misalkan bilangan Y diberikan dan perlu disimpan. Penyimpanan Y akan dilakukan di set dengan indeks (Y mod K). Demikian pula dengan pemeriksaan apakah bilangan X sudah ada atau belum, caranya tinggal periksa apakah set dengan indeks (X mod K) mengandung X atau tidak. Dengan cara ini, diharapkan setiap set memiliki ukuran yang kecil, sekitar N/K. Sehingga kompleksitas setiap operasi menjadi O(log (N/K)).

Sebagai tambahan, pilih K sebagai bilangan dua pangkat, sehingga operasi mod bisa digantikan dengan bitwise and (&).


Masih kurang cepat? Gunakan hashing!

Penggunaan hashing memang tidak selalu untuk mengoptimisasi konstanta. Namun, hal ini bisa jadi sangat berguna. Anda juga dapat menggunakan teknik open-hashing dengan lazy-deletion.


Penutup

Optimisasi konstanta biasanya jarang saya lakukan, hanya ketika merasa bahwa batas waktu terlalu ketat dan banyaknya operasi terlalu membengkak. Bila dengan algoritma yang kompleksitasnya masuk akal untuk AC tetapi mendapat TLE, berarti Anda memerlukan optimisasi konstanta. Semoga dengan tulisan ini, pengetahuan Anda akan teknik optimisasi konstanta bertambah ;)


7 komentar :

  1. Testimoni:
    Postingan yg bagus dan berguna kak William Gozali/

    Saran:
    Jika ada beberapa istilah yg sepertinya perlu sedikit diberi penjelasan tambah, sekalian diketik juga di bagian "catatan kaki" suatu postingan, di bagian paling bawah.
    Mungkin istilah-istilah yg digaris miring tsb yg perlu diberi sedikit penjelasan tambah.

    Terima kasih.

    BalasHapus
    Balasan
    1. eh typo, mksdnya dicetak miring, bukan digaris miring.

      Hapus
    2. Baik terima kasih atas masukannya :)
      Oh ya, jika ada istilah yang belum saya jelaskan, mungkin bisa tinggalkan komentar supaya bisa saya perbaiki.

      Hapus
    3. ini loh kak,

      Aku udah nyoba tanya ke temen2 TOKI 2014-2015.

      "Maksudnya fungsi sqrt(N) memiliki konstanta yang besar itu apa?"

      Tapi jawabannya masih susah saya pahami ~_~

      Hapus
    4. 1. overhead
      2. sieve or Eratosthenes
      3. grid compression
      4. Red-Black Tree
      5. page fault (ini bagian dari materi sistem operasi)
      6. backtracking
      7. teknik bucketing
      8. teknik open-hashing
      9. lazy-deletion

      Sebenarnya ini bisa dipelajari sendiri sih, tapi agar pembaca lebih mudah mengingat istilah tertentu dan cepat mencerna bacaan ini, alangkah baiknya menggunakan "catatan kaki".
      Saya pernah liat beberapa skripsi, jika ada istilah anti mainstream kadang di beri sedikit penjelasan di catatan kaki per halamannya.

      Terima kasih.

      Hapus
    5. Maksud saya seperti ini,

      juga bagus kak..

      http://kupaskode.blogspot.com/2013/12/komposisi-struktur-data-dynamic-range.html

      Hapus