Nachschlagetabelle

In der Informatik ist eine Lookup-Tabelle ( LUT ) ein Array , das die Laufzeitberechnung einer mathematischen Funktion durch eine einfachere Array-Indexierung ersetzt – ein Vorgang , der als direkte Adressierung bezeichnet wird . Die dadurch erzielte Zeitersparnis kann erheblich sein, da das Abrufen eines Wertes aus dem Speicher oft schneller ist als die Durchführung einer aufwändigen Berechnung oder einer Ein-/Ausgabeoperation . ^{[ 1 ]} Die Tabellen können vorab berechnet und im statischen Programmspeicher abgelegt, im Rahmen der Initialisierungsphase eines Programms berechnet (oder „vorabgeladen“ ) ( Memoisierung ) oder sogar in anwendungsspezifischen Plattformen in Hardware gespeichert werden. Lookup-Tabellen werden auch häufig zur Validierung von Eingabewerten verwendet, indem diese mit einer Liste gültiger (oder ungültiger) Elemente in einem Array abgeglichen werden. In einigen Programmiersprachen können sie Zeigerfunktionen (oder Offsets zu Labels) zur Verarbeitung der übereinstimmenden Eingabe enthalten . FPGAs nutzen ebenfalls häufig rekonfigurierbare, hardwareimplementierte Lookup-Tabellen, um programmierbare Hardwarefunktionen bereitzustellen. LUTs unterscheiden sich von Hashtabellen dadurch, dass eine Hashtabelle zum Abrufen eines Werts mit Schlüssel den Wert im Slot speichert, wobei eine Hashfunktion ist, d . h. zur Berechnung des Slots verwendet wird. Im Fall einer LUT wird der Wert hingegen im Slot gespeichert und ist somit direkt adressierbar. ^{[ 2 ] : 466} ${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$${\displaystyle h(k)}$${\displaystyle h}$${\displaystyle k}$${\displaystyle v}$${\displaystyle k}$

Vor dem Aufkommen von Computern wurden Wertetabellen verwendet, um die manuelle Berechnung komplexer Funktionen zu beschleunigen, beispielsweise in der Trigonometrie , bei Logarithmen und statistischen Dichtefunktionen. ^{[ 3 ]}

Im alten Indien (499 n. Chr.) erstellte Aryabhata eine der ersten Sinustabellen , die er in einem auf Sanskrit-Buchstaben basierenden Zahlensystem kodierte. 493 n. Chr. verfasste Victorius von Aquitanien eine 98-spaltige Multiplikationstabelle, die (in römischen Ziffern ) das Produkt jeder Zahl von 2 bis 50 angab. Die Zeilen waren „eine Liste von Zahlen, beginnend mit Tausend, absteigend in Hunderterschritten bis Hundert, dann in Zehnerschritten bis Zehn, dann in Einerschritten bis Eins und schließlich die Brüche bis 1/144“ ^{[ 4 ].} Heutzutage lernen Schulkinder oft das Einmaleins auswendig , um Berechnungen der häufigsten Zahlen (bis 9 × 9 oder 12 × 12) zu vermeiden.

In den Anfängen der Computergeschichte waren Ein-/Ausgabeoperationen besonders langsam – selbst im Vergleich zu den damaligen Prozessorgeschwindigkeiten. Es war sinnvoll, aufwändige Leseoperationen durch eine Art manuelles Caching zu reduzieren , indem entweder statische Nachschlagetabellen (im Programm eingebettet) oder dynamische, vorab geladene Arrays erstellt wurden, die nur die am häufigsten vorkommenden Datenelemente enthielten. Trotz der Einführung von systemweitem Caching, das diesen Prozess mittlerweile automatisiert, können anwendungsspezifische Nachschlagetabellen die Leistung für Datenelemente, die sich selten oder nie ändern, weiterhin verbessern.

Nachschlagetabellen gehörten zu den ersten Funktionen, die in Tabellenkalkulationsprogrammen implementiert wurden . Die erste Version von VisiCalc (1979) enthielt bereits eine solche LOOKUPFunktion unter ihren ursprünglichen 20 Funktionen. ^{[ 5 ]} Microsoft Excel bietet mehrere spezialisierte Nachschlagefunktionen, darunter eine VLOOKUPfür die vertikale Suche (wie in einem traditionellen Nachschlagewerk), HLOOKUPeine für die horizontale Suche und (seit 2019) XLOOKUPeine für die gleichzeitige Ausgabe mehrerer Spalten. ^{[ 6 ]}

Obwohl die Leistung einer LUT für eine Suchoperation garantiert ist, dürfen keine zwei Entitäten oder Werte denselben Schlüssel haben . Ist der Wertebereich – aus dem die Schlüssel stammen – groß, kann die Speicherung im Speicher unpraktisch oder unmöglich sein . Es gibt verschiedene Möglichkeiten, dieses Problem zu umgehen, beispielsweise durch die Verwendung einer Hashtabelle ^{[ 2 ] : 468.} Wenn viele Schlüssel denselben Wert haben oder die Schlüssel einen numerischen Wert mit einer gewissen Genauigkeit repräsentieren, kann eine Verringerung dieser Genauigkeit den Wertebereich ausreichend verkleinern. Anschließend kann die Interpolation verwendet werden, um den durch den Genauigkeitsverlust verursachten Fehler zu korrigieren. ${\displaystyle O(1)}$${\displaystyle k}$${\displaystyle U}$

Bei einer einfachen Hash-Funktionssuche wird der vorzeichenlose Rohdatenwert direkt als Index einer eindimensionalen Tabelle verwendet, um ein Ergebnis zu extrahieren. Für kleine Bereiche zählt dies zu den schnellsten Suchmethoden und übertrifft sogar die Geschwindigkeit der binären Suche ohne Verzweigungen bei konstanter Laufzeit . ^{[ 7 ]}

Ein diskretes Problem, dessen Lösung auf vielen Computern rechenintensiv ist, ist das Zählen der auf 1 gesetzten Bits in einer Binärzahl, auch Populationsfunktion genannt . Beispielsweise entspricht die Dezimalzahl „37“ binär „00100101“ und enthält somit drei auf „1“ gesetzte Bits. ^{[ 8 ] : 282}

Ein einfaches Beispiel für C -Code, der die 1-Bits in einer Ganzzahl zählt , könnte so aussehen: ^{[ 8 ] : 283}

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

Die obige Implementierung benötigt 32 Operationen zur Auswertung eines 32-Bit-Wertes, was aufgrund von Verzweigungen potenziell mehrere Taktzyklen in Anspruch nehmen kann . Sie kann in eine Lookup-Tabelle „ abgewickelt “ werden, die wiederum eine einfache Hash-Funktion verwendet , um eine bessere Performance zu erzielen. ^{[ 8 ] : 282–283}

Das Bit-Array ` bits_set` mit 256 Einträgen wird erstellt, indem die Anzahl der gesetzten Einsen in jedem möglichen Byte-Wert angegeben wird (z. B. 0x00 = 0, 0x01 = 1, 0x02 = 1 usw.). Obwohl ein Laufzeitalgorithmus zur Generierung des `bits_set`- Arrays verwendet werden kann, ist dies angesichts der Größe eine ineffiziente Nutzung von Taktzyklen. Daher wird eine vorab berechnete Tabelle verwendet – obwohl ein Kompilierzeit- Skript die Tabelle dynamisch generieren und an die Quelldatei anhängen könnte . Die Summe der Einsen in jedem Byte der Ganzzahl kann durch eine einfache Hash-Funktionssuche auf jedem Byte berechnet werden ; dadurch werden Verzweigungen effektiv vermieden, was zu einer erheblichen Leistungsverbesserung führt. ^{[ 8 ] : 284}

int count_ones ( int input_value ) { union four_bytes { int big_int ; char each_byte [ 4 ]; } operand = input_value ; const int bits_set [ 256 ] = { 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3, 4 , 4 , 5 , 4 , 5 , 5 , 6 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 2 , 3 , 3 , 4, 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 5 , 6 , 6 , 7 , 6 , 7 , 7 , 8 } ;​​​​​​​​​​​​​​​return ( bits_set [ operand . each_byte [ 0 ]] + bits_set [ operand . each_byte [ 1 ]] + bits_set [ operand . each_byte [ 2 ]] + bits_set [ operand . each_byte [ 3 ]]); }}

