Haskell кеширует результаты функции

Question

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

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

Я искал Data.Array и, хотя массив ленив, мне нужно инициализировать его списком пар (используя listArray) - что нецелесообразно. Если «ключ», например, тип 'Double', я вообще не могу его инициализировать, и даже если я теоретически могу назначить целое число каждому возможному входу, у меня есть несколько десятков тысяч возможных входов, и я на самом деле использую лишь несколько. Мне нужно инициализировать массив (или, желательно, хеш-таблицу, так как будет использоваться только несколько результатов), используя функцию вместо списка.

Обновление: я читаю статьи с заметками и, насколько я понимаю, MemoTrie может работать так, как я хочу. Может быть. Может ли кто-нибудь попытаться создать функцию cachedFunction? Предпочтительно для медленной функции, которая принимает 2 двойных аргумента? Или, альтернативно, для этого требуется один аргумент Int в области ~ [0..1 млрд.], Который не будет использовать всю память?

Answer 1

Ну, есть Data.HashTable. Хеш-таблицы не всегда хорошо играют с неизменяемыми данными и ссылочной прозрачностью, поэтому я не думаю, что они могут найти широкое применение.

Для небольшого количества значений сохранение их в дереве поиска (например, Data.Map), вероятно, будет достаточно быстрым. Если вы можете смириться с каким-либо искажением ваших Double s, более надежным решением было бы использование трип-подобной структуры, такой как Data.IntMap; они имеют время поиска, пропорциональное в первую очередь длине ключа, и примерно постоянное в размере коллекции. Если Int слишком ограничен, вы можете покопаться в Hackage, чтобы найти три библиотеки, более гибкие в типе используемого ключа.

Что касается того, как кешировать результаты, я думаю, что то, что вы хотите, обычно называется "памятка" . Если вы хотите вычислять и запоминать результаты по требованию, суть метода состоит в том, чтобы определить индексированную структуру данных, содержащую все возможные результаты , таким образом, чтобы при запросе определенного результата он вызывал только вычисления, необходимые, чтобы получить ответ, который вы хотите. Распространенные примеры обычно включают в себя индексирование в список, но тот же принцип должен применяться к любой нестрогой структуре данных. Как правило, нефункциональные значения (включая бесконечные рекурсивные структуры данных) часто будут кэшироваться во время выполнения, но не в результатах функций, поэтому хитрость заключается в том, чтобы обернуть все ваши вычисления в определение верхнего уровня, которое не зависит от любых аргументов.

Редактировать: Пример MemoTrie, привет!

Это быстрое и грязное доказательство концепции; лучшие подходы могут существовать.

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

Обратите внимание на расширения GHC, используемые пакетом MemoTrie; надеюсь, это не проблема. Загрузите его в GHCi и попробуйте вызвать slow против memoSlow с чем-то вроде (10 ^ 6) или (10 ^ 7), чтобы увидеть его в действии.

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

Answer 2

См. памятка

Answer 3

В системе времени исполнения GHC есть ряд инструментов, явно поддерживающих запоминание.

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

Вы можете найти оригинальную запись 1999 года полезной, поскольку она включает несколько реализаций в качестве примеров:

Растяжение диспетчера хранилища: слабые указатели и стабильные имена в Haskell Саймон Пейтон Джонс, Саймон Марлоу и Конал Эллиот

Answer 4

Я добавлю свое собственное решение, которое также кажется довольно медленным. Первый параметр - это функция, которая возвращает Int32 - уникальный идентификатор параметра. Если вы хотите однозначно идентифицировать его с помощью различных средств (например, с помощью «id»), вы должны изменить второй параметр в H.new на другую хеш-функцию. Я попытаюсь выяснить, как использовать Data.Map и проверить, получу ли я более быстрые результаты.

import qualified Data.HashTable as H
import Data.Int
import System.IO.Unsafe

cache :: (a -> Int32) -> (a -> b) -> (a -> b)
cache ident f = unsafePerformIO $ createfunc
    where 
        createfunc = do
            storage <- H.new (==) id
            return (doit storage)

        doit storage = unsafePerformIO . comp
            where 
                comp x = do
                    look <- H.lookup storage (ident x)

                    case look of
                        Just res -> return res
                        Nothing -> do
                            result <- return (f x)
                            H.insert storage (ident x) result
                            return result

Answer 5

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

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *)
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *)
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *)
val result2 = computeComplicatedThingFast 2.81
val result3 = computeComplicatedThingFast 2.91

Answer 6

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

Я бы пошел с listArray (start, end) (map func [start..end])

• func на самом деле не вызывается выше. Haskell ленив и создает thunks, которые будут оцениваться, когда значение действительно требуется.
• При использовании обычного массива вам всегда нужно инициализировать его значения. Таким образом, работа, необходимая для создания этих блоков, в любом случае необходима.
• Несколько десятков тысяч - это далеко не много. Если у вас триллионы, я бы предложил использовать хеш-таблицу yada yada

Answer 7

Я не знаю конкретно haskell, но как насчет сохранения существующих ответов в некоторой хешированной структуре данных (может быть названа словарем или hashmap)? Вы можете обернуть вашу медленную функцию в другую функцию, которая сначала проверяет карту и вызывает медленную функцию, только если она не нашла ответа.

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