Hari kamis lalu (14/03/13), malemnya gua ketiduran di kasur tanpa lepas kacamata. Alhasil, pas gua bangun kacamata gua satu lensanya hilang. Gua udah obrak-abrik kamar gua tapi ga nemu. Jadinya gua tutup setengah kacamata gua pake sleeve warna biru biar ga pusing pas make kacamata cuma ada satu lensa. Males keluar kamar, tapi kuliah harus tetep jalan. Alhasil, gua pun menjadi chuunibyou dalam satu hari -__-. Sabtu - Minggu akhirnya ga bisa ikut Muker FUKI Fasilkom UI -__- padahal sabtu siangnya lensanya ketemu.. Yah, mungkin memang ketentuan Allah..

Tapi ga ikut Muker FUKI Fasilkom serasa gua di kosan nyampah. Ga boleh! Gua harus bales ga dateng gua dengan produktifitas! Setelah puas banting-banting modem stupidmate (nama merek asli disamarkan) gara-gara lemot ga karuan, akhirnya gua mulai mencoba menyelesaikan TUGAS 1 SDA...

Baru berhasil 100% pas hari minggu siang, dengan struktur data paling aneh yang pernah gua buat. Dan gua pengen coba ngejelasin cara gua menyelesaikan tugas tersebut, terutama melawan testcase 10 yang jahannam -__-

Tugas 1 itu suruh buat encoder dengan algoritma LZW. Yang susah itu bukan LZW-nya (soalnya algo LZW-nya dijelasin step-by-step di instruksinya), tapi mengefisiensikan kodenya karena terdapat limitasinya hanya boleh menggunakan ArrayList ataupun LinkedList! Sorting juga harus dilakukan dengan implementas sendiri! Dan dengan time limit 2 detik!



(Buat yang ga mau baca racauan gua yang ga jelas dan pengen langsung tau penyelesaian testcase 10, scroll sampe nemu tulisan bold besar "musuh berikutnya adalah testase 10!")

Pertama gua buat sederhana. Kamus dan kamus tambahan gua jadiin satu, lalu lakukan LZW alakadarnya. Hasil output bener, cuma waktunya lambat. Temen gua (sebut saja namanya Rilambang) ngepost suatu testcase random dengan panjang input 64000 karakter. Dan suatu hari di fasilkom..

Joe : "Eh, lu udah nyoba testcase dari Rilambang belom?"
Gua : "Belom, "
Joe : "Coba deh, gila gua butuh 14 detik, testcase killer banget itu"
Gua : "Oke.. " (Dengan pedenya nyoba, ngerasa "Ah, 1 detik juga bisa!")

Hasilnya.. gua butuh 51 detik.
Dafuq..

Okay, gua bingung, gua ga tau mananya yang salah. Sorting gua menggunakan counting sort. Gua cek dan emang cepet, cuma butuh waktu 0,036 s buat yang testcase rilambang. Berarti algo LZW gua lambat. Akhirnya gua coba untuk setiap konkatenasi string menggunakan StringBuilder..

Hasilnya.. 42 detik. Gua ngerasa jago, bisa motong sampe 9 detik. Gua ngerasa bego, bisa-bisanya ngerasa seneng padahal orang lain 28 detik lebih cepet dari punya gua.

Hari jumatnya keluar gradernya. Gua nyoba, nilai 0. Panik, gua salah dimana?? Ternyata gua belom ngehapus kode buat nunjukkin waktu jalan program gua, hahaha. Nilai gua jadi 70. Salah di testcase nomor 4, 9, dan 10. Testcase 9 dan 10 kena timelimit (gua 2,9s), testcase 4 salah total. Ternyata testcase 4 itu adalah file kosong. FILE KOSONG, bahkan ga ada karakter enter, sehingga input tidak pernah diberikan ke program, sehingga input == null. Oke, mudahnya, gua tambahin setelah membaca input

if (input != null) {
   //do LZW
}
//do nothing