„Lookup-Tabellen (LUTs) sind eine hervorragende Technik zur Optimierung der Auswertung von Funktionen, deren Berechnung aufwändig, deren Zwischenspeicherung jedoch kostengünstig ist. … Für Datenanfragen, die zwischen den Stichproben der Tabelle liegen, kann ein Interpolationsalgorithmus durch Mittelung benachbarter Stichproben sinnvolle Näherungswerte erzeugen.“ ^{[ 9 ]}

In Datenanalyseanwendungen wie der Bildverarbeitung kann eine Lookup-Tabelle (LUT) verwendet werden, um die Eingabedaten in ein geeigneteres Ausgabeformat zu transformieren. Beispielsweise könnte ein Graustufenbild des Planeten Saturn in ein Farbbild umgewandelt werden, um die Unterschiede in seinen Ringen hervorzuheben.

In der Bildverarbeitung werden Lookup-Tabellen häufig als LUTs (oder 3DLUTs) bezeichnet. Sie liefern für jeden Indexwert einen Ausgabewert. Eine gängige LUT, die sogenannte Farbpalette , dient zur Bestimmung der Farben und Intensitätswerte, mit denen ein bestimmtes Bild dargestellt wird. In der Computertomographie bezeichnet „Windowing“ ein verwandtes Konzept zur Festlegung der Darstellung der Intensität gemessener Strahlung.

