beberapa saat yang lalu saya mengerjakan proyek tentang sistem embedded mikrokontroller yang menharuskan saya memasang database didalamnya (baca) setelah berhasil menaruh database diadalamnya, kemudian terbesit pertanyaan : dengan kecepatan mikro yang hanya 16 MIPS (mega instruction per seconds) bagaimana bisa mengolah data sebanyak 500 data dengan cepat. permasalahan selanjutnya ialah, database diletakkan di memeory yang lambat namun besar. kalo dipakai algoritma standar yang mancocokkan satu per satu, maka pasti perlu beberapa detik hanya untuk mencocokkan kata mana yang cocok belum lagi proses lainnya yang juga diperlukan.
ketika saya iseng-iseng bertanya ke dosen saya, "pake algoritma yang biasa saja far", saya langsung terdiam, wah masa belum ada algoritma khusus nih? sebagai informasi, saya memang kuliah di kampus IT, tapi jurusan telekomunikasi, jadi untuk programming saya ngerti tapi kalo sampai algoritma yang mendalam saya kebanyakan belum pernah mendalami.
kemudian iseng iseng saya memikirkan bagaimana saya membuat semua proses jauh lebih singkat, tiba tiba terbesit, bagaimana dengan menggunakan string table? tabel yang dimaksud bukan tabel yang berisi string, tapi tabel yang memuat index string yang masuk ke kategori tertentu, memang dalam beberapa alortinma matching biasanya beberapa data sudah dikelompokkan ke dalam kategori tertentu, namun kalo yang saya lakukan sih tidak, karena sistem yang dibuat merupakan sistem yang embedded jadinya untuk me-rearrange data agak sedikit sulit, karena harus mereset lagi semua data dalam mikro yaitu dengan re"flash"ing program atau kata lainnya install ulang program.
singkatnya seperti ini algoritmanya:
- jika baris datanya ada sejumlah N, maka perlu tabel 1xN untuk menyimpan index
- isi tabel 1xN dengan angka default 0-(N-1) yang menunjukkan default elemen dari database
- kemudian perhatikan yang terpenting, jika persebaran dan karakteristik datanya jika data yang mau di cari bersifat terurut seperti no ID atau NIM, maka carilah mulat dari karakter paling belakang, tapi kalo data yang dicari bersifat random dan memilki panjang yang berbeda seperti nama maka pencarian dapat dimulai dari karakter yang paling depan.
- pencarian dilakukan dengan mencocokkan karakter demi karakter, namun pencocokan dilakukan secara vertikal dan bukan horzantal secara umum, hal ini dilakukan agar lebih cepat. jika ditemukan karakter yang sesuai maka hal yang dilakukan adalah mengupdate tabel yang tadinya masih terurut dengan index string yang cocok "sementara" dengan string yang akan dicari
- cari sampai isi index tabel bersisa satu
keunggulan:
- jika dibandingkan dengan sistem pencarian konvensional dengan algoritma horizontal misal dengan rata-rata panjang string yang di cari misalnya L dan banyak data keseluruhan N,. dan misal data yang akan dicari terletak pada elemen paling bawah, maka dengan algoritma konvensional maka diperlukan LxN pencocokan karakter. sedangkan jika menggunakan algoritma ini maka pencocokan karakter bisa di reduksi hingga 2xN bahkan lebih sedikit tergantung dengan persebaran data. maka jika data yang akan di cari semakin random dan tingkat keragaman data semakin tinggi, maka kecepatan pencarian data akan semakin cepat pula.
Wassalamu'alaykum wr wb
Fardhady Himawan KH
Tidak ada komentar:
Posting Komentar