Результаты кэширования Haskell функции

Ответ 1

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

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

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

Изменить: Пример MemoTrie ahoy!

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

{-# 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 vs. memoSlow с чем-то вроде (10 ^ 6) или (10 ^ 7), чтобы увидеть его в действии.

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

Ответ 2

См. memoization

Ответ 3

Я добавлю свое собственное решение, которое тоже довольно медленное. Первый параметр - это функция, которая возвращает 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

Ответ 4

В системе времени выполнения GHK имеется ряд инструментов для поддержки memoization.

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

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

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

Ответ 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

Ответ 6

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

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

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

Ответ 7

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

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