JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
1
Desain dan Analisis Struktur Data Non Linier Rooted Tree Dinamis Nur Ahmad Wahid, Arya Yudhi Wijaya dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia e-mail: 1,
[email protected] Abstrak— Rooted tree merupakan graf berarah memiliki tepat 1 vertex sebagai root dan semua edge yang terhubung pada tree diarahkan berlawanan dari root. Rooted tree dalam prakteknya banyak digunakan di dunia nyata. Contoh sederhana seperti organisasi file-file dalam memori komputer ke dalam sistem direktori dimana root direpresentasikan sebagai root direktori dengan semua internal vertex yang terhubung di dalamnya direpresentasikan sebagai subdirektori. Banyak permasalahan-permasalahan yang dapat ditemukan dalam pengimplementasian struktur data rooted tree dinamis. Salah satunya adalah bagaimana menarik informasi berupa jumlah bobot yang dimiliki oleh vertex yang terhubung pada suatu subtree secara tepat dan efisien dengan kondisi root yang dapat berubah-ubah. Dalam publikasi ini akan dibahas tiga pendekatan yang dapat digunakan untuk menyelesaikan masalah pada struktur data rooted tree dinamis. Dari serangkaian proses penelitian yang dilakukan, didapatkan kesimpulan bahwa permasalahan pada struktur data rooted tree dinamis dapat diselesaikan dengan kompleksitas waktu preprocessing dipengaruhi oleh banyaknya vertex secara linier dan waktu operasi tidak dipengaruhi oleh banyaknya vertex (kompleksitas konstan). Kata Kunci— Graf, struktur data, tree, LCA, pemrograman dinamis.
I. PENDAHULUAN Tree merupakan struktur data graf tak berarah yang tidak memiliki satu pun cycle. Beda halnya dengan tree pada umumnya, rooted tree yang merupakan graf berarah memiliki tepat vertex sebagai root dan semua edge yang terhubung pada tree diarahkan berlawanan dari root. Rooted tree dalam prakteknya banyak digunakan di dunia nyata. Contoh sederhana seperti organisasi file-file dalam memori komputer ke dalam sistem direktori dimana root direpresentasikan sebagai root direktori dengan semua internal vertex yang terhubung di dalamnya direpresentasikan sebagai subdirektori. Adapun yang bertindak sebagai leaves adalah file-file dan direktori kosong [1]. Banyak permasalahan-permasalahan yang dapat ditemukan dalam pengimplementasian struktur data rooted tree. Salah satunya adalah penarikan data yang dimiliki oleh setiap subtree dengan kondisi struktur tree yang dapat berubah-ubah. Dibutuhkan desain struktur data serta algoritma yang efisien baik space yang dibutuhkan maupun kecepatan akses pencariannya. Permasalahan tersebut dapat diabstraksi ke dalam bentuk
yang lebih sederhana, yaitu pada setiap vertex yang terhubung pada tree memiliki bobot masing-masing. Bagaimana menarik informasi jumlah bobot dari vertex-vertex yang terhubung pada suatu subtree secara tepat dan efisien dengan root yang dapat berubah-ubah [2].
II. ULASAN ALGORITMA A. Rangkaian Proses Ide dasar dari metode yang digunakan tidak secara eksplisit mengubah root pada rooted tree pada operasi pemindahan root, sehingga representasi rooted tree yang dibayangkan pengguna berbeda dengan representasi aslinya pada memori komputer. Metode ini bisa dilakukan dengan mamanfaatkan konsep LCA [3]. Jika root dari rooted tree saat ini adalah r, vertex yang ditanyakan jumlahan subtree-nya adalah u dan larik yang menyimpan jumlahan bobot subtree pada saat root di vertex 1 maka ada 3 kasus, yaitu: 1. 2. 3.
Jika u sama dengan r, maka cara hitungnya adalah sum[1] (sama dengan total bobot semua vertex) LCA(u, r) adalah u, maka cara hitungnya adalah sum[1] dikurangi sum[v], yang mana v adalah salah satu child dari u yang mengarah ke r. LCA(u, r) bukan u, jawabannya adalah sum[u].
Gambar 1. Flowchart rangkaian proses program
JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
Flowchart rangkaian proses program ditunjukkan pada Gambar 1. Langkah proses yang berwarna merah pada flowchart merupakan proses penyesuaian query masukan dengan 3 kasus LCA yang dijelaskan sebelumnya. B. Algoritma Path Doubling Menggunakan teknik meta – binary search [4] yang menyimpan informasi berupa parent ke - dari sebuah vertex i. Sehingga dalam proses penelusuran dapat dilakukan langkah besar selama tidak melebihi level ancestor yang dituju. Ilustrasinya dapat dilihat pada Gambar 2. Kompleksitas algoritma ini adalah . Untuk menyimpan informasi tersebut dapat digunakan pendekatan dynamic programming [5]. Fungsi rekurennya dapat dilihat pada persamaan 1 dengan merupakan parent dari vertex i dan variabel sebagai ancestor ke dari vertex i . Teknik ini biasa disebut Path Doubling atau Pointer Jumping [6]. (1) Pseudocode preprocessing algoritma Path Doubling ditunjukkan pada Gambar 3. Pseudocode proses penelusuran ancestor sampai level yang ditentukan pada algoritma Path Doubling ditunjukkan pada Gambar 4.
2
GET-ANCESTOR Input : a : depth vertex yang akan dijangkau b : indeks vertex yang lebih jauh dari root (depth lebih tinggi) Output : b (telah diperbarui) : indeks vertex ancestor dari b dengan depth yang sama dengan a 1. 2. 3. 4. 5. 6. 7.
for i ← LOG_N to 0 if D[b] – 2i ≥ a b ← dp_parent[b][i] endif endfor return b
Gambar 4. Pseudocode fungsi GET-ANCESTOR
C. Algoritma Sparse Table Dengan terlebih dahulu melakukan proses reduksi permasalahan LCA ke permasalahan RMQ [3], sekarang bagaimana menyelesaikan permasalahan RMQ, yaitu dengan menggunakan algoritma Sparse Table [3]. Algoritma Sparse Table melakukan preprocessing RMQ ke dalam sublarik yang memiliki panjang dengan menggunakan teknik dynamic programming [3]. Larik tersebut berdimensi 2, yang dimana adalah indeks dari nilai terkecil yang terdapat pada sublarik dari indeks i dengan memiliki panjang . Ilustrasinya dapat dilihat pada Gambar 5 dengan fungsi rekurennya pada persamaan 2. (2) Untuk menghitung RMQA(i, j) adalah dengan memilih 2 sublarik atau blok yang menutupi semua bagian pada blok i…j. Misalkan , maka untuk menghitung RMQA(i, j) adalah dengan menggunakan formula pada persamaan 3. Ilustrasi 2 blok yang menutup seluruh bagian interval i sampai j dapat dilihat pada Gambar 6. (3)
Gambar 2. Ilustrasi algoritma Path Doubling
PRE-PROCESS Input : Output : 1. 2. 3. 4.
set semua isi dp_parent dengan -1 for i ← 2 to N dp_parent[i][0] ← parent[i] endfor
Gambar 5. Ilustrasi sublarik algoritma Sparse Table
5. 6. 7. 8.
for i ← 1 to LOG_N for j ← 1 to N if dp_parent[j][i-1] ≠ -1 dp_parent[j][i] ← dp_parent[dp_parent[j][i-1]][i-1] 9. endif 10. endfor 11. endfor
Gambar 3. Pseudocode fungsi preprocessing algoritma Path Doubling
Gambar 6. Ilustrasi Perhitungan RMQ dengan Sparse Table
JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) PRE-PROCESS Input : Output : 1. 2. 3. 4. 5. 6. 7. 8. 9.
for i = 0 to counterEuler – 1 ST[i][0] ← i endfor
10. 11. 12. 13. 14. 15. 16. 17.
let j ← 1 while 2j ≤ counterEuler let i ← 1 while i + 2i – 1 ≤ counterEuler If EulerSeq[ST[i][j-1]]< EulerSeq[ST[i+(2 (j1) )][j-1]] ST[i][j] ← ST[i][j-1] else ST[i][j] ← ST[i+(2(j-1))][j-1] Endif i ← i + 1 Endwhile j ← j + 1 endwhile
Gambar 7. Pseudocode fungsi preprocessing algoritma Sparse Table FIND-LCA Input : i dan j : batas kiri dan kanan blok sequence Output : -
1. 2. 3. 4. 5. 6. 7.
let k ← (int) log(j - i + 1) if EulerSeq[ST[i][k]] < EulerSeq[ST[j - (2k) + 1][k]] return ST[i][k] else ST[j - (2k) + 1][k] endif
Gambar 8. Pseudocode fungsi findLCA algoritma Sparse Table
Pseudocode preprocessing dan query algoritma ini ditunjukkan pada Gambar 7 dan Gambar 8. Untuk mendapatkan child pertama dari vertex LCA tinggal mengambil isi larik dari ETS di belakang LCA . Ilustrasinya ditunjukkan pada Gambar 9.
3
D. Algoritma Khusus Permasalahan RMQ Terbatas Pada subbab ini akan dijelaskan mengenai algoritma yang dapat menyelesaikan permasalahan RMQ pada sebuah larik dengan batasan [3]. Larik dengan batasan adalah larik yang berisi bilangan yang di mana bilangan yang saling berdampingan memiliki beda tepat . Dalam hal ini larik Euler Tour Sequence yang didapatkan dari proses reduksi pada subbab 2.4 merupakan larik dengan batasan . Algoritma ini menggunakan teknik table-lookup untuk preprocessing jawaban RMQ pada sublarik dengan ukuran kecil. Langkah pertama adalah dengan membagi larik ke dalam blok-blok dengan ukuran adalah ukuran larik terbentuk adalah
( yang dimaksud disini
), sehingga banyaknya blok yang . Definisikan sebuah larik
yang berisi elemen minimum pada blok ke. Definisikan pula larik dengan ukuran yang sama yang menyimpan indeks posisi pada larik elemen minimum pada blok ke- . Selanjutnya adalah melakukan proprocessing pada larik dengan algoritma Sparse Table yang telah dijelaskan pada subbab 2.9. Algoritma pada Sparse Table memiliki kompleksitas waktu proses preprocessnya dan larik memiliki ukuran , sehingga
kompleksitas
keseluruhan proses ini adalah . Ilustrasi dari penjelasan di atas
dapat dilihat pada Gambar 10. Berikut langkah yang ditempuh untuk menghitung dengan memanfaatkan larik yang telah diproses dengan algoritma Sparse Table tadi (ilustrasi dapat dilihat pada Gambar 11): 1) Menghitung minimum elemen dari dari bloknya. 2) Menghitung minimum elemen yang blok antara blok yang terdapat di blok yang terdapat di dalamnya. 3) Menghitung minimum elemen dari sampai pada bloknya.
sampai akhir terdapat pada dalamnya dan elemen awal
Gambar 10. Ilustrasi Pembagian Blok
Gambar 9. Ilustrasi cara mendapatkan child pertama dari LCA
Gambar 11. Ilustrasi query in-block dan out-block
JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) Untuk menghitung minimum elemen yang terdapat pada blok antara blok yang terdapat di dalamnya dan blok yang terdapat di dalamnya (nomor 2) didapatkan dengan memanfaatkan larik yang telah diproses tadi dengan Sparse Table. Untuk menghitung bagian nomor 1 dan 3 (selanjutnya akan disebut in-block query, sedangkan bagian nomor 2 selanjutnya akan disebut out-block query) memerlukan waktu yang banyak jika dilakukan preprocessing di setiap bloknya dengan Sparse Table. Kompleksitasnya adalah . Kompleksitas waktu yang dimilikinya masih banyak sehingga perlu dikurangi dengan memanfaatkan keuntungan larik dengan batasan . Jika 2 larik dan memiliki nilai beda yang tetap pada setiap posisinya, contohnya dengan adalah nilai beda tetap di setiap nya, maka semua jawaban untuk RMQ akan sama untuk larik dan . Sehingga dapat dilakukan preprocess yang sama di kedua larik tersebut. Dengan demikian suatu blok dapat dinormalisasi menjadi blok yang hanya menyimpan nilai sehingga jumlah blok yang normal menjadi jauh lebih sedikit. Ilustrasi dapat dilihat pada Gambar 12. Setelah semua blok masing-masing telah didefinisikan indeks normalnya, maka sisa melakukan preprocessing RMQ dengan algoritma trivial yang pseudocode-nya ditunjukkan pada Gambar 13.
Gambar 12. Ilustrasi blok normal
BUILD-TABLE-SQRT Input : Output : 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.
for i=0 to numBlock-1 if isFinished[indexSqrtBlock[i]] = false for j=0 to sizeBlock-1 tableSqrt[indexSqrtBlock[i]][j][j] ← j endfor for j=0 to sizeBlock-1 for k=j+1 to sizeBlock-1 let a ← L[i*sizeBlock+tableSqrt[indexSqrtBlock[i]][j][k - 1]] let b ← INF if i*sizeBlock+j < 2*N-1 b ← L[i*sizeBlock+k] endif if a < b tableSqrt[indexSqrtBlock[i]][j][k] ← tableSqrt[indexSqrtBlock[i]][j][k - 1] else tableSqrt[indexSqrtBlock[i]][j][k] ← k endif endfor endfor isFinished[indexSqrtBlock[i]] ← true endif endif
Gambar 13. Pseudocode algoritma RMQ trivial pada algoritma khusus permasalahan RMQ Terbatas
4
III. HASIL UJI COBA Uji coba akan dilakukan dengan beberapa mekanisme, yaitu meliputi pengunggahan kode program yang telah dibuat ke situs penilaian daring SPOJ, uji coba kebenaran dan uji coba kinerja disertai dengan analisis kinerja serta kompleksitas waktu dan ruang program yang telah dibuat. A.
Uji Coba Melalui SPOJ Dalam uji coba ini, kode sumber dari program yang telah dibuat diunggah ke situs penilaian daring SPOJ pada soal yang berjudul Dynamically-Rooted Tree. Format masukan juga telah disesuaikan dengan yang diminta pada soal tersebut. Setelah kode sumber diunggah, situs penilaian daring SPOJ akan memberikan umpan balik. Jika hasil keluaran program sesuai dengan ketentuan pada soal, maka situs SPOJ akan menampilkan umpan balik berupa tulisan "accepted", tetapi jika sebaliknya, maka akan muncul umpan balik berupa tulisan "time limit exceeded", "wrong answer", atau "runtime error". Program dengan 3 pendekatan berbeda akan diunggah masingmasing 6 kali untuk mendapatkan waktu eksekusi rata-rata dari program yang telah dibuat. Tabel 1 menunjukkan perbandingan umpan balik situs SPOJ dari ketiga implementasi algoritma. B.
Uji Coba Kebenaran Pada uji coba ini dilakukan pengujian program dengan data masukan berupa graf rooted tree dengan jumlah vertex dan query yang sedikit. Uji coba kebenaran dilakukan untuk menguji kebenaran hasil keluaran program sesuai dengan data keluaran yang diinginkan. Pada uji coba kebenaran ini akan diuji juga metode perhitungan jumlah bobot subtree tanpa dilakukan pengubahan root pada real memori. Uji coba dilakukan dengan memberi masukan ke program dengan data masukan seperti yang ditunjukkan pada Gambar 14 (kiri). Ditunjukkan pula pada gambar tersebut data keluaran program (kanan) dengan catatan keluaran program dengan menggunakan 3 kelas berbeda adalah sama. Tabel 1. Tabel perbandingan uman balik situs penilaian daring SPOJ
Algoritma Path Doubling Sparse Table untuk permasalahan RMQ terbatas
Waktu eksekusi rata-rata
Memori
0.52 detik 0.50 detik
17 Megabyte 30 Megabyte
0.25 detik
15 Megabyte
16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 2 2 2 3 3 3 6 6 8 13 13 14 5 R 14 S 14 S 3 S 13 S 1 Gambar 14. Data masukan dan keluaran program
136 70 106 48
JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print)
5
Pada uji coba pengaruh banyaknya vertex terhadap waktu preprocessing, banyaknya vertex dibuat bervariasi antara hingga dengan rentang 5000 vertex. Waktu yang dihitung pada uji coba ini adalah waktu lamanya preprocessing struktur data rooted tree setelah masukan representasi rooted tree telah dimasukkan ke kelas. Dicatat waktu eksekusi program terhadap tiap data dalam satuan milidetik agar pengaruh banyak vertex terhadap waktu eksekusi program dapat diamati. Garfik hasil uji coba dari percobaan ketiga pendekatan yang digunakan ditunjukkan pada Gambar 17.
Gambar 15. Ilustrasi 4 query dengan root pada vertex 14
Gambar 17. Grafik pengaruh jumlah vertex terhadap waktu operasi preprocessing
Gambar 18. Grafik pengaruh jumlah vertex terhadap waktu operasi sebanyak
Gambar 16. Rooted tree dengan vertex 14 sebagai root-nya
Ilustrasi penggunaan kasus LCA sesuai data masukan dan keluaran program. Ditunjukkan pada Gambar 15 dengan angka merah di samping vertex menyatakan jumlah bobot yang dimiliki subtree dengan vertex tersebut sebagai root-nya. Ilustrasi representasi rooted tree dengan vertex 14 sebagai root-nya ditunjukkan pula pada Gambar 16 dengan angka merah di samping vertex menyatakan jumlah bobot yang dimiliki subtree dengan vertex tersebut sebagai root-nya. C.
Uji Coba Kinerja Pada uji coba ini akan dilakukan 2 macam uji coba, yaitu pengaruh banyaknya vertex terhadap waktu preprocessing dan pengaruh banyaknya vertex terhadap waktu operasi sebanyak (batasan permasalahan).
Tabel 2. Tabel pengaruh jumlah vertex preprocessing
Percobaan
Jumlah vertex
1 2 3
150000 200000 250000
terhadap waktu operasi
Waktu (milidetik) Sparse Path Table Doubling 53 142 60 error error 90 error error error
Tabel 3. Tabel pengaruh jumlah vertex terhadap waktu operasi sebanyak query
Percobaan
Jumlah vertex
1 2 3
150000 200000 250000
Waktu (milidetik) Sparse Path Table Doubling 11 78 98 error error 88 error error error
JURNAL SAINS DAN SENI POMITS Vol. 2, No. 1, (2014) ISSN: 2337-3539 (2301-9271 Print) Tabel 4. Kompleksitas keseluruhan masing-masing program
Program dengan algoritma Path Doubling Sparse Table Khusus pada Permasalahan RMQ Terbatas
Kompleksitas Waktu
Ruang
Pada uji coba pengaruh banyaknya vertex terhadap waktu operasi sebanyak , banyaknya vertex dibuat bervariasi antara hingga dengan rentang 5000 vertex. Waktu yang dihitung pada uji coba ini adalah waktu lamanya operasi (method public query dan changeRoot) struktur data rooted tree setelah masukan representasi rooted tree telah dimasukkan ke kelas. Dicatat waktu eksekusi program terhadap tiap data dalam satuan milidetik agar pengaruh banyak vertex terhadap waktu eksekusi program dapat diamati. Garfik hasil uji coba dari percobaan ketiga pendekatan yang digunakan ditunjukkan pada Gambar 18. Dilakukan pula uji coba jika jumlah masukan vertex dibuat lebih dari batas permasalahan ( ) dengan rentang yang hasilnya ditunjukkan pada Tabel 2 untuk proses preprocessing dan Tabel 3 untuk proses query. D.
Analisis Kompleksitas Pada bagian ini ditunjukkan hasil analisis kompleksitas waktu dan ruang program secara keseluruhan. Hasilnya dapat dilihat pada Tabel 4.
IV. KESIMPULAN DAN SARAN Dari hasil uji coba dan analisis yang telah dilakukan, dapat ditarik beberapa kesimpulan dari kinerja struktur data rooted tree dinamis yang implementasinya menggunakan tiga macam pendekatan. Beberapa hal tersebut adalah sebagai berikut: 1) Dengan menggunakan tiga macam pendekatan dapat menyelesaikan masalah penarikan data pada struktur data rooted tree dinamis. 2) Algoritma Path Doubling membutuhkan memori lebih sedikit dari yang dibutuhkan oleh algoritma Sparse Table, sebaliknya waktu eksekusinya lebih lambat (sesuai uji coba situs penilaian daring SPOJ walaupun pada uji coba kinerja, preprocessing Sparse Table lebih lambat). 3) Pendekatan algoritma khusus pada permasalahan RMQ terbatas lebih unggul dari keduanya baik dari aspek kebutuhan memori maupun aspek kecepatan eksekusi namun implementasinya lebih kompleks. 4) Lama waktu eksekusi preprocessing ketiga pendekatan dipengaruhi oleh banyaknya vertex secara linier baik yang memiliki kompleksitas 𝑂(𝑁) maupun 𝑂(𝑁𝑙𝑜𝑔(𝑁)). 5) Lama waktu eksekusi operasi (query dan changeRoot) ketiga pendekatan tidak dipengaruhi oleh banyaknya vertex (konstan) baik yang memiliki kompleksitas 𝑂(1) maupun 𝑂(𝑙𝑜𝑔(𝑁)). 6) Program dengan menggunakan algoritma khusus pada permasalahan RMQ terbatas unggul di kedua aspek, baik kompleksitas waktu maupun ruang.
6
Saran yang diberikan dalam pengembangan struktur data rooted tree dinamis adalah agar dapat dibuat lebih dinamis lagi dengan ditambahnya berbagai macam operasi seperti penambahan nilai bobot dengan mempertahankan kompleksitas waktu.
UCAPAN TERIMA KASIH Penulis mengucapkan puji syukur kepada Allah SWT yang melimpahkan rahmat dan hidayahnya sehingga penulis dapat menyelesaikan penelitian ini dengan lancar. Penulis juga mengucapkan terima kasih kepada Bapak Rully Soelaiman dan Bapak Arya Yudhi Wijaya yang telah membantu penulis dalam menyelesaikan penelitian ini dengan lancar. Penulis juga mengucapkan terima kasih kepada pihak-pihak lain yang turut membantu kelancaran penelitian ini.
DAFTAR PUSTAKA [1] Kenneth H. Rosen, Descrete Mathematics and Its Application, 6th ed. New York, United States of America: McGraw-Hill, 2007.
[2] (2013, June) Dynamically Rooted Tree. [Online]. HYPERLINK "http://www.spoj.com/problems/DRTREE" http://www.spoj.com/problems/DRTREE
[3] Michael A. Bender and Martin Farah-Colton, "The LCA Problem
Revisited," LATIN '00 Proceedings of the 4th Latin American Symposium on Theoretical Informatics, pp. 88-94, May 2000.
[4] Steven S. Skiena, The Algorithm Design Manual, 2nd ed. London: Springer, 2008.
[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 3rd ed. Massachusetts: The MIT Press, 2009.
[6] Michael A. Bender and Martin Farach-Colton, "The Level Ancestor
Problem simplified," Theoretical Computer Science - Latin American theorotical informatics, vol. 321, no. 1, pp. 5-12, June 2004.
