Пространства-времени или времени памяти Компромисс в информатике является случай , когда алгоритм или программа сделок увеличилось использование пространства с уменьшением времени. Здесь пространство относится к хранилищу данных, потребляемому при выполнении данной задачи ( ОЗУ , жесткий диск и т. Д.), А время относится к времени, затраченному на выполнение данной задачи ( время вычислений или время отклика ).
Полезность данного компромисса между пространством и временем зависит от связанных фиксированных и переменных затрат (например, скорости процессора , объема памяти) и подлежит уменьшению отдачи .
История
Биологическое использование компромиссов между временем и памятью можно увидеть на ранних стадиях поведения животных . Использование накопленных знаний или кодирования реакций стимулов как «инстинктов» в ДНК позволяет избежать необходимости «вычислений» в критических по времени ситуациях. Более конкретно для компьютеров, справочные таблицы были реализованы с самых ранних операционных систем. [ необходима цитата ]
В 1980 году Мартин Хеллман впервые предложил использовать для криптоанализа компромисс между временем и памятью . [1]
Типы компромиссов
Таблицы подстановки и пересчет
Распространенной ситуацией является алгоритм, включающий таблицу поиска : реализация может включать в себя всю таблицу, что сокращает время вычислений, но увеличивает необходимый объем памяти, или она может вычислять записи таблицы по мере необходимости, увеличивая время вычислений, но уменьшая требования к памяти.
Сжатые и несжатые данные
Компромисс между пространством и временем может быть применен к проблеме хранения данных. Если данные хранятся в несжатом виде, они занимают больше места, но доступ занимает меньше времени, чем если бы данные хранились в сжатом виде (поскольку сжатие данных уменьшает объем занимаемого места, но для запуска алгоритма распаковки требуется время ). В зависимости от конкретного случая проблемы, любой способ является практичным. Также есть редкие случаи, когда можно напрямую работать со сжатыми данными, например, в случае сжатых индексов растровых изображений , когда работать со сжатием быстрее, чем без сжатия.
Повторный рендеринг и сохраненные изображения
Сохранение только SVG- источника векторного изображения и рендеринг его как растрового изображения каждый раз, когда запрашивается страница, было бы обменом времени на пространство; используется больше времени, но меньше места. Рендеринг изображения при изменении страницы и сохранение визуализированных изображений будет занимать место в обмен на время; используется больше места, но меньше времени. Этот метод более известен как кэширование .
Меньший код по сравнению с развертыванием цикла
Больший размер кода можно использовать для более высокой скорости программы при применении разворачивания цикла . Этот метод увеличивает длину кода для каждой итерации цикла, но экономит время вычислений, необходимое для возврата к началу цикла в конце каждой итерации.
Другие примеры
Алгоритмы, которые также используют компромисс между пространством и временем, включают:
- Бэби-шаг алгоритм гигантского шага для вычисления дискретных логарифмов
- Радужные таблицы в криптографии, где злоумышленник пытается добиться большего, чем экспоненциальное время, необходимое для атаки методом грубой силы . Радужные таблицы используют частично предварительно вычисленные значения в хэш-пространстве криптографической хеш-функции для взлома паролей за минуты, а не за недели. Уменьшение размера радужной таблицы увеличивает время, необходимое для перебора хеш-пространства.
- Meet-в-середине атаки использует пространственно-временной компромисс , чтобы найти криптографический ключ в только шифрование (и пробел) по сравнению с ожидаемым шифрование (но только пространство) наивной атаки.
- Динамическое программирование , при котором временная сложность проблемы может быть значительно уменьшена за счет использования большего объема памяти.
Смотрите также
Рекомендации
- ↑ Хеллман, Мартин (июль 1980 г.). «Криптоаналитический компромисс времени и памяти». IEEE Transactions по теории информации . 26 (4): 401–406. CiteSeerX 10.1.1.120.2463 . DOI : 10,1109 / tit.1980.1056220 .