1 in a million

1 juta 3D points, kurang dari satu minit (bagi 100 koordinat terhampir). Impressive. Bersembang dengan Mahadi hari itu tentang hal ini.

Algoritma aku sekarang ni memakan masa dalam 20 minit untuk run. Lambatnya kerana proses mencari titik-titik terhampir tuh memakan masa.

Ceritanya begini. Bagi setiap titik-titik, aku kena cari beberapa titik terhampir untuk tujuan analisis. Macam dalam gambar belah kiri. Sekarang ni, program yang aku guna tu guna brute-force. Maksudnya, bagi satu titik tu, dia cari jarak dengan kesemua titik-titik lain. Pastu tengok yang mana jarak paling dekat, jadilah titik-titik terhampir. Bayangkan kalau ada 20 ribu titik-titik, maka kena ulang 20 ribu kalilah (Yang mana dinamakan quadratic in time, supervisor aku point out. Aku blur jer awal-awal).kdtreeDisebabkan pengkhususan aku bukanlah nak buat benda nih (yang nih dalam Data Structure punya bidang), jadi aku cari-carilah program dalam internet. Aku dah pernah terjumpa journal berkenaan cari titik-titik terhampir nih (nearest neighbourhood). Ada satu paper nih sampai 49 mukasurat bercakap fasal nak cari titik terhampir (E Chavez et al.- Searching in Metric Spaces)

Belek-belek paper tersebut dan paper-paper lain a.k.a membuka-buka helaian sambil mengaku study tapi tengah menunggu fail cerita abis didownload (tak gitu Cik Armidala? Or in your case mendengar lagu-lagu Korea), aku dapatlah idea yang cara nak cepat cari titik-titik hampiran nih dengan membahagikan dulu ruang set kepada beberapa bahagian (seperti gambar belah kanan). Nama dia kd-tree. Jadi proses perbandingan tuh cepatlah sikit.

Maka, the hunting process begin. Sementara menunggu subuh kat Cardiff itu hari (ala-ala rajin, tapi sebenarnya kena buat sebab dok berseronok survey location di siang harinya), sempatlah terjumpa algoritma yang sorang mamat nih buat.

Nih baru lepas cuba-cuba. Less than a minute. Untuk satu juta titik. Best-best.

P.S: Sudah pukul 4 pagi di sini. Bulan penuh malam ini. Tiba-tiba terasa jiwang.

P.S 2: Okey apa sekali sekala cakap fasal study. Sejak kebelakangan ini, banyak sangat komen-komen di blog daripada orang-orang yang mendengar video-video aku di YouTube. Tiba-tiba terasa macam buat major music and mass communication di sini.


2 Responses to “1 in a million”

  1. alient mulut besar says:

    benda titik-titik yang akak suka hanyalah sambung titik bernombor yang akhirnya akan menjana illustrasi seperti seekor zirafah yang comel

  2. tra says:

    bende titik-titik yang aku suka ialah …………….

Leave a Reply

See also: