Arama tablosu - Lookup table

Gelen bilgisayar bilimleri , bir arama tablosu bir olduğunu dizisi cümledeki o çalışma süresiyle daha basit bir dizi indeksleme işlemi ile hesaplama. İşlem süresindeki tasarruflar önemli olabilir, çünkü bellekten bir değer elde etmek genellikle "pahalı" bir hesaplama veya girdi / çıktı işlemi gerçekleştirmekten daha hızlıdır . Tablolar olabilir önceden hesaplanmış ve depolanmış statik program depolama hesaplanan (ya da "ön zorlama" ) bir programın başlatma fazı (bir parçası olarak memoization ), ya da uygulamaya özgü platformlarda donanım içinde saklanan. Arama tabloları, bir dizideki geçerli (veya geçersiz) öğeler listesiyle eşleşerek giriş değerlerini doğrulamak için kapsamlı bir şekilde kullanılır ve bazı programlama dillerinde, eşleşen girişi işlemek için işaretçi işlevlerini (veya etiketlere ofsetleri) içerebilir. FPGA'lar ayrıca programlanabilir donanım işlevselliği sağlamak için yeniden yapılandırılabilir, donanımla uygulanan arama tablolarından kapsamlı bir şekilde yararlanır.

Tarih

Abramowitz ve Stegun referans kitabındaki 20. yüzyıl ortak logaritmalar tablosunun bir parçası .

Bilgisayarların ortaya çıkmasından önce, trigonometri , logaritma ve istatistiksel yoğunluk fonksiyonları gibi karmaşık fonksiyonların elle hesaplanmasını hızlandırmak için değer arama tabloları kullanılıyordu .

Eski (MS 499) Hindistan'da Aryabhata , Sanskritçe harf tabanlı bir sayı sisteminde kodladığı ilk sinüs tablolarından birini yarattı . MS 493'te Victorius of Aquitaine , her sayının ürününü 2'den 50'ye kadar veren ( Roma rakamlarıyla ) 98 sütunlu bir çarpım tablosu yazdı ve satırlar "bin ile başlayan, yüzler bire azalan sayıların bir listesi idi. yüz, sonra ondan ona, sonra bire ve sonra da 1/144'e inen kesirler "Modern okul çocuklarına , en sık kullanılan sayıların (9'a kadar) hesaplanmasını önlemek için genellikle" çarpım tablolarını " ezberlemeleri öğretilir. x 9 veya 12 x 12).

Bilgisayar tarihinin ilk dönemlerinde, girdi / çıktı işlemleri özellikle yavaştı - zamanın işlemci hızlarına kıyasla bile. Pahalı okuma işlemlerini, statik arama tabloları (programa gömülü) veya yalnızca en yaygın olarak ortaya çıkan veri öğelerini içerecek şekilde önceden getirilmiş dinamik diziler oluşturarak manuel önbelleğe alma yoluyla azaltmak mantıklıydı . Artık bu süreci otomatikleştiren sistem genelinde önbelleğe alma uygulamasına rağmen, uygulama düzeyi arama tabloları, nadiren değişen veri öğelerinin performansını yine de artırabilir.

Arama tabloları , ilk 20 işlevi arasında bir işlev içeren VisiCalc'ın (1979) ilk sürümüyle, bilgisayar elektronik tablolarında uygulanan en eski işlevlerden biriydi . Bunu, Microsoft Excel gibi sonraki elektronik tablolar izledi ve dikey veya yatay bir tabloda aramayı basitleştirmek için özel ve işlevlerle tamamlandı . Microsoft Excel'de işlev 28 Ağustos 2019'dan itibaren kullanıma sunulmuştur. LOOKUPVLOOKUPHLOOKUPXLOOKUP

Örnekler

Bir dizide, ilişkilendirilebilir bir dizide veya bağlantılı bir listede basit arama (sıralanmamış liste)

Bu, doğrusal arama veya kaba kuvvet araması olarak bilinir; sırayla her bir öğe eşitlik açısından kontrol edilir ve varsa ilişkili değer, aramanın bir sonucu olarak kullanılır. Bu, sık oluşan değerler listenin başlarında oluşmadığı sürece genellikle en yavaş arama yöntemidir. Tek boyutlu bir dizi veya bağlantılı liste için , arama genellikle bir 'giriş' veri değeriyle bir eşleşme olup olmadığını belirlemektir.

Bir dizide veya bir ilişkisel dizide ikili arama (sıralı liste)

Bir " böl ve yönet algoritması " örneği olan ikili arama , tablonun hangi yarısında bir eşleşmenin bulunabileceğini belirleyerek ve başarıya veya başarısızlığa kadar tekrar ederek bulunan her bir öğeyi içerir. Bu, yalnızca liste sıralandığında mümkündür, ancak uzun listelerde bile iyi performans sağlar.

Önemsiz karma işlevi

Bir için önemsiz karma işlev arama, işaretsiz ham veri değeri kullanılır , doğrudan bir sonuç elde etmek için tek boyutlu bir tablo için bir indeks olarak. Küçük aralıklar için, bu en hızlı arama olabilir, hatta sıfır dallanma ile ikili arama hızını aşabilir ve sabit zamanda çalıştırabilir .

Bir dizi baytta bit sayma

Birçok bilgisayarda çözülmesi pahalı olan ayrı bir problem, bazen popülasyon fonksiyonu olarak adlandırılan (ikili) bir sayı içinde 1'e ayarlanan bitlerin sayısının sayılmasıdır . Örneğin, "37" ondalık sayısı ikili olarak "00100101" dir, bu nedenle ikili "1" olarak ayarlanmış üç bit içerir.

Basit bir örnek C bir 1 bit saymak için tasarlanmış kod, int gibi görünebilir: 

int count_ones(unsigned int x)
{
    int result = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        result++;
    }
    return result;
}

