Компромисс между пространством и временем

Алгоритм, позволяющий экономить больше места за меньшее время

Пространственно -временной компромисс , также известный как компромисс между временем и памятью или алгоритмический пространственно-временной континуум в информатике, — это случай, когда алгоритм или программа обменивает увеличенное использование пространства на уменьшенное время. Здесь пространство относится к хранилищу данных , потребляемому при выполнении данной задачи ( ОЗУ , жесткий диск и т. д.), а время относится ко времени, потребляемому при выполнении данной задачи ( время вычислений или время отклика ).

Полезность данного компромисса между пространством и временем зависит от связанных с ним постоянных и переменных затрат (например, скорости ЦП , объема памяти) и подвержена убывающей доходности .

История

Биологическое использование компромиссов между временем и памятью можно увидеть на ранних стадиях поведения животных . Использование сохраненных знаний или кодирование реакций стимулов в качестве «инстинктов» в ДНК позволяет избежать необходимости «вычислений» в критических по времени ситуациях. Что касается компьютеров, то таблицы поиска были реализованы с самых ранних операционных систем. ^{[ необходима цитата ]}

В 1980 году Мартин Хеллман впервые предложил использовать компромисс между временем и памятью для криптоанализа . ^[1]

Типы компромиссов

Таблицы поиска и пересчет

Распространенной ситуацией является алгоритм, включающий таблицу поиска : реализация может включать всю таблицу, что сокращает время вычислений, но увеличивает объем необходимой памяти, или она может вычислять записи таблицы по мере необходимости, увеличивая время вычислений, но уменьшая требования к памяти.

Индексы баз данных и сканирование таблиц

Системы управления базами данных предлагают возможность создания структур данных индекса базы данных . Индексы повышают скорость операций поиска за счет дополнительного пространства. Без индексов иногда требуются трудоемкие операции полного сканирования таблиц для поиска нужных данных.

Сжатые и несжатые данные

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

Повторная визуализация и сохраненные изображения

Сохранение только исходного SVG векторного изображения и его рендеринг в виде растрового изображения каждый раз при запросе страницы будет торговать временем за пространство; больше используемого времени, но меньше используемого пространства. Рендеринг изображения при изменении страницы и сохранение рендеринговых изображений будет торговать пространством за время; больше используемого пространства, но меньше используемого времени. Этот метод более известен как кэширование .

Меньший код по сравнению с развертыванием цикла

Больший размер кода можно обменять на более высокую скорость программы при применении разворачивания цикла . Этот метод делает код длиннее для каждой итерации цикла, но экономит время вычислений, необходимое для перехода к началу цикла в конце каждой итерации.

Другие примеры

Алгоритмы, которые также используют компромиссы между пространством и временем, включают:

• Алгоритм «маленький шаг-гигантский шаг» для вычисления дискретных логарифмов
• Радужные таблицы в криптографии, где противник пытается сделать лучше, чем экспоненциальное время, необходимое для атаки методом подбора . Радужные таблицы используют частично предварительно вычисленные значения в хэш-пространстве криптографической хэш-функции для взлома паролей за минуты вместо недель. Уменьшение размера радужной таблицы увеличивает время, необходимое для итерации по хэш-пространству.
• Атака «встреча посередине» использует компромисс между пространством и временем, чтобы найти криптографический ключ только в шифровании (и пространстве) по сравнению с ожидаемым шифрованием (но только в пространстве) наивной атаки. ${\displaystyle 2^{n+1}}$ ${\displaystyle O(2^{n})}$ ${\displaystyle 2^{2n}}$ ${\displaystyle O(1)}$
• Динамическое программирование , где временная сложность задачи может быть значительно снижена за счет использования большего объема памяти.
• Атака на компромисс между временем, памятью и данными , которая использует компромисс между пространством и временем с дополнительным параметром данных.

Смотрите также

• Эффективность алгоритма  – свойство алгоритма
• Теорема Блюма об ускорении  – Исключает присвоение произвольным функциям их вычислительной сложности.
• Вычислительная сложность  – количество ресурсов для выполнения алгоритма.
• Вычислительный ресурс  — то, что необходимо компьютеру для решения задачи, например, этапы обработки или память.
• Теорема Сэвича  – Связь между детерминированной и недетерминированной сложностью пространства

Ссылки

1. Хеллман, Мартин (июль 1980 г.). «Криптоаналитический компромисс времени и памяти». Труды IEEE по теории информации . 26 (4): 401–406. CiteSeerX  10.1.1.120.2463 . doi :10.1109/tit.1980.1056220. S2CID  552536.

Внешние ссылки

• Филипп Охслин: Создание более быстрого криптоаналитического компромисса между временем и памятью.
• Однажды в сказке: компромисс между памятью и драмой.