Nilai gua jadi 80. Okay. Dari setiap orang yang gua tanyain berapa nilai yag didapatkan, kebanyakan menjawab 80. Hore! Setidaknya gua rata-rata! Gua seneng, sampe gua sadar yang lain itu salah di testcase nomor 10 dan 4. Setelah pada tau cara membenarkan testcase nomor 4, akhirnya nilai rata-rata orang-orang menjadi 90. Gua kembali di bawah rata-rata ._.

Setelah merenung lama di hari sabtu tersebut, gua baru sadar kesalahan gua. Gua loop menggunakan while (selama string masih bersisa) dan setiap akhir loop membuang satu karakter di depan input. Nah, membuang karakter di depan itu sama jeleknya kayak remove elemen di arraylist, karena perlu shifting tiap elemennya. Akhirnya gua ganti dengan loop for, dan akhirnya testcase nomor 9 gua bener!! Ye ye ye la la la la!!

Mencoba kembali testcase Rilambang.. 15s. Testcase 10 masih 2,9s

Okay, musuh berikutnya adalah testcase 10! Tebakan gua itu testcase input ekstrim, soalnya semuanya yang gua tanya pada salah karena lewat timelimit. Masalahnya adalah LZW itu encoding linear, baca input dari awal sampai akhir. O(n). Lalu di dalam algo LZW, gua make method arraylist indexOf(), yang berarti mencari elemen through array, O(n) juga. Jadinya total kompleksitas kode adalah O(n^2), lambat broo..

Gua udah nyoba banyak cara, mulai dari menggunakan StringBuffer (yang ternyata lebih lambat dari StringBuilder karena StringBuffer itu tersinkronisasi) sampe membagi dua search, ada yang binarySearch kalo mau nyari String panjangnya 1 karakter (karena yang satu karakter pasti ada di kamus awal yang sudah tersortir sebelumnya) dan ada yang seach biasa.

Lalu gua kepikiran ide yang entah datang darimana : "Gimana kalo baca Stringnya per karakter, trus buat kamusnya juga per karakter?" Gua langsung coba, ga peduli bahwa kayak gitu itu boros memori, tapi hantam aja! Dan ternyata berhasil! Testcase 10 menjadi 0,8s!!

Jadi gimana struktur datanya? Pertama, buat arraylist berisi objek kamus awal. Misalnya, inputnya LALA_LAPAR, berarti kan kamus awalnya [_, A, L, P, R]. Nah, berikutnya, misalkan gua mau nambahin kamus "LA". Cara biasa bakal nambahin di belakang array, jadinya [_, A, L, P, R, LA]. Nah, kalo gua enggak. Gua buat si L punya array anak, jadinya :

[_,A,L [A],P,R]

Trus misalnya nambah lagi kamus "LAP", gua buat supaya A di anak L punya anak lagi, yaitu P, jadinya

[_,A,L [A [P]],P,R]

Jadi kamus yang harusnya [_,A,L,P,R,LA,AL,LA_,_L,LAP,PA,AR] disulap menjadi

[_ [L], A [L , R], L [A [_, P]], P [A], R]

Nah, apa untungnya gua buat ginian? Untungnya, misalkan gua mau search LAP, gua cuma perlu searh L, trus search anak L ada A gak, trus kalo A ada, search anaknya ada P ngga, trus return indeksnya deh. Jadinya ga perlu lagi search yang awalannya bukan L (kayak PA, AL, AR) sehingga menghemat timecost! Ga tau komplesitasnya berapa, tapi yang pasti dibawah O(n^2).

Gimana cara ngekodenya?

Untuk arraynya, gua buat node khusus, misalnya gua namain class Three. Dia nyimpen data char, index, dan Arraylist anaknya. Kalo yang gua :

/**
 * Kelas khusus Three, sebagai node penyimpanan 3 tipe data : key dalam bentuk character, 
 * value dalam bentuk integer, dan ArrayList of Three.
 */
class Three{
 
 public char key;
 public int value;
 public ArrayList next;
 
