Функция, связанная с памятью

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

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

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

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

Функции памяти используют метод динамического программирования , называемый мемоизацией , чтобы уменьшить неэффективность рекурсии , которая может возникнуть. Он основан на простой идее вычисления и сохранения решений подзадач, чтобы решения можно было повторно использовать позже без повторного вычисления подзадач . Самый известный пример, использующий преимущества мемоизации, — это алгоритм , который вычисляет числа Фибоначчи . Следующий псевдокод использует рекурсию и мемоизацию и работает за линейное время ЦП :

 Фибоначчи ( n ) { для i = 0 до n -1 результаты [ i ] = -1 // -1 означает неопределено             вернуть Fibonacci_Results ( результаты , n ); }     Fibonacci_Results ( results , n ) { if ( results [ n ] != -1 ) // Если задача уже была решена, вернуть results [ n ] // найти ее. if ( n == 0 ) val = 0 else if ( n == 1 ) val = 1 else val = Fibonacci_Results ( results , n -2 ) + Fibonacci_Results ( results , n -1 ) results [ n ] = val // Сохраните этот результат для повторного использования.                                        возвращаемое значение }  

Сравните вышеприведенный пример с алгоритмом, который использует только рекурсию и работает за экспоненциальное время ЦП:

 Рекурсивный_Фибоначчи ( n ) { если ( n == 0 ) вернуть 0 если ( n == 1 ) вернуть 1               вернуть Рекурсивный_Фибоначчи ( n -1 ) + Рекурсивный_Фибоначчи ( n -2 ) }      

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

Термин «функция, связанная с памятью» появился совсем недавно и используется в основном для описания функции, которая использует XOR и состоит из серии вычислений, в которых каждое вычисление зависит от предыдущего вычисления. В то время как функции памяти уже давно играют важную роль в улучшении временной сложности, функции, связанные с памятью, нашли гораздо меньше применений. Однако недавно ^{[ когда? ]} ученые предложили метод, использующий функции, связанные с памятью, как средство, препятствующее спамерам злоупотреблять ресурсами, что может стать крупным прорывом в этой области.

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

В 1992 году ученые-исследователи IBM Синтия Дворк и Мони Наор опубликовали на конференции CRYPTO 1992 статью под названием « Ценообразование посредством обработки или борьбы с нежелательной почтой» [ ^1], в которой предлагалась возможность использования функций, связанных с процессором, для удержания злоумышленников от рассылки спама. Схема основывалась на идее, что пользователи компьютеров с гораздо большей вероятностью будут злоупотреблять ресурсом, если стоимость злоупотребления ресурсом незначительна: основная причина, по которой спам стал настолько распространенным, заключается в том, что отправка электронного письма обходится спамерам совсем недорого.

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

Базовая схема, защищающая от злоупотреблений, выглядит следующим образом:
даны Отправитель, Получатель и Сообщение электронной почты. Если Получатель заранее согласился получать электронное письмо от Отправителя, то Сообщение передается обычным способом. В противном случае Отправитель вычисляет некоторую функцию G(Сообщение) и отправляет (Сообщение, G(Сообщение)) Получателю. Получатель проверяет, имеет ли то, что он получает от Отправителя, форму (Сообщение, G(Сообщение)) . Если да, Получатель принимает Сообщение. В противном случае Получатель отклоняет Сообщение.

Функция G() выбирается таким образом, чтобы проверка Получателем была относительно быстрой (например, занимая миллисекунду), а вычисление Отправителем было несколько медленным (занимающим по крайней мере несколько секунд). Таким образом, Отправитель будет отбит желанием отправлять Сообщение нескольким получателям без предварительных соглашений: стоимость с точки зрения как времени, так и вычислительных ресурсов многократного вычисления G() станет весьма непомерной для спамера, который намерен отправить много миллионов электронных писем.

Основная проблема использования вышеприведенной схемы заключается в том, что быстрые ЦП выполняют вычисления намного быстрее, чем медленные ЦП. Кроме того, компьютерные системы более высокого класса также имеют сложные конвейеры и другие выгодные функции, которые облегчают вычисления. В результате спамер с современной системой вряд ли будет затронут таким сдерживанием, в то время как типичный пользователь с посредственной системой будет затронут неблагоприятно. Если вычисление занимает несколько секунд на новом ПК , оно может занять минуту на старом ПК и несколько минут на КПК , что может быть неприятно для пользователей старых ПК, но, вероятно, неприемлемо для пользователей КПК. Различие в скорости клиентских ЦП представляет собой одно из существенных препятствий для широкого принятия любой схемы, основанной на функции, связанной с ЦП. Поэтому исследователи озабочены поиском функций, которые большинство компьютерных систем будут оценивать примерно с одинаковой скоростью, так что высокопроизводительные системы могли бы оценивать эти функции несколько быстрее, чем низкопроизводительные системы (в 2–10 раз быстрее, но не в 10–100 раз быстрее), как может подразумевать различие ЦП. Эти соотношения достаточно « эгалитарны » для предполагаемых приложений: функции эффективно препятствуют злоупотреблениям и не добавляют чрезмерной задержки к законным взаимодействиям в широком спектре систем.

Новый эгалитарный подход заключается в том, чтобы полагаться на функции, связанные с памятью. Как уже говорилось ранее, функция, связанная с памятью, — это функция, время вычисления которой доминирует над временем, потраченным на доступ к памяти. Функция, связанная с памятью, обращается к ячейкам в большой области памяти непредсказуемым образом, таким образом, что использование кэшей неэффективно. В последние годы скорость ЦП резко возросла, но был достигнут сравнительно небольшой прогресс в разработке более быстрой основной памяти. Поскольку коэффициенты задержек памяти машин , построенных за последние пять лет, обычно не превышают двух и почти всегда меньше четырех, функция, связанная с памятью, будет эгалитарной для большинства систем в обозримом будущем.

• Архитектура компьютера
• CPU-bound
• Динамическое программирование
• I/O-связанный
• Мемоизация
• Функция, требующая большой памяти
• Оптимальная подструктура
• Доказательство работы
• Рекурсия
• Узкое место памяти

• Реализация функции, связанной с памятью
• Архитектура компьютера
• Как работает компьютерная память
• Динамическое программирование
• Ограничение ЦП и ограничение ввода-вывода
• Спам – FTC Информация для потребителей