Вступление
Сегодня все больше людей занимаются программированием. Новички, которые клепают тонны «красивого» кода на Java, или языках высокого уровня, или главные архитекторы приложений, у которых все строится красиво по паттернам и максимально применяя рефакторинг, или простые «средненькие» программисты который выполняют задания – все гонятся за ресурсами вычислительной техники.
Испокон веков программирования и теории алгоритмов стояла задача сократить использование ресурсов всеми возможными методами. Сейчас мы рассмотрим один из видов уменьшения времени выполнения. Но как и любая оптимизация – эта оптимизация не будет «идеальной», т.е. уменьшив время выполнения мы увеличим требуемую память.
Однажды, как-то на паре преподаватель задал нам главный вопрос – «Как сделать так, чтобы функция вычислялась самым быстрым способом?» и ответом на этот вопрос было «Не вычислять функцию вообще». Следуя из этой парадигмы, мы не будем совершать вообще никаких преобразований, мы будем только хранить выходы функции.
Таким образом, например, если нам нужно отсортировать массив, в котором будут все числа от одного до 100, мы не будем сортировать его, в худшем случае мы просто сгенерируем новый массив вида {1,2,3….100}, в лучшем – просто вернем уже сгенерированный массив.
Таблицы
Таблицы это наш сегодняшний основной инструмент. Все они располагаются в RAM. Запоминающее устройство с произвольным доступом (сокращённо ЗУПД; также Запоминающее устройство с произвольной выборкой, сокращённо ЗУПВ; англ. Random Access Memory) — один из видов памяти компьютера, позволяющий единовременно получить доступ к любой ячейке (всегда за одно, и то же время, вне зависимости от расположения) по её адресу на чтение или запись.
Допустим, у нас есть f(x) и ее рассчитанная таблица T(x). Таким образом таблица – будет одномерным массивом, размером с количества используемых аргументов функции. Например, для f(x) = 2*x^2, где x є GF(32^2-1), т.е. x – наше любимое целое число типа «unsigned int» для 32-битной архитектуры, T(x) будет выглядеть как {0, 2, 8, 18, 32, 50, … } и представляться в коде так:
const unsigned int DoubleSquareTable[6] = {0, 2, 8, 18, 32,50};
а для вычисления первых 6 выходов функции просто используем:
char i = 0;
while(i < 7)
{
std::cout << DoubleSquareTable[i] << std::endl;
++i;
}
Таким образом для вычисления f(x) требуется только tдост – время доступа в массив DoubleSquareTable согласно компиляции. Это будет время доступа в RAM. Понятно, что tдост << tвып, где tвып – время выполнения операций в f(x).
Обратные стороны медали
Первое – это время генерации таблицы. Так как таблицу же нужно где-нибудь найти, то ее нужно сгенерировать перед применением. Для генерации больших таблиц нужно использовать стандартные алгоритмы, аппаратное ускорение и аппаратное проектирование на FPGA.
Второе – это память которую занимает таблица. Они огромны, действительно огромны. Например для x є GF(32^2-1) их будет 32^2*4 байт. Ну в общем довольно много.
Моей мечтой всегда было составление таких таблиц для алгоритмов шифрования AES, Twofish и др. Это бы позволило довольно быстро подбирать ключи по множеству шифр-текстов, но вычисление такой таблицы будет очень и очень долгим. Кстати, на этом же принципе основан Bitcoin, по факту Bitcoin создает таблицу для хеш-функции.
Выводы
Таким образом, можно сказать, что это сильнейший способ увеличения производительности функций, но он имеет ряд недостатков и стоит использовать его с умом.
Автор: Kojiba