Görünüşe göre basit olan bu algoritma, modern bir mimaride bile potansiyel olarak yüzlerce döngü alabilir, çünkü döngüde birçok dallanma yapar ve dallanma yavaştır. Bu, döngü açma ve diğer bazı derleyici optimizasyonları kullanılarak iyileştirilebilir. Bununla birlikte, basit ve çok daha hızlı bir algoritmik çözüm var - önemsiz bir hash işlevi tablosu araması kullanan .

Basitçe , her bir olası bayt değerinde ayarlanan bir bit sayısını veren 256 girişle (örneğin, 0x00 = 0, 0x01 = 1, 0x02 = 1, vb.) Statik bir tablo, bit_set oluşturun . Ardından , sırayla her bayt için önemsiz bir hash işlevi araması kullanarak tamsayının her baytında bulunanların sayısını bulmak için bu tabloyu kullanın ve bunları toplayın. Bu, dallanma gerektirmez ve yalnızca önceki koddan önemli ölçüde daha hızlı olan dört dizinlenmiş bellek erişimi gerektirir. 

/* Pseudocode of the lookup table 'uint32_t bits_set[256]' */
/*                    0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... */
int bits_set[256] = {    0,    1,    1,    2,     1,     2, // 200+ more entries

/* (this code assumes that 'int' is an unsigned 32-bits wide integer) */
int count_ones(unsigned int x)
{
    return bits_set[ x       & 255]
        + bits_set[(x >>  8) & 255]
        + bits_set[(x >> 16) & 255]
        + bits_set[(x >> 24) & 255];
}

Yukarıdaki kaynak, "x" i 4 baytlık işaretsiz karakter dizisi olarak "yeniden biçimlendirerek" ve tercihen, bir işlev olmak yerine tek bir ifade olarak satır içi kodlanarak kolayca geliştirilebilir (AND'den kaçınarak ve kaydırarak). Bu basit algoritmanın bile artık çok yavaş olabileceğini unutmayın, çünkü orijinal kod modern işlemcilerin önbelleğinden daha hızlı çalışabilir ve (büyük) arama tabloları önbelleklere tam olarak uymaz ve belleğe daha yavaş erişime neden olabilir (ek olarak, Yukarıdaki örnekte, gerekli dört aramayı gerçekleştirmek için bir tablo içindeki hesaplama adresleri gerektirir).

Görüntü işlemede arama tabloları

Kırmızı (A), Yeşil (B), Mavi (C) 16 bitlik başvuru tablosu dosyası örneği. (14 - 65524 arası satırlar gösterilmemiştir)

Görüntü işleme gibi veri analizi uygulamalarında, giriş verilerini daha istenen bir çıktı formatına dönüştürmek için bir arama tablosu (LUT) kullanılır. Örneğin, Satürn gezegeninin gri tonlamalı bir resmi, halkalarındaki farklılıkları vurgulamak için renkli bir görüntüye dönüştürülecek.

Arama tablolarını kullanarak çalışma zamanı hesaplamalarını azaltmanın klasik bir örneği , bir değerin sinüsü gibi bir trigonometri hesaplamasının sonucunu elde etmektir . Trigonometrik fonksiyonların hesaplanması, bir hesaplama uygulamasını önemli ölçüde yavaşlatabilir. Aynı uygulama, örneğin her bir tam derece sayısı için bir dizi değerin sinüsünü ilk kez önceden hesapladığında çok daha erken bitirebilir (Tablo, derleme zamanında statik değişkenler olarak tanımlanabilir ve tekrarlanan çalışma süresi maliyetlerini azaltır). Program bir değerin sinüsünü gerektirdiğinde, bir bellek adresinden en yakın sinüs değerini almak için arama tablosunu kullanabilir ve ayrıca matematiksel formülle hesaplamak yerine istenen değerin sinüsüne enterpolasyon yapabilir. Arama tabloları bu nedenle bilgisayar sistemlerinde matematik yardımcı işlemcileri tarafından kullanılır . Arama tablosundaki bir hata, Intel'in meşhur kayan nokta bölme hatasından sorumluydu .

Tek bir değişkenin (sinüs ve kosinüs gibi) fonksiyonları basit bir dizi ile uygulanabilir. İki veya daha fazla değişkeni içeren işlevler, çok boyutlu dizi indeksleme tekniklerini gerektirir. Son durum, sınırlı bir aralıktaki x ve y değerleri için x y'yi hesaplamak üzere bir fonksiyonun yerine geçmek üzere iki boyutlu bir güç [x] [y] dizisi kullanabilir . Birden fazla sonucu olan işlevler, yapı dizileri olan arama tablolarıyla uygulanabilir.

Belirtildiği gibi, tabloları az miktarda hesaplamayla birlikte kullanan, genellikle enterpolasyon kullanan ara çözümler vardır . Ön hesaplama ile birlikte enterpolasyon, önceden hesaplanmış iki değer arasında kalan değerler için daha yüksek doğruluk sağlayabilir. Bu tekniğin gerçekleştirilmesi biraz daha fazla zaman gerektirir, ancak daha yüksek doğruluk gerektiren uygulamalarda doğruluğu büyük ölçüde artırabilir. Ön hesaplanan değerlere bağlı olarak, enterpolasyonlu ön hesaplama, doğruluğu korurken arama tablosu boyutunu küçültmek için de kullanılabilir.

Olarak görüntü işleme , arama tabloları genellikle denir LUT s (ya da 3DLUT) ve endeks değerleri bir dizi her biri için bir çıkış değeri verir. Renk haritası veya palet adı verilen ortak bir LUT, belirli bir görüntünün görüntüleneceği renkleri ve yoğunluk değerlerini belirlemek için kullanılır. Gelen bilgisayarlı tomografi , "pencereleme" ölçülen radyasyonun şiddetini göstermek için belirleyen ilgili konsepti anlamına da gelir.

Çoğu zaman etkili olsa da, bir arama tablosunun kullanılması yine de, eğer LUT'un yerini alan hesaplama nispeten basitse, ciddi bir ceza ile sonuçlanabilir. Bellek alma süresi ve bellek gereksinimlerinin karmaşıklığı, düz formül hesaplamasının gerektirdiğine göre uygulama çalışma süresini ve sistem karmaşıklığını artırabilir. Önbelleği kirletme olasılığı da bir sorun haline gelebilir. Büyük tablolar için tablo erişimleri neredeyse kesinlikle bir önbellek kaybına neden olacaktır . İşlemciler belleği geride bıraktıkça, bu fenomen giderek artan bir sorun haline geliyor. Benzer bir sorunu görünür rematerialization , bir derleyici optimizasyon . Java programlama dili gibi bazı ortamlarda, her arama için ek bir karşılaştırma ve dal içeren zorunlu sınır denetimi nedeniyle tablo aramaları daha da pahalı olabilir.

Gerekli bir işlem için bir arama tablosu oluşturmanın ne zaman mümkün olduğu konusunda iki temel sınırlama vardır. Biri, mevcut bellek miktarıdır: tablo için mevcut alandan daha büyük bir arama tablosu oluşturulamaz, ancak arama süresi pahasına disk tabanlı arama tabloları oluşturmak mümkündür. Diğeri, ilk durumda tablo değerlerini hesaplamak için gereken süredir; bunun genellikle yalnızca bir kez yapılması gerekmesine rağmen, çok uzun bir zaman alırsa, bir arama tablosunun kullanımını uygun olmayan bir çözüm haline getirebilir. Ancak daha önce belirtildiği gibi, birçok durumda tablolar statik olarak tanımlanabilir.

Sinüsleri hesaplama

Çoğu bilgisayar yalnızca temel aritmetik işlemleri gerçekleştirir ve belirli bir değerin sinüsünü doğrudan hesaplayamaz . Bunun yerine, sinüs değerini yüksek bir hassasiyetle hesaplamak için CORDIC algoritmasını veya aşağıdaki Taylor serisi gibi karmaşık bir formülü kullanırlar :

( 0'a yakın x için)

Ancak, özellikle yavaş işlemcilerde bunun hesaplanması pahalı olabilir ve özellikle geleneksel bilgisayar grafiklerinde her saniye binlerce sinüs değerini hesaplaması gereken birçok uygulama vardır . Yaygın bir çözelti başlangıçta bir çok eşit olarak dağıtılmış değerler sinüs hesaplamak için, ve bundan sonra da sinüs bulmaktır x biz değere yakın sinüs tercih x . Bu, doğru değere yakın olacaktır çünkü sinüs, sınırlı bir değişim oranına sahip sürekli bir fonksiyondur . Örneğin: 

real array sine_table[-1000..1000]
for x from -1000 to 1000
    sine_table[x] = sine(pi * x / 1000)

function lookup_sine(x)
    return sine_table[round(1000 * x / pi)]
Sinüs fonksiyonunun bir bölümünde doğrusal enterpolasyon

Ne yazık ki, tablo oldukça fazla alan gerektiriyor: IEEE çift duyarlıklı kayan noktalı sayılar kullanılırsa, 16.000 bayttan fazla gerekli olacaktır. Daha az numune kullanabiliriz, ancak bu durumda hassasiyetimiz önemli ölçüde kötüleşir. İyi bir çözüm, değerin her iki tarafındaki tablodaki iki nokta arasına bir çizgi çizen ve cevabı o satırda bulan doğrusal enterpolasyondur . Bunun hesaplanması hala hızlıdır ve sinüs işlevi gibi düzgün işlevler için çok daha doğrudur . Doğrusal enterpolasyon kullanan bir örnek: 

function lookup_sine(x)
    x1 = floor(x*1000/pi)
    y1 = sine_table[x1]
    y2 = sine_table[x1+1]
    return y1 + (y2-y1)*(x*1000/pi-x1)

Doğrusal enterpolasyon, sürekli olan ancak genel olarak sürekli türevlere sahip olmayan bir enterpolasyonlu fonksiyon sağlar . Sürekli olan ve sürekli birinci türevi olan tablo aramasının daha düzgün enterpolasyonu için kübik Hermite eğri kullanılmalıdır .

Alanın dörtte birini kullanan ancak hesaplaması biraz daha uzun süren başka bir çözüm, simetri kurallarıyla birlikte sinüs ve kosinüs arasındaki ilişkileri hesaba katmak olacaktır. Bu durumda, başvuru tablosu ilk çeyrek için sinüs fonksiyonu kullanılarak hesaplanır (yani sin (0..pi / 2)). Bir değere ihtiyacımız olduğunda, birinci çeyreğe sarılmış açı olması için bir değişken atarız. Daha sonra açıyı dört çeyreğe sararız (değerler her zaman 0 ile 2 * pi arasında ise gerekli değildir) ve doğru değeri döndürürüz (yani birinci çeyrek düz bir dönüş, ikinci çeyrek pi / 2-x, üçüncü ve dördüncü, sırasıyla birinci ve ikinci negatiflerdir). Kosinüs için, sadece pi / 2 (yani x + pi / 2) kadar kaydırılan açıyı döndürmeliyiz. Tanjant için sinüsü kosinüs ile böleriz (sıfıra bölme işlemi uygulamaya bağlı olarak gerekli olabilir): 

function init_sine()
    for x from 0 to (360/4)+1
        sine_table[x] = sin(2*pi * x / 360)

function lookup_sine(x)
    x = wrap x from 0 to 360
    y = mod (x, 90)
    if (x <  90) return  sine_table[   y]
    if (x < 180) return  sine_table[90-y]
    if (x < 270) return -sine_table[   y]
    return -sine_table[90-y]

function lookup_cosine(x)
    return lookup_sine(x + 90)

function lookup_tan(x)
    return lookup_sine(x) / lookup_cosine(x)

Enterpolasyon kullanılırken, arama tablosunun boyutu, tek tip olmayan örnekleme kullanılarak azaltılabilir ; bu, fonksiyonun düze yakın olduğu yerlerde, birkaç örnek noktası kullanırız, hızlı bir şekilde değer değiştirdiğinde ise yaklaşıklığı korumak için daha fazla örnek noktası kullanırız. gerçek eğriye yakın. Daha fazla bilgi için enterpolasyona bakın .

Arama tablolarının diğer kullanımları

Önbellekler

Ana madde: Önbellek (bilgi işlem)

Depolama önbellekleri (dosyalar için disk önbellekleri veya kod veya veriler için işlemci önbellekleri dahil) aynı zamanda bir arama tablosu gibi çalışır. Tablo, daha yavaş harici bellekte depolanmak yerine çok hızlı bellekle oluşturulmuştur ve bir harici bellek (veya disk) adresini (özellikle olası herhangi bir harici adresin en düşük bitleri) oluşturan bir alt bit aralığı için iki veri parçası tutar. :

  • bir parça (etiket) adresin kalan bitlerinin değerini içerir; eğer bu bitler okumak veya yazmak için hafıza adresinden gelenlerle eşleşirse, diğer parça bu adres için önbelleğe alınmış değeri içerir.
  • diğer parça bu adresle ilişkili verileri korur.

Arama tablosundaki etiketi istenen harici depolama adresinin en düşük bitleri tarafından belirtilen dizinde okumak ve bellek adresine önbellek tarafından vurulup vurulmadığını belirlemek için tek bir (hızlı) arama gerçekleştirilir. Bir isabet bulunduğunda, harici belleğe erişim gerekmez (önbelleğe alınan değerin bir süre sonra eşzamansız olarak daha yavaş belleğe güncellenmesinin gerekebileceği yazma işlemleri veya başka bir önbelleğe almak için önbellekteki konumun değiştirilmesi gerektiği durumlar hariç) adres).

Donanım LUT'ları

Olarak dijital mantık , bir arama tablosu bir ile uygulanabilecek çoklayıcı olan seçme hatlar adres sinyali tarafından tahrik edilir ve, girdileri dizide ihtiva edilen elemanların değerleridir. Bu değerler , amacı bir işleve özgü bir ASIC'de olduğu gibi fiziksel bağlantılı olabilir veya yapılandırılabilir değerlere izin veren D mandalları ile sağlanabilir . ( ROM , EPROM , EEPROM veya RAM .)

Bir n- bit LUT, işlevin doğruluk tablosunu LUT'ta depolayarak herhangi bir n- girdili Boole işlevini kodlayabilir . Bu, Boolean mantık işlevlerini kodlamanın etkili bir yoludur ve 4-6 bit girişli LUT'lar aslında yeniden yapılandırılabilir donanım mantık yetenekleri sağlayan modern alan programlanabilir kapı dizilerinin (FPGA'ler) temel bileşenidir .

Veri toplama ve kontrol sistemleri

Gelen veri toplama ve kontrol sistemleri , arama tabloları yaygın aşağıdaki işlemleri üstlenmek için kullanılır:

  • Kalibre edilmemiş ölçüm veya ayar noktası değerlerine düzeltmeler uygulamak için kalibrasyon verilerinin uygulanması ; ve
  • Ölçü birimi dönüştürme üstlenilmesi ; ve
  • Genel kullanıcı tanımlı hesaplamalar yapmak.

Bazı sistemlerde, bu hesaplamalar için arama tabloları yerine polinomlar da tanımlanabilir.

Ayrıca bakınız

Referanslar

Dış bağlantılar