Может ли memoizing возможно без побочных эффектов

У меня есть код F #, который кэширует результаты для будущего поиска. Я понимаю, что словари и другие структуры данных, которые вы добавляете, требуют побочных эффектов. (т. е. изменение состояния словаря). Правильно ли это? Это считается нечистым или это все еще находится в модели свободного вычисления свободных побочных эффектов.Может ли memoizing возможно без побочных эффектов

let rec fib = 
    let dict = new System.Collections.Generic.Dictionary<_,_>() 
    fun n -> 
     match dict.TryGetValue(n) with 
     | true, v -> v 
     | false, _ -> 
      let fibN = 
       match n with 
       | 0 | 1 -> n 
       | _ -> fib (n - 1) + fib(n - 2) 
      dict.Add(n, fibN) 
      fibN

источник

2015-05-26 t3dodson

Мое F # может быть немного ржавым, но я не вижу, как последовательные вызовы 'fib' могут делиться экземпляром' dict' для обеспечения кэширования. Не будет ли каждый вызов функции получить свой собственный экземпляр 'dict'? – CoderDennis

@CoderDennis Его закрытие над dict. Слово fib связано с функцией lamda, которая выполняет логику. Каждый вызов разделяет привязку dict – t3dodson

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

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

let memoize f = 
    let dict = new System.Collections.Generic.Dictionary<_,_>() 
    fun x -> 
     match dict.TryGetValue(n) with 
     | true, v -> v 
     | false, _ -> 
      let v = f x 
      dict.Add(x, v) 
      v

Делая это, вы на самом деле можете сделать memoized function pure и memoization деталь реализации. Код, который вы опубликовали, где эти две проблемы запутались, не так прост в рассуждении, насколько это возможно.

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

Отдельная проблема здесь - проблемы параллелизма, с которыми вы можете столкнуться. Для борьбы с теми, вы можете либо иметь блокировку вокруг dict.Add:

... 
let v = f x 
lock dict <| fun() -> 
    if not <| dict.ContainsKey(x) then 
     dict.Add(x, v) 
v

или вместо Dictionary не имеют ref клеток, держащего Map (в этом случае какие-либо вопросы, параллелизм вы, возможно, все еще есть, но уже не катастрофический характер).

источник

2015-05-27 00:33:39 scrwtp

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

Чтобы отправить комментарий о сохранении неправильного значения в dict; да, вы правы, но есть еще одна проблема, которая не связана с неправильными результатами. Класс Dictionary не является потокобезопасным. Если два потока пытаются читать и/или записывать в словарь одновременно, вы, скорее всего, получите исключение. Например:

let data = [| 1 .. 20 |] 
let fibs = data |> Array.Parallel.map fib

я не получил каких-либо исключений, когда я управлял этим, несколько раз, в F # интерактивной, но с некоторыми изменениями, я получил System.ArgumentException:

Элемент с тот же ключ уже добавлен.

Изменения были этими; в каждом конкретном случае, я получил исключение на первую или вторую попытке:

Instrument функция для печати диагностической информации при помощи printfn
Изменения числового типа в uint64 (удаление printfn диагностика)
Измени числовые типа в float (т.е. System.Double)
Изменение числового типа в bigint

источник

2015-05-26 22:12:04 phoog

Может ли memoizing возможно без побочных эффектов

ответ

Смежные вопросы