Tabel pencarian

Dalam ilmu komputer, tabel pencarian (bahasa Inggris: lookup table) adalah larik yang menggantikan perhitungan saat berjalan dengan operasi pengindeksan larik sederhana. Waktu yang terpotong cukup signifikan karena mengambil nilai dari memori sering lebih cepat daripada komputasi yang berat atau operasi masukan/keluaran.[1] Tabel ini dapat dihitung sebelumnya dan disimpan secara statis dalam program, dihitung sebagai tahap awal inisialisasi program, atau bahkan disimpan dalam perangkat keras untuk platform khusus tertentu.

Sejarah

Tabel logaritma umum dalam buku referensi Abramowitz and Stegun.

Sebelum penemuan komputer, tabel pencarian dipakai untuk mempercepat laju hitung dengan tangan (manual) dalam perhitungan rumit, seperti trigonometri, logaritma, dan fungsi statistika.[2]

Pada zaman India kuno (499 SM), Aryabhata membuat salah satu tabel sinus pertama yang dikodekan dalam sistem bilangan Sanskerta. Pada 493 SM, Victorius dari Aquitaine menulis tabel perkalian 98 kolom (dalam angka Romawi) yang berisi hasil perkalian antara tiap bilangan dari dua sampai 50 dan "bilangan yang dimulai dari seribu dan turun tiap ratus hingga seratus, lalu turun tiap puluh hingga sepuluh, lalu turun hingga satu, lalu pecahan hingga 1/144".[3] Saat ini, para siswa diajari tabel perkalian untuk mempercepat perhitungan perkalian dasar.

Pada awal sejarah komputer, operasi masukan/keluaran cukup pelan, bahkan terhadap kecepatan prosesor saat itu, sehingga operasi baca yang mahal dikurangi dengan tembolok manual berupa tabel pencarian statis atau larik praambil dinamis yang berisi item data yang sering muncul. Meski tembolok tingkat sistem sudah mengaturnya secara otomatis, tabel pencarian dalam aplikasi masih meningkatkan kinerja untuk item data yang jarang, bahkan tidak pernah, berubah.

Tabel pencarian adalah salah satu fungsi pertama yang diimplementasikan dalam lembar sebar komputer. VisiCalc (1979) memiliki fungsi LOOKUP di antara dua puluh fungsi pertamanya.[4] Fungsi ini juga diikuti aplikasi lembar sebar selanjutnya, seperti Microsoft Excel, dan dilengkapi fungsi khusus, VLOOKUP dan HLOOKUP, untuk menyederhanakan pencarian dalam tabel vertikal dan horizontal.

Contoh

Contoh yang sering dipakai adalah perhitungan trigonometri, misal hasil fungsi sinus. Perhitungan fungsi trigonometri cukup berat. Perhitungan fungsi trigonometri dapat dilakukan pada awal dan disimpan dalam tabel pencarian. Untuk fungsi dengan satu parameter, larik dapat disusun dalam satu dimensi. Untuk fungsi dengan dua parameter, larik dapat dua dimensi yang dipakai. Untuk nilai di antaranya, dapat dipakai interpolasi.

Tabel pencarian dalam pengolahan citra

Peta warna viridis[5]

Nilai	R	G	B	Warna
0	68	1	84
1	68	2	86
⁞	⁞			⁞
84	49	103	142
85	49	104	142
⁞	⁞			⁞
169	52	182	121
170	53	183	121
⁞	⁞			⁞
254	251	231	35
255	253	231	37

Dalam aplikasi analisis data, seperti pengolahan citra digital, tabel pencarian (LUT) dipakai untuk mengubah data masukan ke dalam format keluaran yang lebih diinginkan. Misalnya, citra derajat keabuan planet Saturnus diubah mencari citra warna untuk menegaskan perbedaan cincin-cincinnya.

LUT (atau 3DLUT) berisi nilai keluaran untuk tiap indeks. Misalnya, LUT yang sering dijumpai (disebut peta warna atau palet) dipakai untuk menentukan warna ketika menampilkan citra yang berisi intensitas (mentah).

Perhitungan fungsi sinus

Kebanyakan komputer hanya melakukan operasi aritmetika dasar dan tidak dapat langsung menghitung sinus suatu nilai secara langsung. Sebagai gantinya, algoritme CORDIC atau rumus yang rumit seperti deret Taylor berikut dipakai untuk menghitung sinus dengan presisi yang tinggi.