Ein klassisches Beispiel für die Reduzierung von Laufzeitberechnungen mithilfe von Nachschlagetabellen ist die Ermittlung des Ergebnisses einer trigonometrischen Berechnung, beispielsweise des Sinus eines Wertes. ^{[ 10 ]} Die Berechnung trigonometrischer Funktionen kann eine Anwendung erheblich verlangsamen. Dieselbe Anwendung kann wesentlich schneller fertig sein, wenn sie zuvor den Sinus einer Reihe von Werten vorab berechnet, beispielsweise für jede ganze Gradzahl (die Tabelle kann zur Kompilierzeit als statische Variable definiert werden, wodurch wiederholte Laufzeitkosten reduziert werden). Benötigt das Programm den Sinus eines Wertes, kann es mithilfe der Nachschlagetabelle den nächstgelegenen Sinuswert aus einer Speicheradresse abrufen und den Sinus des gewünschten Wertes interpolieren, anstatt ihn mit einer mathematischen Formel zu berechnen. Nachschlagetabellen können daher von mathematischen Koprozessoren in Computersystemen verwendet werden. Ein Fehler in einer Nachschlagetabelle war für Intels berüchtigten Gleitkomma-Divisionsfehler verantwortlich .

Funktionen mit einer einzelnen Variablen (wie Sinus und Kosinus) lassen sich durch ein einfaches Array implementieren. Funktionen mit zwei oder mehr Variablen erfordern mehrdimensionale Array-Indexierungstechniken. Im letzteren Fall kann beispielsweise ein zweidimensionales Array vom Typ ` power[x][y]` verwendet werden , um eine Funktion zur Berechnung von x ^y für einen begrenzten Wertebereich von x und y zu ersetzen. Funktionen mit mehreren Ergebnissen können mithilfe von Nachschlagetabellen implementiert werden, die Arrays von Strukturen sind.

Wie bereits erwähnt, gibt es Zwischenlösungen, die Tabellen in Kombination mit geringem Rechenaufwand, oft mittels Interpolation , verwenden . Die Vorberechnung in Verbindung mit Interpolation kann die Genauigkeit für Werte, die zwischen zwei vorab berechneten Werten liegen, erhöhen. Dieses Verfahren benötigt etwas mehr Zeit, kann aber die Genauigkeit in entsprechenden Anwendungen deutlich verbessern. Je nach den vorab berechneten Werten kann die Vorberechnung mit Interpolation auch dazu verwendet werden, die Größe der Nachschlagetabelle zu reduzieren und gleichzeitig die Genauigkeit beizubehalten.

