Terasi (bagian 3): Agregasi, Database, dan Back End API

Sejauh ini, kita berhasil mendapatkan datanya. Kini waktunya untuk menghitung statistiknya dan membuat back end API sederhana. Nantinya bisa dibuat aplikasi sederhana (entah di HTML atau Android) untuk mengambil datanya dan menampilkan grafik waktu tunggu dan waktu tempuh.

---

Agregasi Nilai Statistik

Data yang telah kita miliki adalah:

1. Daftar ketibaan suatu bus, lengkap dengan:
1. lokasi haltenya
2. halte tujuan akhirnya
3. waktu ketibaannya
2. Daftar waktu tempuh suatu bus, lengkap dengan:
1. halte awal
2. halte akhir
3. durasi

Untuk prototipe pertama, informasi statistik berikut perlu didapatkan dengan bermodalkan data mentah di atas:

1. Distribusi probabilitas dalam bentuk PDF (Probability Density Function) untuk waktu tunggu di suatu halte, ke halte tujuan, pada suatu waktu.
2. PDF untuk waktu tempuh bus antara setiap halte yang bertetanggaan.

Dari PDF, segala nilai seperti rata-rata, median, p95, dan lainnya yang nantinya dibutuhkan dapat dihitung dengan mudah. Strategi yang akan saya gunakan adalah memperkirakan PDF-nya dengan Kernel Density Estimation (KDE).

Terasi (bagian 2): Panen dan Pengolahan Data

Setelah membahas bagaimana ide dasar proyek Terasi muncul, tulisan ini akan membahas pengolahan data yang dibutuhkan.

---

Jakara Smart City API

Dengan googling sekilas, saya menemukan bahwa Jakarta Smart City memang membuka API untuk Transjakarta. Terdapat data untuk halte-halte dalam suatu koridor, koordinat halte, dan koordinat setiap bus pada saat itu juga. Saya tidak menemukan data lain yang lebih berguna, jadi diputuskanlah untuk menggunakan koordinat setiap bus pada suatu waktu.

API untuk koordinat setiap bus dapat diakses di http://202.51.116.138:8088/jsc_tj_api.php. API itu sekarang sudah tewas, tetapi sebelumnya dia akan memberikan JSON berisi koordinat setiap bus dalam format:

Saya hanya menampilkan tiga bus saja, tetapi sebenarnya ada 461 bus pada 26 Januari 2016. Sekali mengkonsumsi API itu, didapatkan data sekitar 60 kB. Untuk keperluan Terasi, saya akan mengkonsumsi API itu setiap 1 menit sekali, sehingga setiap hari didapatkan 24 * 60 berkas. Jika 1 berkas berukuran 60 kB, berarti setiap harinya saya memanen data sebesar 86,4 MB. Dalam 1 bulan, datanya akan sebesar 2,6 GB. Angka ini terlihat besar, tapi sebenarnya data JSON yang diberikan ini dapat dikompres menjadi data tabular (misal: csv) yang lebih ringkas. Karena itu saya tidak mengkhawatirkan ukuran datanya.

Dengan "snapshot" koordinat bus setiap menitnya, kita dapat mensimulasikan pergerakan bus secara cukup akurat.

---

Pemanen Data

Selanjutnya saya menuliskan program sederhana dengan Node.js untuk memanggil API tersebut setiap menitnya, lalu menyimpan JSON yang diberikan. Setiap akhir hari, data yang terkumpul dikompres menjadi .tar.gz. Kalau ditanya kenapa pakai Node.js, karena kebetulan saya sedang belajar itu.

Karena saya tidak mau menyalakan komputer sepanjang waktu, saya menyewa server melalui DigitalOcean. Dengan biaya 5 dollar AS setiap bulannya, saya mendapat server paling murah dengan spesifikasi lebih lemah dari laptop tua saya. Servernya memiliki RAM 512 MB dan hard disk 25 GB. Meskipun lemah, cukup untuk keperluan pemanenan data ini.

