Запоминает ли Clojure оценку своих аргументов?

В Clojure, если я запомнил функцию, назовите ее f и вызвать это на спор a,

Если a является большим ленивым значением, запоминает ли возвращаемое значение на основе соответствия thunk, в отличие от форсирования оценки a и соответствие по результату?

Где thunk - это неоцененная часть ленивой последовательности.

Если это не так, есть ли встроенный способ получить такое поведение?

Спасибо!

Источник

2 ответа

Решение

Как утверждает Микера, memoize не обрабатывает бесконечные ленивые последовательности. Я добавляю этот ответ, чтобы дать краткое описание причин реализации этого (плюс две идеи для схем запоминания на основе идентичности, одна простая, другая более сложная). (Изменить: на самом деле существует простое общее решение на основе идентичности, см. Ниже.)

Почему это не работает

memoize использует хеш-карту для хранения сопоставления от аргументов до значений, а хеш-карты используют clojure.lang.Util/hasheq при определении, является ли объект одним из их ключей (кроме пустых карт, которые просто возвращают false). поскольку hasheqРеализация lazy seqs заставляет весь seq запрашивать у любой карты, является ли бесконечный ленивый seq одним из ее ключей, и заставляет его идти в бесконечный цикл, истощающий память. То же самое относится и к memoize,

Строго говоря, изначально карта является массивом карт. (В Clojure по соображениям эффективности маленькие карты обычно представляют собой карты массивов; если assoc'на карту массива, возвращаемое значение становится хеш-картой.) Однако непустые карты массива также не в состоянии обрабатывать бесконечные ленивые последовательности по аналогичной причине, включающей метод проверки эквивалентности.

Решение

System/identityHashCode возвращает что угодно hashCode возвратился бы для данного объекта, если бы он использовал реализацию по умолчанию (независимо от того, hashCode отменяется).

(defprotocol PWrapped
  (-unwrap [this]))
PWrapped

(defn wrap [o]
  (reify
    Object
    (hashCode [_] (System/identityHashCode o))
    PWrapped
    (-unwrap [_] o)))

;;; adapted from clojure.core/memoize, (C) Rich Hickey, EPL-licenced
(defn memoize
  "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."
  {:added "1.0"
   :static true}
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem (map wrap args))]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc (map wrap args) ret)
          ret)))))

Теперь вы можете сделать это (что не будет работать с обычным memoize):

user> (def r (lazy-cat (range 10000) (prn :foo) (range)))
#'user/r
user> (def f (memoize #(apply + (take 100 %))))
#'user/f
user> (f [1 2 3])
6
user> (f r)
4950

Оригинальное обсуждение альтернативных реализаций следует.

Я не думаю, что есть встроенное решение, использующее равенство указателей. Чтобы реализовать такой общий как memoizeВы должны реализовать структуру карты, используя хэширование на основе равенства указателей (а именно: System/identityHashCode). Или вы можете создать простой "последний использованный" кеш с clojure.lang.PersistentQueue,

Источник

Memoize запомнит на основании значения любого аргумента, который вы ему передадите.

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

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

Источник
Другие вопросы по тегам