www.wikidata.id-id.nina.az

Tabel pencarian Artikel ini sudah memiliki daftar referensi bacaan terkait atau pranala luar tetapi sumbernya belum jela

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. 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 sunting

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.

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". 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. 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 sunting

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 sunting

Peta warna viridis
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 sunting

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.

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.

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 sunting

  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 sunting

wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Artikel ini sudah memiliki daftar referensi bacaan terkait atau pranala luar tetapi sumbernya belum jelas karena belum menyertakan kutipan pada kalimat Mohon tingkatkan kualitas artikel ini dengan memasukkan rujukan yang lebih mendetail bila perlu Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini 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 Daftar isi 1 Sejarah 2 Contoh 2 1 Tabel pencarian dalam pengolahan citra 2 2 Perhitungan fungsi sinus 3 Referensi 4 Pranala luarSejarah sunting nbsp 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 suntingContoh 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 sunting 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 sunting 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 sin x x x 3 6 x 5 120 x 7 5040 displaystyle operatorname sin x approx x frac x 3 6 frac x 5 120 frac x 7 5040 nbsp 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 nbsp 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 cos x sin x p 2 displaystyle operatorname cos x operatorname sin left x frac pi 2 right nbsp tan x sin x cos x displaystyle operatorname tan x frac operatorname sin x operatorname cos x nbsp 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 lt 90 kembalikan tabel sinus y jika x lt 180 kembalikan tabel sinus 90 y jika x lt 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 sunting McNamee Paul Automated Memoization in C pmcnamee net Campbell Kelly Martin Croarken Mary Robson Eleanor ed 2003 The History of Mathematical Tables From Sumer to Spreadsheets Oxford University Press Maher David W J John F Makowski 2001 Literary Evidence for Roman Arithmetic with Fractions Classical Philology 96 4 376 399 MrExcel East 31 Maret 2012 Bill Jelen From 1979 VisiCalc and LOOKUP Berkeley Institute for Data Science colormap colormaps py at master BIDS colormap GitHub Diakses tanggal 14 November 2020 Pranala luar sunting 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 Diperoleh dari https id wikipedia org w index php title Tabel pencarian amp oldid 17607616