Введение
Алгоритмическая торговля: больше ресурсов для меньшего времени.
Компромисс между пространством и временем, также известный как компромисс между временем и памятью или алгоритмический континуум пространства-времени в информатике, — это ситуация, когда алгоритм или программа увеличивает использование памяти в обмен на сокращение времени выполнения. Под пространством здесь понимается объем памяти, используемый для выполнения задачи (ОЗУ, ЖД и т.п.), а под временем — время, необходимое для выполнения задачи (время вычислений или время отклика). Эффективность конкретного компромисса между пространством и временем зависит от связанных с ним постоянных и переменных затрат (например, скорость процессора, объем памяти) и подвержена закону убывающей отдачи.
История
Биологическое использование компромиссов между временем и памятью можно наблюдать на ранних этапах поведения животных. Использование накопленных знаний или кодирование реакций на стимулы в виде "инстинктов" в ДНК позволяет избежать необходимости в "вычислениях" в ситуациях, требующих быстрого реагирования. В компьютерах таблицы поиска используются с самых первых операционных систем. В 1980 году Мартин Хеллман впервые предложил использовать компромисс между временем и памятью для криптоанализа.
Таблицы поиска и перерасчет
Общая ситуация — это алгоритм с таблицей поиска: реализация может включать в себя всю таблицу, что уменьшает время вычислений, но увеличивает объем необходимой памяти, или же вычислять элементы таблицы по мере необходимости, увеличивая время вычислений, но снижая требования к памяти.
Индексы баз данных против сканирования таблиц
Системы управления базами данных предоставляют возможность создания индексных структур данных для баз данных. Индексы повышают скорость поиска данных, но требуют дополнительного места для хранения. Без индексов для поиска нужных данных иногда необходимо выполнять полное сканирование таблицы, что занимает много времени.
Сжатые и не сжатые данные
Компромисс между пространством и временем может быть применен к задаче хранения данных. Хранение данных в несжатом виде требует больше места, но обеспечивает более быстрый доступ, чем хранение сжатых данных (поскольку сжатие уменьшает объем необходимого пространства, но требует времени на выполнение алгоритма декомпрессии). В зависимости от конкретной ситуации, любой из подходов может быть целесообразным. Существуют также редкие случаи, когда возможно непосредственная работа со сжатыми данными, например, при использовании сжатых битовых индексов, где работа со сжатием оказывается быстрее, чем без него.
Перепроизведение и сохранение изображений
Хранение только исходного кода SVG векторного изображения и его отрисовка в виде растрового изображения при каждом запросе страницы означало бы обмен временем на пространство: больше времени на обработку, но меньше места для хранения. Отрисовка изображения при изменении страницы и сохранение полученных растровых изображений означало бы обмен пространством на время: больше места для хранения, но меньше времени на обработку. Этот прием более известен как кэширование.
Меньший код против разворачивания цикла
Более большой размер кода можно увеличить в обмен на более высокую скорость работы программы при использовании разворачивания циклов. Эта техника увеличивает объем кода для каждой итерации цикла, но позволяет сэкономить время, затрачиваемое на возврат к началу цикла в конце каждой итерации.