Что значит преобразовать функцию в таблицу поиска?

Question

В этом видео под названием " Не бойся монады", между 05:02 и 06:05, Брайан Бекман говорит:

Каждый императивный программист проходит через эту фазу обучения, что функции могут быть заменены поисками таблиц. Часто вы делаете это для производительности. Вы хотите сделать sin функция или cosine функция, просто создайте таблицу и интерполируйте в этой таблице.... Все учат этот трюк.

Мне интересно, что он подразумевает под этим трюком и как он улучшает производительность. Не могли бы вы уточнить?

Означает ли это просто иметь какой-то вид Dictionary<TKey, Func<TInput, TReturn>>?

Answer 1

Это означает, что каждый алгоритм при наличии достаточной (потенциально бесконечной) памяти может хранить предварительно вычисленные выходные значения на основе входных значений в (индексированном) массиве и, таким образом, преобразовывать алгоритм в O(1) поиск в массиве. Это трюк, такой же старый, как и сам компьютер, предшествующий компьютерам на века. Ученые всегда использовали таблицы предварительно вычисленных значений, чтобы быстро получить результаты, не делая реальных вычислений.

Статья в Википедии на эту тему: https://en.wikipedia.org/wiki/Lookup_table.

Кстати, многие реальные алгоритмы (здесь приходит на ум CRC) тоже делают это, особенно когда важна скорость (приложения реального времени). Обратите внимание, что объем памяти, необходимый для хранения предварительно вычисленных значений, напрямую связан с ожидаемой точностью и количеством входных переменных.