 /**
  * Membangun Three baru
  *
  * @param e1 char nilai untuk key
  * @param e2 int nilai untuk value
  * @param e3 ArrayList nilai untuk ArrayList of Three
  */
 public Three(char e1, int e2, ArrayList e3) {
  this.key = e1;
  this.value = e2;
  this.next = e3;
 }
 
 /**
  * Menampilkan isi data Three dalam bentuk String
  *
  * @return string berisi data yang disimpan dalam node Three
  */
 public String toString() {
  return "( " + key + ", " + value + ", " + next.toString() + " )";
 }
}

Nah, jadi arraylist utamanya adalah array of Three (ArrayList<Three>). Jadi Kalo dilihat semua datanya, bakalan jadi gini array-nya  ([] artinya ga punya anak)

[_(1) [L(9) []], A(2) [L(7) [] , R(12) []], L(3) [A(6) [_(8) [], P(10) []]], P(4) [A(11) []], R(5) []]

Kalo digambar :

Cara addnya, baca satu-satu karakter dari string yang mau di-add. Misalkan "LAP", maka pertama cari node Three yang berisi karakter L. Ketemu, trus liat anaknya, cari yang A, nah, baru deh kasih anak ke A, yaitu P. Indeksnya gua dapet dari variabel counter yang gua taro di luar method. Nih kode add gua :

        /**
  * Menambahkan data baru ke kamus sesuai algoritma data container untuk kamus tambahan
  */
 public static boolean specialAdd (String theString, int charAt, ArrayList kamusnya) {
  
  //BASE CASE : pointer charAt sudah menunjuk karakter terakhir
  if (charAt == theString.length() - 1) {
   ArrayList newArray = new ArrayList();
   counter++;
   return kamusnya.add(new Three(theString.charAt(charAt), counter, newArray));
  }
  
  //RECURSIVE
  char current = theString.charAt(charAt);
  for (int i = 0; i < kamusnya.size(); i++) {
   Three toCheck = kamusnya.get(i);
   if (current == toCheck.key) {
    return specialAdd (theString, charAt + 1, toCheck.next);
   }
  }
  
  return false;
 }

Cara Searchnya, baca karakternya satu-satu juga. Misalkan mau cari "LAP", pertama cari L, trus cari anaknya si L ada si A ga, kalo ada, cari lagi anaknya A ada si P ga. Ternyata ada, return nilai indeks P deh. Ini kode search gua :

        /**
  * Mencari indeks data di dalam kamus sesuai data container untuk kamus tambahan
  */
 public static int specialSearch (String theString, int charAt, ArrayList kamusnya) {
  
  //IMPLICIT BASE CASE
  //RECURSIVE :
  char current = theString.charAt(charAt);
  for (int i = 0; i < kamusnya.size(); i++) {
   Three toCheck = kamusnya.get(i);
   if (current == toCheck.key && toCheck.next.size() > 0 && charAt != theString.length() - 1) 
    return specialSearch (theString, charAt + 1, toCheck.next);
   else if (current == toCheck.key) {
    if (charAt == theString.length() - 1) 
     return toCheck.value;
    else
     return -1;
   }
  }
  
  return -1;
 }

Udah, cuma segitu yang bisa gua share. Sori kalo penjelasannya seadanya dan ngebuat ga ngerti, soalnya gua emang ga jago nulis + lebih gampang ngejelasin secara langsung. Kalo mau penjelasan lanjut bisa tanya gua kok~

Semoga bermanfaat~

* Testcase Rilambang : 0,3s :3
* Tolong gunakan kode untuk referensi, bukan untuk di copy-paste untuk tugas masing-masing
* Sebenarnya gua juga belom yakin apakah ini emang cara terbaik. Gua masih ngerasa kayaknya masih ada cara yang lebih mudah
* Terima Kasih untuk dewa Cakra, ternyata Struktur Data tersebut bernama "Trie". Jadi untuk lebih jelasnya dapat di googling apa itu Trie.