Obwohl die Verwendung einer Lookup-Tabelle oft effektiv ist, kann sie dennoch zu erheblichen Leistungseinbußen führen, wenn die Berechnung, die die LUT ersetzt, relativ einfach ist. Speicherzugriffszeiten und die Komplexität der Speicheranforderungen können die Laufzeit der Anwendung und die Systemkomplexität im Vergleich zu einer direkten Formelberechnung erhöhen. Auch die Gefahr einer Cache-Überlastung kann ein Problem darstellen. Zugriffe auf große Tabellen führen fast immer zu einem Cache-Fehler . Dieses Phänomen gewinnt zunehmend an Bedeutung, da die Prozessoren die Speicherkapazität übertreffen. Ein ähnliches Problem tritt bei der Rematerialisierung auf , einer Compiler-Optimierung . In manchen Umgebungen, wie beispielsweise der Programmiersprache Java , können Tabellenzugriffe aufgrund der obligatorischen Bereichsprüfung, die für jeden Zugriff einen zusätzlichen Vergleich und eine Verzweigung erfordert, noch aufwändiger sein.

Es gibt zwei grundlegende Einschränkungen hinsichtlich der Erstellung einer Nachschlagetabelle für eine benötigte Operation. Die erste ist der verfügbare Speicherplatz: Eine Nachschlagetabelle kann nicht größer sein als der dafür verfügbare Speicherplatz. Zwar lassen sich auch datenträgerbasierte Nachschlagetabellen erstellen, dies führt jedoch zu längeren Suchzeiten. Die zweite Einschränkung ist die Zeit, die für die erstmalige Berechnung der Tabellenwerte benötigt wird. Obwohl dies in der Regel nur einmal erforderlich ist, kann eine unzumutbar lange Berechnung die Verwendung einer Nachschlagetabelle ungeeignet machen. Wie bereits erwähnt, können Tabellen jedoch in vielen Fällen statisch definiert werden.

Die meisten Computer führen nur einfache Rechenoperationen aus und können den Sinus eines gegebenen Wertes nicht direkt berechnen. Stattdessen verwenden sie den CORDIC- Algorithmus oder eine komplexe Formel wie die folgende Taylorreihe , um den Sinuswert mit hoher Genauigkeit zu berechnen: ^{[ 11 ] : 5}

${\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$(für x nahe 0)

Die Berechnung kann jedoch aufwändig sein, insbesondere auf langsamen Prozessoren, und viele Anwendungen, vor allem in der traditionellen Computergrafik , benötigen Tausende von Sinuswerten pro Sekunde. Eine gängige Lösung besteht darin, zunächst den Sinus vieler gleichmäßig verteilter Werte zu berechnen und anschließend den Sinus von x zu ermitteln, indem man den Wert auswählt, der x am nächsten liegt (mittels Array-Indexierung). Dieser Wert liegt nahe am korrekten Wert, da der Sinus eine stetige Funktion mit beschränkter Änderungsrate ist. ^{[ 11 ] : 6} Zum Beispiel: ^{[ 12 ] : 545–548}

reelles Array sine_table [ - 1000 .. 1000 ] für x von - 1000 bis 1000 sine_table [ x ] = sin ( pi * x / 1000 )function lookup_sine ( x ) return sine_table [ round ( 1000 * x / pi )]

Leider benötigt die Tabelle recht viel Speicherplatz: Bei Verwendung von IEEE-Gleitkommazahlen doppelter Genauigkeit wären über 16.000 Bytes erforderlich. Wir könnten zwar weniger Werte verwenden, aber die Genauigkeit würde sich dadurch deutlich verschlechtern. Eine gute Lösung ist die lineare Interpolation . Dabei wird eine Gerade zwischen den beiden Tabellenpunkten beidseitig des Wertes gezogen und der Wert auf dieser Geraden ermittelt. Die Berechnung ist weiterhin schnell und für stetige Funktionen wie die Sinusfunktion deutlich genauer. Hier ist ein Beispiel für die Anwendung der linearen Interpolation:

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 )

Die lineare Interpolation liefert eine stetige interpolierte Funktion, deren Ableitungen jedoch im Allgemeinen nicht stetig sind . Für eine glattere Interpolation von Tabellenwerten, die stetig ist und eine stetige erste Ableitung besitzt , sollte man den kubischen Hermite-Spline verwenden .

Bei der Interpolation lässt sich die Größe der Nachschlagetabelle durch ungleichmäßiges Sampling reduzieren . Das bedeutet, dass bei annähernd linearem Funktionsverlauf wenige Abtastpunkte verwendet werden, während bei schnellen Wertänderungen mehr Abtastpunkte genutzt werden, um die Approximation möglichst genau an die tatsächliche Kurve anzupassen. Weitere Informationen finden Sie unter Interpolation .

