Salah satu rahasia kecil pemrograman komputer adalah bahwa hal ini sebenarnya cukup menyenangkan. Anda menemukan sedikit teka-teki intelektual untuk digeluti dan dipecahkan dalam perjalanan Anda membangun sesuatu yang lebih besar. Dan alih-alih membuang solusi teka-teki seperti Sudoku yang diselesaikan pada hari Sabtu, Anda bisa memasukkannya ke dalam aplikasi Anda dan menyimpannya di dalam tas trik Anda.
Saya punya beberapa contoh terbaru yang dapat memberikan gambaran tentang pengalaman ini.
Aplikasi yang sedang saya kerjakan, karena berbagai alasan, kadang-kadang harus dapat mengambil ID blok sensus - string 15 karakter - dan memetakannya ke ID daerah pemilihan yang menyertakannya - 9–12 string karakter. Departemen sensus menerbitkan informasi ini dan menyediakannya secara gratis di situs web mereka. Kami mengimpor informasi ini dan menyimpannya dalam representasi JSON/JavaScript paling sederhana yang dapat Anda bayangkan — hanya sebuah objek dengan ID blok sebagai kunci dan ID distrik pemungutan suara sebagai nilainya. Pemrosesan yang diperlukan untuk melakukan pemetaan akan memuat file JSON dan kemudian menggunakan objek tersebut untuk melakukan pemetaan dari kunci ke nilai.
File-file ini disimpan berdasarkan negara bagian, jadi untuk memilih kasus terburuk, Texas memiliki hampir satu juta blok sensus dan struktur ini hampir berukuran 30 megabita bila disimpan di disk. Dalam memori itu meluas hingga 50 MB. JSON (JavaScript Object Notation - cara untuk mengambil objek JavaScript dan meneruskannya sebagai string atau menyimpannya dalam file) bisa sangat bertele-tele sehingga terkadang bisa menjadi lebih kecil saat diimpor tetapi dalam kasus ini sebagian besar file hanya berupa string jadi sebenarnya berkembang setelah diurai dan disimpan ke dalam memori.
Pemrosesan yang memerlukan kemampuan pemetaan ini sebelumnya harus memuat sejumlah file yang lebih besar, jadi meskipun ukurannya besar, file tersebut tidak termasuk dalam daftar masalah utama. Namun seperti biasa, beberapa perubahan dan peningkatan lainnya tiba-tiba membuat biaya pengunduhan dan pemrosesan yang terkait dengan tabel pemetaan ini menjadi sesuatu yang kami pedulikan.
Sekarang lihat lagi di Texas, file JSON 30 MB itu sebenarnya hanya 4 MB ketika dikompresi, begitulah cara penyimpanan dan transmisinya. Kompresi adalah cara cepat yang baik untuk mendapatkan intuisi tentang isi informasi "sebenarnya" dari beberapa blok data. Bentuk terkompresi mungkin bukan bentuk terbaik untuk diproses, namun ini memberi Anda gambaran tentang seberapa banyak redundansi yang ada dalam data. Dalam hal ini, terdapat ton redundansi. Redundansi itu cukup jelas jika Anda memikirkan kontennya. Setiap daerah pemilihan terdiri dari sekitar 65 blok sensus, sehingga setiap nilai (ID daerah pemilihan yang terdiri dari 9 hingga 12 karakter) diulang rata-rata sebanyak 65 kali. ID blok sebenarnya dalam bentuk yang sangat terstruktur di mana 2 karakter pertama adalah ID negara bagian (jadi sama untuk semua nilai dalam file yang disusun berdasarkan negara bagian), 3 karakter berikutnya adalah ID daerah, lalu saluran sensus, grup blok sensus dan terakhir nomor blok individual.
Mengingat semua redundansi ini, bagi saya sepertinya kita bisa menghasilkan struktur data yang jauh lebih padat yang dapat disimpan, dikirim, dimuat, dan digunakan secara langsung dalam representasi padat ini tanpa harus meledakkannya di memori. Saya baru-baru ini menjadi penggemar pemrograman JavaScript ketika perlu mempercepat atau mengurangi penggunaan memori (seringkali hal yang sama) untuk mengidentifikasi di mana representasi data JavaScript yang naif terlalu membengkak dan sebagai gantinya menggunakan representasi biner yang ringkas. Mungkin itu akar C/C++ saya.
Dalam hal ini, saya memiliki dua area untuk fokus: cara menyimpan nilai dan cara menyimpan kunci. Karena saya tahu nilainya diduplikasi rata-rata 65 kali, solusi sepele adalah dengan menyimpan salinan semua string unik dan menyimpan referensi ke string unik daripada string literal (kompiler dan bahasa sering melakukan ini secara otomatis secara internal untuk beberapa bagian dari program Anda). Saya pikir saya bisa melakukan sedikit lebih baik karena nilai-nilai juga memiliki banyak redundansi internal - banyak nilai-nilai berbagi bagian pertama yang sama dan kemudian banyak nilai-nilai memiliki beberapa karakter pembeda terakhir yang sama. Solusi sederhananya adalah dengan memecah string menjadi dua bagian (secara dinamis) dan menemukan pemisahan yang meminimalkan penyimpanan string. Ini pada dasarnya adalah perkiraan dari apa yang dilakukan algoritma kompresi umum (temukan urutan bersama dan kemudian rujuk secara kompak).
Untuk kunci, ketika Anda memiliki redundansi dalam jumlah besar di ruang kunci Anda, sebuah trie adalah pilihan yang baik. Pengkodean ini sebagian besar tentang merancang cara mengemasnya ke dalam satu blok data, menggunakan offset dari awal buffer daripada pointer untuk menelusuri struktur data. Seperti biasa ketika Anda mulai bermain-main dengan memori dengan cara yang rumit, ini memerlukan sedikit pengujian dan debugging agar dapat berfungsi.
Saya cukup senang dengan hasil akhirnya. File Texas tersebut berakhir sebagai buffer kompak sebesar 2,7 MB yang dapat langsung dimuat ke dalam memori sebagai satu blok dan digunakan tanpa transformasi lebih lanjut. Ini dikompresi menjadi kurang dari 1 MB untuk penyimpanan dan transmisi (yang menyatakan bahwa ada lebih banyak ruang untuk perbaikan dalam solusi saya). Namun saya sudah mengalami peningkatan 20X lipat dalam penggunaan memori dan peningkatan signifikan dalam penyimpanan dan transmisi, jadi saya berhenti di situ.
Ini adalah masalah kecil yang menyenangkan. Ini terisolasi dengan baik dan mudah dideskripsikan sehingga saya tidak perlu menghabiskan banyak waktu untuk masalah integrasi dan pengujian yang rumit serta penerapan yang rumit. Saya dapat menggunakan intuisi dari pemrograman seumur hidup dan juga memerlukan sedikit ketelitian untuk melakukannya dengan benar. Dan kemudian itu benar-benar berhasil dan memecahkan masalah tersebut.
Saya akan mengatakan bahwa masalah umum “kamus kompak” (yang merupakan kasus khusus) adalah masalah yang telah dipelajari dengan baik sehingga saya merasa sedikit bersalah menulis sesuatu dari awal. Tentunya ada sesuatu yang bisa saya ambil dari rak? Pencarian tidak menemukan apa pun jadi saya mendapat keuntungan karena sudah pensiun; Saya bisa menekan rasa bersalah dan bersenang-senang memecahkan masalah.
Contoh kedua saya sedikit berbeda. Dalam hal ini, menyenangkan mempelajari sesuatu yang baru dan kemudian menerapkannya secara efektif.
Saya mencoba memecahkan tiga masalah yang ternyata berhubungan dengan cara yang mengejutkan. Inti dari aplikasi kami memuat dan menampilkan bentuk daerah pemilihan. Daerah pemilihan dibuat dari bentuk blok sensus yang mendasarinya. Memori yang diperlukan untuk menyimpan dan memproses bentuk-bentuk ini pada akhirnya memiliki pengaruh besar pada kinerja kami secara keseluruhan.
Cara paling mendasar untuk meningkatkan kinerja adalah dengan mengambil bentuk resolusi tinggi yang disediakan oleh departemen sensus dan menyederhanakannya dengan menghilangkan poin. Ini membantu di mana pun (dalam penggunaan memori dan di setiap tahap pemrosesan) sehingga merupakan hal yang jelas untuk menjadi fokus. Poin tambahan tidak menimbulkan perbedaan visual saat ditampilkan di layar komputer atau tidak menimbulkan perbedaan efektif karena tidak mengubah cara pengguna berinteraksi dengan aplikasi. Bentuk-bentuk sensus yang mendasarinya perlu membedakan apakah sebuah rumah berada dalam satu blok sensus atau yang lain, namun untuk tujuan kami, perkiraan mengenai hal tersebut sudah cukup karena tidak ada data kami yang lain (sensus dan pemilu) yang tersedia pada resolusi tersebut.
Jadi penyederhanaan bentuk adalah masalah pertama kita.
Masalah kedua adalah bagaimana menggabungkan sekumpulan bentuk menjadi satu bentuk atau lebih umum lagi “penyatuan poligon”. Inti masalah yang kita hadapi adalah mengambil serangkaian bentuk daerah pemilihan dan menggabungkannya menjadi satu bentuk kongres (atau legislatif negara bagian). Penyatuan poligon adalah masalah yang banyak dipelajari dalam grafik komputer, namun solusi umumnya membutuhkan memori dan pemrosesan yang intensif dan ketika kami mengintegrasikan solusi sumber terbuka ke dalam aplikasi kami, hal tersebut memberikan beban yang signifikan pada kinerja interaktif aplikasi. Saya harus membangun mekanisme pemotongan kerja asinkron yang kompleks di atasnya untuk mencegahnya mengunci aplikasi kita selama beberapa detik.
Masalah ketiga adalah bagaimana menentukan apakah dua bentuk berdekatan. Ini adalah inti dari cara kami menganalisis rencana pemekaran wilayah. Dalam aplikasi kita, ini terjadi “offline” untuk menghasilkan grafik kedekatan. Hal ini tidak perlu terlalu cepat namun pada awalnya telah diselesaikan dengan seperangkat alat yang terpisah dari rangkaian alat inti kami sehingga kami memiliki motivasi untuk mencoba menyatukannya.
Ada banyak algoritma penyederhanaan yang dapat dipilih, namun tantangan tambahan dalam kasus kita adalah kita memiliki sekumpulan bentuk yang kita gambar bersama pada suatu permukaan. Bentuknya menutupi permukaan dan saat Anda menyederhanakannya, Anda dapat mengalami dua masalah terkait jika Anda membuat keputusan penyederhanaan yang berbeda untuk dua bentuk yang terletak bersebelahan. Pengambilan keputusan yang berbeda dapat dilakukan dengan mudah karena satu bentuk mungkin memiliki satu garis bersambung sementara mungkin ada beberapa bentuk di sisi lain yang membatasi garis tersebut. Mempertahankan integritas bentuk-bentuk yang lebih kecil berarti mempertahankan lebih banyak titik, sedangkan bentuk yang lebih besar dapat menyederhanakan dan menghilangkan titik-titik tersebut. Saat Anda membuat keputusan penyederhanaan yang berbeda, Anda akan meninggalkan lubang di peta saat Anda menggambar bentuk yang berdekatan, atau Anda memiliki bentuk yang tumpang tindih dan ini menyebabkan anomali visual saat Anda mengisi bentuk dengan opacity parsial (karena area yang tumpang tindih digambar dua kali dan tampak lebih gelap ).
Kesenjangan juga menyebabkan masalah ketika Anda ingin menggabungkan bentuk (masalah gabungan poligon yang saya sebutkan di atas) karena Anda akhirnya menghasilkan bentuk dengan banyak lubang kecil yang tidak wajar yang sebenarnya tidak ada dalam data sebenarnya. Hal ini membuat pemrosesan menjadi lebih mahal serta menimbulkan anomali visual dan analitik.
Saat meneliti ini, saya menemukan perpustakaan TopoJSON yang ditulis oleh Mike Bostock. Mike cukup terkenal di komunitas visualisasi, sebelumnya melakukan karya inovatif di New York Times dan salah satu penulis perpustakaan visualisasi sumber terbuka yang penting, d3.js. Menyelidiki di sinilah saya belajar sesuatu yang baru.
Perpustakaan TopoJSON mengambil pendekatan berbeda terhadap masalah yang saya hadapi. Pemahaman intinya adalah ketika Anda memiliki serangkaian bentuk seperti garis besar negara bagian AS atau daerah pemilihan di suatu negara bagian, bentuk-bentuk ini sebenarnya memiliki karakteristik penting dalam membagi permukaan — bentuk-bentuk tersebut tidak tumpang tindih dan menutupi seluruh wilayah. bagian dari permukaan yang Anda pedulikan. Anda benar-benar memiliki topologi (sesuai dengan nama paketnya) dan poligonnya berbagi segmen garis atau busur dari topologi ini.
Wawasan intinya adalah bahwa alih-alih menganggap data Anda sebagai sekumpulan bentuk, Anda sebenarnya memiliki kumpulan busur topologi yang membagi permukaan Anda. Ini akhirnya menjadi kunci untuk proses selanjutnya. Ini sangat keren!
Pola terobosan ini sering terulang. Anda memiliki beberapa masalah umum yang “secara teoritis sulit” tetapi dengan mengidentifikasi wawasan utama, Anda dapat memecahkan masalah lain yang lebih sederhana dengan cara yang menghilangkan kompleksitas dengan kinerja yang jauh lebih baik.
Tahap pemrosesan pertama adalah mengambil poligon dan membaginya menjadi busur yang dipecah pada titik perpotongan poligon. Kemudian Anda menghilangkan duplikat busur dengan mengidentifikasi semua poligon yang berbagi busur dan menjadikannya referensi busur yang sama.
Dengan representasi ini - setiap poligon dideskripsikan sebagai himpunan yang diambil dari kumpulan busur bersama - tantangan utama yang saya jelaskan di atas menjadi jelas.
Sekarang ketika Anda menyederhanakan, Anda menyederhanakan pada rincian dari busur bersama ini. Hal ini secara otomatis menjamin bahwa dua poligon yang berbagi tepi akan membuat keputusan penyederhanaan yang sama pada kedua sisi tepi. Tepi tersebut ditentukan oleh busur bersama yang disederhanakan.
Masalah serikat pekerja menjadi lebih mudah. Mengingat kumpulan poligon yang dideskripsikan sebagai sekumpulan busur, Anda cukup menghapus busur apa pun yang direferensikan oleh lebih dari satu poligon. Busur yang tersisa menggambarkan batas bentuk gabungan (ada beberapa kehalusan untuk menangani bentuk dan lubang yang terputus-putus saat merekonstruksi bentuk akhir).
Masalah kedekatan juga sepele dalam representasi ini - dua bentuk saling berdekatan jika keduanya berbagi busur.
Hal lain yang menurut saya luar biasa adalah semua fungsi ini (dan fitur lain yang saya lewati) diimplementasikan dalam beberapa ratus baris kode. Sebuah karya yang sangat rapi. Saya lebih akrab dengan basis kode seperti Microsoft Office di mana Anda mungkin memiliki 100-an ribu baris kode yang hanya berhubungan dengan salin/tempel (yang sejujurnya, sebenarnya merupakan masalah yang rumit secara semantik — izinkan saya memberi tahu Anda tentang salin dan tempel dalam HTML tabel beberapa waktu).
Saya mendapat kesempatan untuk menyelami lebih dalam bagian kode ini karena segala sesuatunya tidak “berfungsi”. Saya pribadi merasa sulit untuk membaca dan memahami sepotong kode jika saya tidak menggali lebih dalam untuk mencoba memperbaiki bug atau memperluasnya dengan cara tertentu. Saya hanya tidak memiliki kegigihan untuk memberikan perhatian yang diperlukan jika saya tidak berusaha mencapai tujuan yang jelas.
Dalam hal ini, ada beberapa masalah yang perlu diatasi sebelum kami dapat menggunakannya di aplikasi kami, jadi saya mendapatkan apresiasi yang lebih dalam atas pekerjaan ini serta kepuasan tambahan dalam memecahkan masalah yang saya temui selama ini.
Tantangan penyederhanaan pada dasarnya adalah kebalikan dari penyederhanaan pada rincian poligon. Keputusan penyederhanaan yang sama dibuat untuk dua poligon yang mempunyai sisi yang sama, namun keputusan yang tidak konsisten dapat dibuat untuk sisi yang berbeda dari poligon yang sama. Hasilnya adalah sebuah poligon yang bersilangan dengan sendirinya. Hal ini biasanya hanya terjadi pada bentuk belokan yang sempit, misalnya blok sensus yang dibuat untuk menutupi jalur sungai atau aliran sungai. Sayangnya, hasil dari poligon yang bersilangan sendiri ini adalah anomali visual dan pemrosesan yang ingin saya hindari!
Hal ini memberi saya kesempatan untuk mendalami lebih dalam cara kerja penyederhanaan di dalam TopoJSON. Perpustakaan memperlakukan penyederhanaan sebagai proses dua langkah. Langkah pertama adalah proses yang dapat dikonfigurasi yang menghitung bobot untuk setiap titik, paling umum dengan menghitung luas segitiga yang dibentuk oleh titik tersebut dengan titik-titik yang berdekatan. Anda dapat menganggap luas segitiga tersebut sebagai ukuran pentingnya titik tersebut dalam menunjukkan jalur garis yang sebenarnya. Tahap kedua adalah menentukan beberapa batas bobot dan menghilangkan titik-titik yang berada di bawahnya (tetapi selalu menjaga titik-titik kunci yang menandai titik-titik perpotongan poligon).
Pendekatan yang saya ambil adalah pendekatan yang berulang-ulang. Saya tahu bahwa jika saya mempertahankan semua poinnya, saya jelas akan memiliki sekumpulan bentuk yang terbentuk dengan baik. Jadi, saya akan menjalankan proses penyederhanaan, mengidentifikasi bentuk-bentuk yang salah dan secara bertahap meningkatkan “bobot” titik-titik di sepanjang busur yang direferensikan oleh poligon-poligon yang merosot tersebut. Hal ini dimungkinkan dan cukup efisien karena bobot secara eksplisit diekspos sebagai keluaran dari tahap pertama proses penyederhanaan. Pada awalnya, saya tidak yakin hal ini akan menghasilkan penyederhanaan yang memadai, namun dalam praktiknya hal ini berhasil dengan baik. Fakta bahwa perpustakaan telah mengungkap tahap peralihan ini daripada memperlakukan seluruh proses sebagai kotak hitam menjadikan hal ini cukup mudah.
Proses pengembangannya mengalami beberapa putaran dan putaran. Saya akan memproses puluhan juta bentuk yang mencakup AS dan beberapa ratus akan menyulitkan saya. Ada apa dengan bentuk-bentuk ini? Jadi saya akan melakukan perjalanan ke suatu tempat di sepanjang Pelabuhan Boston di mana sebagian besar bentuknya berbentuk persegi panjang dengan jari-jari panjang dan tipis menutupi dermaga. Atau serangkaian bentuk di Colorado yang digambar dengan cermat oleh ahli geografi untuk menutupi aliran sungai yang sempit dan berkelok-kelok. Ke Minnesota, yang menggunakan lebih banyak bentuk daripada yang Anda duga, gambarlah dengan hati-hati di seluruh perairannya. Tanah sepuluh ribu danau. Saya harus menemukan bug umum dengan algoritma penggabungan TopoJSON ketika berhadapan dengan poligon dengan lubang yang dapat disentuh sendiri (pikirkan angka delapan). Mengapa hal ini hanya terjadi beberapa lusin kali di seluruh Amerika? Dan kemudian saya melihat serangkaian lubang - untaian mutiara - yang digambar dengan hati-hati di sekitar barisan pulau di tengah sungai.
Masalah kedua adalah representasi TopoJSON yang digunakan untuk titik dan urutan garis konsisten dengan paket dan format JavaScript lainnya untuk pemrosesan geografis (pada dasarnya sebuah titik diwakili oleh larik dua elemen dan urutan garis direpresentasikan sebagai larik titik) tetapi tidak memori sangat tidak efisien. Pemrogram C menganggap array sebagai struktur data yang paling sederhana dan ringkas, namun JavaScript memperlakukan array sebagai bentuk khusus dari objek umum atau tabel hash, hanya dengan kunci string khusus dalam bentuk “0”, “1”, dll. Hasilnya adalah representasi urutan titik/garis sederhana menggunakan banyak memori dan sebenarnya mendominasi penggunaan memori kita. Hal ini benar meskipun faktanya TopoJSON dimulai dengan kemenangan besar hampir 50% dibandingkan format yang diatur berdasarkan poligon dengan hanya menyandikan titik pada edge bersama satu kali.
Saya sebelumnya telah membuat representasi yang dikemas yang pada dasarnya menyimpan semua titik untuk serangkaian bentuk kompleks dalam satu buffer biner yang memberi saya peningkatan dua kali lipat dalam penggunaan memori (Saya suka JavaScript tetapi itu mengejutkan saya betapa buruknya representasi naif itu). Saya ingin melihat apakah saya dapat menerapkan peningkatan yang sama pada paket TopoJSON.
Di sinilah ukuran keseluruhan paket yang kecil (dalam baris kode) serta desainnya yang bersih sangat membantu. Saya dapat mengintegrasikan format paket hanya dengan beberapa lusin baris kode tambahan (dan kode yang ada hanya perlu diubah di beberapa tempat). Lebih baik lagi, pemrosesan inti yang perlu saya lakukan menggunakan pustaka TopoJSON, penggabungan, dapat dilakukan langsung dari representasi yang dikemas. Pendekatan sebelumnya telah membuat poligon tetap dikemas tetapi perlu membongkar koordinatnya agar dapat meneruskannya ke perpustakaan yang kami gunakan untuk penyatuan poligon.
Ketika akhirnya terintegrasi, pekerjaan yang telah selesai mengurangi penggunaan memori aplikasi kami sebesar 100 megabyte dan pada dasarnya menghilangkan masalah yang merupakan bagian paling intensif komputasi dan memori dari aplikasi interaktif kami. Dan sepanjang perjalanan saya belajar tentang teknologi yang menarik dan menjelajahi beberapa keanehan geografi AS. Apanya yang seru!
