Was bedeutet es, eine Funktion in eine Tabelle umzuwandeln?

Question

In this videobetitelt Sie die Monade nicht fürchten, zwischen 05:02 und 06:05, Brian Beckman sagt:

Jeder Imperativ Programmierer geht durch diese Phase des Lernens, die Funktionen können mit Tisch-Lookups ersetzt werden. Oft machen Sie dies für Leistung. Sie möchten die sin Funktion oder die cosine Funktion machen, einfach eine Tabelle erstellen und in dieser Tabelle interpolieren .... Alle lernt diesen Trick.

Ich frage mich, was er mit diesem Trick meint und wie es die Leistung verbessert. Könnten Sie bitte etwas ausarbeiten?

Bedeutet es nur, dass Sie eine Art Look-Up wie Dictionary<TKey, Func<TInput, TReturn>>?

Answer 1

Dies bedeutet, dass jeder Algorithmus bei ausreichendem (potentiell unendlichen) Speicher vorberechnete Ausgabewerte basierend auf Eingabewerten in einem (indizierten) Array speichern und somit den Algorithmus in O (1) -Array-Lookup konvertieren kann. Es ist ein Trick, der so alt ist wie die Computer selbst, der seit Jahrhunderten vor Computern steht. Wissenschaftler verwendeten immer Tabellen mit vorberechneten Werten, um schnell Ergebnisse zu erhalten, ohne dass sie tatsächlich berechnet wurden.

Der Wikipedia-Artikel zu diesem Thema ist https://en.wikipedia.org/wiki/Lookup_table.

BTW, viele Real-Life-Algorithmen (CRC kommt hier in den Sinn) tun es auch, vor allem, wenn Geschwindigkeit entscheidend ist (Echtzeit-Anwendungen). Beachten Sie, dass die Speichermenge, die zum Speichern der vorausberechneten Werte benötigt wird, direkt mit der erwarteten Genauigkeit und der Anzahl der Eingangsvariablen zusammenhängt.