${\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$ (untuk x di sekitar 0)

Namun, perhitungan tersebut bisa membutuhkan waktu yang lama, terlebih pada prosesor lambat, dan ada banyak aplikasi, biasanya grafika komputer, yang menggunakan ribuan perhitungan sinus tiap detiknya. Penyelesaian yang umum dipakai adalah pembuatan tabel pencarian yang berisi hasil sinus dari nilai-nilai dalam rentang tertentu. Ketika dibutuhkan, diambil hasil sinus dari nilai yang mendekati. Cara ini cukup dekat dengan nilai aslinya karena fungsi sinus adalah fungsi kontinu dengan gradien yang terbatas (bounded). Contohnya sebagai berikut.

misalkan tabel_sinus adalah larik berindeks [-1000, 1000]
untuk tiap indeks x dalam tabel_sinus,
    tabel_sinus[x] ← sin(x × pi / 1000)

fungsi cari_sin(x)
    kembalikan tabel_sinus[bulatkan(x × 1000 / pi)]

Interpolasi linear untuk fungsi sinus

Sayangnya, tabel itu butuh ruang yang cukup banyak. Kita bisa memakai sampel yang lebih sedikit. Namun, presisinya akan lebih buruk secara signifikan. Salah satu penyelesaian yang baik adalah interpolasi linear yang membuat garis antara dua nilai pada tabel dan mengambil jawabannya dari garis tersebut. Cara ini masih cukup cepat untuk dihitung dan lebih akurat untuk fungsi halus seperti fungsi sinus. Contohnya sebagai berikut.

fungsi cari_sin(x)
    x1 ← ⌊x × 1000 / pi⌋
    y1 ← tabel_sinus[x1]
    y2 ← tabel_sinus[x1 + 1]
    kembalikan y1 + (y2 - y1) × (x × 1000 / pi - x1)

Cara lain yang memakai seperempat ruang, tetapi butuh tambahan operasi, menggunakan hubungan antara sinus dan kosinus serta aturan simetrinya. Pada kasus ini, tabel pencarian dihitung dengan fungsi sinus untuk kuadran I. Ketika butuh hasil fungsi suatu nilai, kita menentukan posisinya dalam kuadran dan mengembalikan hasil yang sesuai. Untuk kosinus dan tangen, dapat menggunakan sifat-sifat trigonometri.

${\displaystyle \operatorname {cos} (x)=\operatorname {sin} \left(x+{\frac {\pi }{2}}\right)}$

${\displaystyle \operatorname {tan} (x)={\frac {\operatorname {sin} (x)}{\operatorname {cos} (x)}}}$

Dalam implementasinya, hati-hati ketika nilai cos(x) sama dengan nol.

misalkan tabel_sinus adalah larik berindeks [0, 91]
fungsi buat_tabel()
    untuk x dari 0 hingga (360 / 4) + 1,
        tabel_sinus[x] ← sin(2 × pi × x / 360)

fungsi cari_sin(x)
    x ← x mod 360
    y ← x mod 90
    jika x <  90, kembalikan  tabel_sinus[     y]
    jika x < 180, kembalikan  tabel_sinus[90 - y]
    jika x < 270, kembalikan -tabel_sinus[     y]
                  kembalikan -tabel_sinus[90 - y]

fungsi cari_cos(x)
    kembalikan cari_sin(x + 90)

fungsi cari_tan(x)
    kembalikan cari_sin(x) / cari_cos(x)

Referensi

1. McNamee, Paul. "Automated Memoization in C++". pmcnamee.net. 
2. Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, ed. (2003). The History of Mathematical Tables: From Sumer to Spreadsheets. Oxford University Press. 
3. Maher, David. W. J.; John F. Makowski (2001). "Literary Evidence for Roman Arithmetic with Fractions". Classical Philology. 96 (4): 376–399. 
4. MrExcel East (31 Maret 2012). "Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!". 
5. Berkeley Institute for Data Science. "colormap/colormaps.py at master · BIDS/colormap". GitHub. Diakses tanggal 14 November 2020. 

Pranala luar

• (Inggris) Tabel pencarian cepat dengan karakter masukan sebagai indeks untuk tabel percabangan
• (Inggris) Art of Assembly: Calculation via Table Lookups
• (Inggris) Bit Twiddling Hacks (termasuk tabel pencarian) oleh Sean Eron Anderson dari Universitas Stanford
• (Inggris) Memoization in C++ oleh Paul McNamee dari Universitas Johns Hopkins
• (Inggris) The Quest for an Accelerated Population Count oleh Henry S. Warren, Jr.