Untuk memastikan bahwa data terus menerus dipanen, saya membuat sistem logging sederhana. Kalau untuk alasan apapun API memberikan error atau data yang rusak, maka error akan dicatat dan dilaporkan ke channel gratisan Slack (https://slack.com/). Saya cukup memasang aplikasi Slack di hp saya, lalu setiap notifikasi error dapat segera diketahui. Untuk menjaga kesehatannya, setiap hari akan ada laporan berapa ukuran data yang dipanen hari itu juga. Jadi kalau ukuran datanya tidak normal, error bisa disampaikan juga.

Sampai saat ini, saya rasa pemanen datanya sudah bekerja. Selanjutnya perlu dipastikan bahwa data yang diberikan API ini masuk akal. Kalau misalnya posisi busnya sering tidak diperbaharui, atau koordinatnya bisa kacau, dijamin hasil akhirnya amburadul. Oleh karena itu saya terpikir untuk menulis program sederhana untuk memvisualisasikan data perjalanan bus tersebut seperti sebuah video.

---

Visualisasi

Setelah pulang kerja keesokan harinya, saya memeriksa data yang telah dipanen. Terlihat baik, karena setiap menitnya ada data dan tidak ada kerusakan data.

Lalu saya menghabiskan 2 jam berurusan dengan Java awt sambil mengingat kembali ilmu kuliah semester 1. Akhirnya berhasillah penulisan program untuk menggambarkan pergerakan bus berdasarkan API.

Hasilnya memuaskan. Berikut gambaran bus dari 00:00 sampai 23:59. Terlihat bahwa dari 00:00 sampai 03:00 pergerakan bus hanya di koridor tertentu. Masuk akal, berhubung tidak semua bus beroperasi tengah malam. Sesudah itu bus mulai ramai (jam masuk kerja), terutama sejak 05:00. Selanjutnya saya menyaring hasilnya supaya hanya menunjukkan bus dengan label koridor "1".

Video beresolusi tinggi bisa dilihat di https://youtu.be/lzyAfKbAiwc

Terasi (bagian 1): Proyek Analitik Transjakarta

Seri tulisan kali ini tidak ada hubungannya langsung dengan pemrograman kompetitif. Namun, saya menggunakan sejumlah ilmunya dalam perjalanan yang akan saya ceritakan berikut.

Setelah lulus dari perguruan tinggi, saya kerja di Cermati. Kantornya di dekat mall Central Park, Jakarta Barat. Kebetulan lokasinya sangat strategis, terdapat halte Transjakarta di dekatnya. Saya pikir untuk pergi dan pulang ke kantor menjadi sesederhana naik Transjakarta saja. Namun sebenarnya tidak sesederhana itu...

Waktu itu adalah tahun 2015. Saya tidak tahu apakah sekarang situasinya sudah membaik, tetapi kondisi lalu lintas tahun itu cukup mengenaskan. Daerah Jalan S. Parman terkenal sangat macet pada jam masuk atau pulang kantor. Awalnya saya pikir ada busway (jalur Transjakarta), yang membuat Transjakarta kebal kemacetan. Sayangnya, ternyata di Jalan S. Parman terdapat penyatuan busway dengan jalan raya yang membuat bus ikut kena macet...

Akibat dari kemacetan ini adalah:

1. Pergerakan bus menjadi lambat, sehingga...
2. Frekuensi kedatangan bus menjadi rendah, sehingga...
3. Orang yang mengantre di halte menjadi ramai, sehingga...
4. Begitu bus sampai di halte, tidak semua orang kedapatan menaiki bus, sehingga...
5. Harus menunggu kedatangan bus berikutnya, sehingga...
6. ... tekanan darah saya meningkat karena perjalanan dari rumah ke kantor menjadi lama.

Seluruh akibat itu saya rasakan setiap hari, ditambah dengan setiap kali naik TJ (Transjakarta) untuk jalan-jalan di Jakarta. Hingga suatu ketika saya muak, dan menjadi marah. Bagaimana mungkin fasilitas umum untuk masa depan beroperasi seperti ini?

Akhirnya energi amarah yang meluap-luap itu saya alirkan ke ide untuk membuat sistem yang dapat menghitung metrik-metrik Transjakarta, seperti waktu tunggu, waktu perjalanan dari halte ke halte, rata-rata kedatangan bus, dan sebagainya. Dengan metrik tersebut, saya dapat mengukur apakah untuk suatu perjalanan saya akan menggunakan Transjakarta. Apabila ternyata data menunjukkan perjalanannya akan memakan waktu lama, lebih baik saya naik ojek.

Struktur Data Dynamic Range Query

Tanpa terasa saya sudah membahas banyak struktur data dynamic range query. Tulisan ini akan menjadi rangkuman semuanya dan menjadi peta bagi kalian yang hendak mempelajarinya.

---

Technology Tree

Intermezzo:

Kalau kalian pernah bermain game berjenis Real Time Strategy (RTS), mungkin tahu tentang konsep "technology tree". Biasanya Anda akan memainkan satu peradaban yang dimulai dengan teknologi seadanya. Seiring dengan berjalannya waktu, Anda dapat melakukan riset untuk memajukan teknologi dan meningkatkan produktivitas. Ditemukannya suatu teknologi juga memungkinkan pembuatan sejumlah teknologi lain. Contohnya pada game Age of Empires, pembuatan kandang hewan akan memungkinkan dibuatnya cavalry dan pemanah berkuda.

Oke cukup dengan cerita game. Pembelajaran struktur data pun dapat digambarkan seperti sebuah technology tree. Mempelajari suatu struktur data memungkinkan Anda untuk belajar sejumlah struktur data lainnya. Berikut adalah gambarannya:

Klik untuk memperbesar gambar.

Semuanya dimulai dengan array. Dengan array polos, kita dapat melakukan apa saja walaupun secara kurang efektif. Lalu saya tidak mengikutkan keluarga struktur data linear seperti stack/queue/deque, dan juga keluarga heap.

Anak panah menunjukkan bahwa setelah mempelajari suatu konsep (struktur data/teknik), Anda dapat beranjak ke konsep yang lebih lanjut.

Petunjuk Coding: Segment Tree Lazy Propagation

Setelah menguasai penulisan kode segment tree yang melayani update sebuah elemen dan range query, kini waktunya beranjak ke operasi yang lebih sulit: range update.

Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.

---

Konsep

Lazy propagation dapat diimplementasikan ketika:

1. Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
2. Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.

Apabila kedua syarat itu dipenuhi, maka lazy propagation dapat diterapkan. Setiap range update atau query dapat dilaksanakan dalam O(log N).

Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".

Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.

Petunjuk Coding: Segment Tree

Sebenarnya tulisan ini mau difokuskan ke implementasi segment tree. Tapi karena tulisan saya sebelumnya di ristekfasilkom.com sudah musnah (hosting-annya habis), jadinya saya kembalikan back-up tulisannya ke sini.

Segment tree merupakan struktur data yang biasa dipakai untuk menjawab dynamic range
query, yaitu sejumlah operasi yang dilakukan dengan rentang yang bervariasi. Selama tidak ada penyisipan atau penghapusan elemen, segment tree hampir selalu bisa digunakan. Tulisan ini akan membahas tentang konsep struktur data ini dan cara implementasinya.

---

Permasalahan Motivasi

Diberikan sebuah array integer dan serangkaian operasi.
Sebut saja array itu adalah ar. Operasi-operasi yang diberikan bisa berupa:

• update(x, v), yang artinya mengubah isi ar[x] menjadi v.
• query(x, y), yang artinya mencari nilai minimum dari ar[x], ar[x+1], ..., ar[y].

Dengan cara naif, update dapat dilaksanakan dalam O(1). Sementara query dapat dilaksanakan dalam O(N), dengan N adalah panjang array. Tentunya cara ini kurang efisien, khususnya jika N cukup besar dan operasi yang diberikan cukup banyak.

Dengan segment tree, kita dapat melakukannya dengan lebih baik.

Strategi Belajar CP

Kalau diingat-ingat, saya menghabiskan waktu cukup lama di pemrograman kompetitif (alias Competitive Programming/CP). Mulai dari 2009 sampai dengan 2015, yang mana sesudah itu saya pensiun. Selama 7 tahun tersebut saya menghabiskan banyak waktu untuk berlatih.

Dari beberapa cara berlatih, ada yang lebih efisien atau kurang. Mungkin bisa dianggap seperti sistem "experience" atau exp pada game. Misalnya pada game pokemon, mengalahkan dragonite memberikan exp jauh lebih banyak dari magikarp. Seandainya sejak awal saya tahu cara berlatih yang paling efisien, mungkin dengan 7 tahun saya bisa lebih jago dari saya yang sekarang.

Melalui tulisan ini, saya akan berbagi informasi cara berlatih berdasarkan pengalaman saya. Cara berlatih ini tidak saling lepas, jadi bisa dikombinasikan sesuai kebutuhan. Semoga dapat membantu kalian yang sedang menempuh perjalanan menuju OSN, IOI, regional ICPC, atau ICPC world final.

---

Latihan NonKontes (UVa, SPOJ)

Saya memulai pembelajaran CP dari latihan UVa. Setiap harinya, saya memilih beberapa soal secara acak lalu dikerjakan. Biasanya saya dapat menyelesaikan 3 soal dalam sehari. Setelah mengenal SPOJ, saya mulai berlatih di sana dengan menonton papan submission, dan memilih soal yang berkode menarik.

Ciri utama dari latihan nonkontes adalah tidak adanya batas waktu dan kebebasan dalam memilih soal. Anda boleh memilih soal sendiri, dan dikerjakan dalam jangka waktu yang ditentukan sendiri pula.

Lazy Segment Tree (Bukan Lazy Propagation)

Belakangan ini saya jadi sering menulis tentang segment tree. Berhubung masih terpikirkan, saya akan terus membagikan ilmu-ilmu aneh tentang segment tree.

Yang kali ini adalah lazy segment tree, yang berbeda dengan lazy propagation. Saya pernah menghadapi soal semacam ini, seingat saya di codeforces. Namun sayangnya tidak bisa saya temukan lagi padahal sudah mengorek-ngorek submission lama.

Inti soalnya adalah:

• Terdapat sebuah array dengan M elemen, yang mana M bisa sebesar 2 milyar.
• Pada awalnya setiap elemen bernilai 0.
• Terdapat N operasi berupa:
• U x y: artinya ubah elemen array di posisi ke-x menjadi y.
• Q x y: artinya cari elemen terbesar yang berada di antara elemen ke-x dan ke-y.
• Anda diwajibkan untuk mengerjakan operasi secara online (operasi berikutnya tidak dapat dibaca sebelum operasi saat ini dikerjakan) 

Untuk menjamin soal diselesaikan secara online, si pembuat soal mengenkripsi operasi selanjutnya dengan jawaban dari operasi 'Q' yang terakhir ditanyakan (atau 0, apabila tidak ada operasi 'Q' sebelumnya).

Seandainya soal ini boleh dikerjakan secara offline, solusinya sesederhana membaca seluruh query terlebih dahulu lalu grid compression. Meskipun terdapat 2 milyar elemen, sebenarnya hanya paling banyak 2N elemen yang mungkin disebut dalam operasi-operasinya.

---

Solusi Binary Search Tree

Solusi langsung terpikirkan adalah menggunakan BST.

Cukup simpan elemen BST berupa pasangan data <indeks, nilai>. BST ini terurut berdasarkan indeks elemen. Setiap node perlu menyimpan nilai agregat berupa nilai terbesar antar elemen-elemen subtreenya. Kini seluruh operasi dapat dilakukan dalam O(log N).

Apabila Anda belum tahu apa itu BST, cek tulisan saya sebelumnya tentang treap.

---

Solusi Lazy Segment Tree

Solusi alternatifnya adalah dengan segment tree yang node-nya bersifat "lazy". Setiap node hanya dibuat apabila dia akan diakses. Nilai agregat dari segment tree ini adalah nilai terbesar yang diwakilkan oleh suatu segmen.

Pada awalnya, kita hanya memiliki sebuah node yang mencakup elemen 1 sampai dengan M. Kita tidak perlu membuat anak kiri dan kanannya untuk saat ini. 

Kemudian untuk operasi "U x y", lakukan perubahan pada elemen ke-x seperti segment tree pada umumnya. Berhubung bisa saja terdapat node yang belum dibuat, inilah waktunya untuk membuat node tersebut. Setiap kali kita mengunjungi sebuah node yang belum memiliki anak kiri dan kanan, buat kedua anak tersebut, lalu lanjutkan operasi ke salah satu anak yang bersangkutan.

Struktur Data Range Tree Bagian 2: RMQ

Tulisan ini adalah kelanjutan dari bagian pertama tentang pengenalan range tree.

Kini kita mampu menghitung banyaknya elemen di suatu daerah persegi panjang. Operasi lainnya yang sering dibutuhkan adalah pencarian nilai terbesar, terkecil, atau bahkan jumlahan elemennya. Kita akan menggunakan contoh soal berikut:

Pada suatu lahan, terdapat N titik yang mengandung sejumlah emas. Lahan ini dapat dianggap suatu bidang 2 dimensi. Titik ke-i memiliki koordinat (xi, yi), dan memiliki kandungan emas sebanyak vi kg. Tugas kita adalah menjawab sejumlah pertanyaan berupa:

"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), berapa kandungan emas terbanyak yang ada pada suatu titik di daerah tersebut?"

---

Ide Penyelesaian

Dengan ide pada tulisan sebelumnya, kita dapat membagi-bagi daerah berdasarkan sumbu x. Kemudian untuk setiap suatu rentang x, kita bagi berdasarkan sumbu y.

Untuk mendapatkan nilai terbesar di suatu daerah persegi panjang, lakukan query range tree seperti cara sebelumnya. Nilai terbesar sebenarnya sesederhana nilai terbesar dari tiap-tiap nilai terbesar di setiap daerah yang kita cari. Dengan struktur yang telah kita pelajari, pencarian nilai terbesar di suatu node range tree perlu dilakukan melalui linear search, sehingga kompleksitasnya O(N) dan kurang efisien.

Sebetulnya pencarian nilai terbesar di suatu node range tree ini mengingatkan kita pada masalah klasik, yaitu mencari nilai terbesar dari subbarisan di array alias RMQ (Range Maximum Query).

Strategi Kontes ICPC

Sepanjang berkompetisi ICPC, saya menyadari bahwa dinamika antar anggota tim penting untuk memaksimalkan performa tim. Maksimal di sini berarti berkompetisi sebaik mungkin, sehingga apapun hasil yang didapatkan, tidak ada kekecewaan. Tulisan ini akan membagikan pengalaman saya sepanjang 4 tahun berkompetisi di ACM ICPC.

Perlu diingat bahwa tulisan ini sangat subjektif, yaitu berdasarkan pengalaman saya. Yang Anda alami mungkin berbeda, dan yang saya tuliskan hanya sebagai referensi saja.

---

Komposisi Tim

Tim yang ideal adalah tim yang anggotanya saling melengkapi. Ada anggota yang mampu mengerjakan soal tipe X, ada yang mengerjakan soal tipe Y, dan sebagainya. Namun setiap anggota sebaiknya menguasai seluruh ilmu dasar.

Storm, earth, dan fire dari warcraft (https://blizzardwatch.com)

Ilmu yang setidaknya harus dimiliki setiap anggota adalah coding. Jelas bahwa setiap anggota pasti sudah bisa coding, tetapi yang saya maksud di sini adalah setiap anggota mampu menuliskan kode dengan lancar, minim bug, dan mudah dibaca anggota lainnya. Bila tim membebankan pekerjaan coding ke seorang anggota, maka ia kemungkinan besar akan jenuh, lelah, dan hanya berperan sebagai kuli. Tanpa berperan dalam berpikir mencari solusi, anggota ini bisa saja merasa tidak dihargai...