Почему memoization не является языковой функцией?

Ответ 1

То, что вы хотите от memoization, может не совпадать с тем, что предоставит опция memoization компилятора.

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

Вы можете знать, что имеет смысл запоминать последние 2 или 3 значения, потому что вы никогда не будете использовать значения старше этого. (Fibonacci Sequence приходит на ум.)

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

Вы можете захотеть "выбросить" некоторые из меморизированных значений и начать все заново. (Таким образом, я memoized генератор случайных чисел, поэтому я мог воспроизвести последовательность случайных чисел, которые построили определенную структуру, в то время как некоторые другие параметры структуры были изменены.)

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

Памятный компилятор должен либо предоставить меморандум "один размер подходит всем", либо он должен предоставить множество возможных альтернатив и параметры для управления альтернативами. В какой-то момент всем становится проще требовать от пользователя предоставления собственной мемуаризации.

Ответ 2

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

Ответ 3

Clojure имеет функцию memoize (http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize):

memoize
function

Usage: (memoize f)

Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.

Ответ 4

В Haskell memoization является автоматическим для (чистых) функций, которые вы определили, которые не принимают аргументов. И пример Фибоначчи в том, что Wiki действительно о простейшем демонстрационном примере, о котором я мог бы подумать.

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

Я не уверен, каковы верхние пределы - очевидно, он не будет запоминать больше, чем доступная память. И я также не уверен, если memoization происходит во время компиляции (если значения могут быть определены во время компиляции), или если это всегда происходит при первом вызове функции.

Ответ 5

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

Ответ 6

A) Memoization торгует пространство для времени. Я полагаю, что это может оказаться довольно несвязанным свойством, в том смысле, что объем программ данных или библиотек должен был бы хранить очень быстро.

Для нескольких языков memoization легко реализуется и легко настраивается для данных требований.

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

B) Другой аспект: неверно, что все функции или методы дают один и тот же вывод для одного и того же заданного ввода. Во всяком случае, потребуется некоторое ключевое слово или синтаксис для memoization, а также конфигурация (ограничения памяти, политика недействительности,...)...

Ответ 7

Не все языки изначально поддерживают декораторы функций. Я предполагаю, что это будет более общий подход к поддержке, а не поддержка просто memoization.

Ответ 8

Ваш вопрос также оставляет открытым решение для вашего обучения больше языков. Я думаю, что Lisp поддерживает memoization, и я знаю, что Mathematica делает.

Ответ 9

Отмените вопрос. Почему это должно быть? Как сказал кто-то, его можно поместить в библиотеку, поэтому не нужно добавлять синтаксис к языку, он доступен только для чистых функций, которые трудно идентифицировать автоматически (если вы не заставляете программиста их комментировать). Также очень сложно определить, будет ли мемонирование ускоряться или нет. Я не думаю, что это желательная функция для языка программирования.

Ответ 10

Я действительно думаю, что такой вариант должен быть.

В задачах обработки данных есть неизменные входные данные (например, временные ряды, где в течение заданного времени, как только значение известно, оно никогда не может измениться). Принимая во внимание сегодняшнюю доступность ОЗУ, если результат функции зависит только от таких неизменяемых данных, разумно запоминать ее, а не перечитывать каждый раз, когда это необходимо. В настоящее время я (в Scala и С#) вручную вводит таблицу хранения в памяти и записываю 3 функции вместо одного - считывая значение из файла /db/ws, один из которых хранит его в таблице памяти, один обернуть их и прочитать из памяти, если они доступны, или вызвать функцию raw, если нет. Я думаю, что это может и должно быть реализовано как ключевое слово и сделано за кулисами.

Ответ 11

Для того, чтобы memoization работала как функция языка, было бы пара требований.

• Компилятор должен будет идентифицировать допустимые функции для memoization (например, они являются ссылочными прозрачными).
• Время выполнения должно было бы разумно выбирать кандидатов для заметок, не замедляя общую производительность.

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

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