In der heutigen Welt hat Lookup-Tabelle in verschiedenen Bereichen des täglichen Lebens eine zentrale Rolle eingenommen. Von Politik über Technologie bis hin zu Unterhaltung und Kultur hat Lookup-Tabelle es geschafft, die Aufmerksamkeit unzähliger Menschen auf der ganzen Welt zu erregen. Seine Bedeutung und sein Einfluss haben sich im Laufe der Zeit gefestigt und sind zu einem Thema von allgemeinem Interesse geworden, das niemanden gleichgültig lässt. In diesem Artikel werden wir versuchen, uns mit den wichtigsten Aspekten von Lookup-Tabelle zu befassen und seine Auswirkungen und Entwicklung in verschiedenen Kontexten zu analysieren. Wagen Sie den Einstieg in die faszinierende Welt von Lookup-Tabelle und entdecken Sie alles, was es zu bieten hat.
Lookup-Tabellen (LUT) bzw. Umsetzungstabellen werden in der Informatik und in der Digitaltechnik verwendet, um Informationen statisch zu definieren und diese zur Laufzeit des Programms – zur Vermeidung aufwändiger Berechnungen oder hohen Speicherverbrauchs – zu benutzen.
Zur Speicherung und Verarbeitung von Lookup-Tabellen sind folgende Varianten üblich:
Zur Erzeugung der LUT-Daten kommen mehrere Verfahrensweisen infrage:
Externe Lookup-Tabellen definieren sich lediglich über die Art ihrer Verwendung (look-up = "nachschlagen"); bezüglich der Speicherungstechnik unterscheiden sie sich in keiner Weise von anderen Daten.
Die Werte einer Funktion werden vorab ermittelt und im Speicher als Tabelle abgelegt. Damit gleicht das LUT-Verfahren der Benutzung einer Tabelle aus der Vor-Taschenrechner-Ära, wie bei Zinstabellen, im Tafelwerk und manchen Rechenschiebern.
Die LUT wird als eine Datenstruktur, meist ein (assoziatives) Array, das komplizierte Laufzeitberechnungen durch einen einfachen indizierten Zugriff auf die Datenstruktur ersetzt, realisiert. Dies führt zu einem signifikanten Geschwindigkeitsgewinn, sofern die benötigten Speicherzugriffe schneller sind als die normale Berechnung.
Da die Zugriffe auf den Index der Lookup-Tabelle mit einem geringerwertigeren Datentyp durchgeführt werden können als die in der Tabelle enthaltenen Werte, kann die Methode auch zur Einsparung von Speicherplatz verwendet werden.
Ein klassisches Beispiel ist eine trigonometrische Tabelle. Die Berechnung des Sinus etwa kann sehr lange dauern und ist bei jedem Aufruf der Funktion wiederholt nötig. Um das zu vermeiden, werden zu Beginn einige Werte des Sinus berechnet und in einer Tabelle gespeichert, zum Beispiel für jede ganze Gradzahl. Später, wenn ein konkreter Sinus berechnet werden soll, rundet die Funktion die gewünschte Gradzahl und liest den Sinuswert aus der Tabelle.
Zu beachten ist weiterhin, dass z. B. ein reelles Argument (bzw. eine Real-Zahl mit einigen Nachkommastellen) erst auf einen natürlichen (Integer-)Index abgebildet werden muss, um als Schlüssel für eine Speicherstelle Verwendung zu finden. Dazu muss, wenn beispielsweise für eine periodische Funktion nur Werte aus der ersten Periode um 0 herum in der LUT vorhanden sind, das Argument zunächst in das Periodenintervall abgebildet („reelles Modulo“) und danach gehasht (auf eine Speicherstelle abgebildet) werden.
Um die Genauigkeit der Berechnung zu verbessern, kann auch ein Interpolations-Algorithmus verwendet werden. Dabei wird versucht, durch mehrere benachbarte Einträge aus der Tabelle (im obigen Beispiel die darüber und darunter liegende ganze Gradzahl) und einige weitere Berechnungen den Wert genauer abzuschätzen. Das benötigt zwar etwas mehr Zeit, kann die Genauigkeit aber enorm verbessern. Die Methode kann auch dazu verwendet werden, die Lookup-Tabelle bei gleicher Genauigkeit zu verkleinern.
Bei der Benutzung von Lookup-Tabellen ist zu beachten, dass sie auch langsamer als die direkte Berechnung sein können, wenn die Berechnung relativ simpel ist. Das liegt nicht nur an langsamen Speicherzugriffen, sondern auch an einem erhöhten Speicherbedarf und einer Beeinträchtigung des Caches. Dies wird immer wichtiger, da Mikroprozessoren zunehmend schneller als Speicherchips werden. Optimierungen wie die beispielhaft angeführten Sinus-Tabellen sind mit modernen Prozessorgenerationen oft unnötig oder sogar kontraproduktiv.
In der digitalen Schaltungstechnik werden im Gegensatz zur Programmierung auch sehr einfache Funktionen wie logische Gleichungen (AND, OR, XOR) durch eine LUT ersetzt. Eine Tabelle ist leichter anzupassen als eine Transistorschaltung, daher wird die LUT in der programmierbaren Logik, insbesondere FPGAs und bei der Herstellung von ICs nach Kundenwunsch (ASIC), implementiert.
Eine weitere LUT-Schaltung basiert auf einem 2n-nach-1-Multiplexer mit n Steuereingängen und 2n Speicherstellen. Auch wurden PROM-Speicher zur Realisierung einer 8-Bit-ALU verwendet.
Hierbei werden in Lookup-Tabellen Einträge für beliebige anwendungsbezogene Inhalte (z. B. Informationen je Bundesland, je Branche, je Kfz-Ortskennzeichen, je Währung, je Fehlercode etc.) geführt. Die Einträge bestehen i. d. R. aus einer Kurz-Identifikation und weiteren Attributen, z. B. einer ausführlichen Bezeichnung. Die Tabellen können wie folgt benutzt werden:
Beispiel:
Die Einzelzeilen der Branchenmeldung könnten dann z. B. wie folgt aussehen:
ZL-NR Branchenbezeichnung Kreditsumme 01 Öffentliche Haushalte 1) 1.234.567 2) 02 Land- und Forstwirtschaft 567.890 1) = aus der Lookup-Tabelle zugeordnet 2) über Branchenschlüssel aggregiert