Speichercaches (einschließlich Festplattencaches für Dateien oder Prozessorcaches für Code oder Daten) funktionieren auch wie eine Nachschlagetabelle. Die Tabelle wird mit sehr schnellem Speicher erstellt, anstatt auf langsamerem externem Speicher gespeichert zu werden, und verwaltet zwei Datenelemente für einen Teilbereich von Bits, aus denen eine externe Speicheradresse (oder Festplattenadresse) besteht (insbesondere die niedrigstwertigen Bits jeder möglichen externen Adresse):

• Ein Teil (das Tag) enthält den Wert der verbleibenden Bits der Adresse; wenn diese Bits mit denen der zu lesenden oder zu schreibenden Speicheradresse übereinstimmen, enthält der andere Teil den zwischengespeicherten Wert für diese Adresse.
• Das andere Element speichert die Daten, die mit dieser Adresse verknüpft sind.

Es wird eine einzelne (schnelle) Suche durchgeführt, um das Tag in der Lookup-Tabelle an dem durch die niedrigstwertigen Bits der gewünschten externen Speicheradresse angegebenen Index zu lesen und festzustellen, ob die Speicheradresse im Cache vorhanden ist. Wenn ein Treffer gefunden wird, ist kein Zugriff auf den externen Speicher erforderlich (außer bei Schreibvorgängen, bei denen der zwischengespeicherte Wert nach einer gewissen Zeit asynchron in den langsameren Speicher aktualisiert werden muss oder wenn die Position im Cache ersetzt werden muss, um eine andere Adresse zwischenzuspeichern).

In der digitalen Logik lässt sich eine Lookup-Tabelle mit einem Multiplexer realisieren , dessen Selektionsleitungen vom Adresssignal angesteuert werden und dessen Eingänge die Werte der im Array enthaltenen Elemente darstellen. Diese Werte können entweder fest verdrahtet sein, wie in einem ASIC , dessen Zweck funktionsspezifisch ist, oder durch D-Latches bereitgestellt werden , die konfigurierbare Werte ermöglichen ( ROM , EPROM , EEPROM oder RAM ) .

Eine n -Bit-LUT kann jede boolesche Funktion mit n Eingängen kodieren, indem sie die Wahrheitstabelle der Funktion in der LUT speichert. Dies ist eine effiziente Methode zur Kodierung boolescher Logikfunktionen , und LUTs mit 4–6 Eingangsbits sind tatsächlich die Schlüsselkomponente moderner FPGAs ( Field-Programmable Gate Arrays ), die rekonfigurierbare Hardware-Logikfunktionen bieten.

In Datenerfassungs- und Steuerungssystemen werden Nachschlagetabellen häufig verwendet, um die folgenden Operationen durchzuführen:

• Die Anwendung von Kalibrierdaten , um Korrekturen an unkalibrierten Mess- oder Sollwerten vorzunehmen ; und
• Durchführung der Umrechnung von Maßeinheiten ; und
• Durchführung generischer, benutzerdefinierter Berechnungen.

In manchen Systemen können für diese Berechnungen auch Polynome anstelle von Nachschlagetabellen definiert werden.

• Assoziatives Array
• Zweigtabelle
• Gals genaue Tabellen
• Memoisierung
• Speichergebundene Funktion
• Nächste-Nachbar-Interpolation
• Schieberegister-Nachschlagetabelle
• Palette , auch Farbtabelle oder CLUT genannt – zur Verwendung in der Computergrafik
• 3D-Lookup-Tabelle – Anwendung in der Filmindustrie

• Schnelle Tabellensuche unter Verwendung des Eingabezeichens als Index für die Verzweigungstabelle
• Die Kunst der Montage: Berechnung mittels Tabellennachschlagen
• „Bit-Twiddling-Hacks“ (einschließlich Nachschlagetabellen) Von Sean Eron Anderson von der Stanford University
• Memoization in C++ von Paul McNamee, Johns Hopkins University, zeigt Einsparungen
• „Das Streben nach einer beschleunigten Bevölkerungszählung“ von Henry S. Warren Jr.