Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

fnds

"Cache" em Haskell

Recommended Posts

fnds

Boas.

Estou a resolver um problema em que precisava de fazer cache de determinados valores para evitar executar a mesma função com os mesmos argumentos várias vezes, se fosse noutra linguagem criava uma lista/array/dicionario e colocava lá os valores, mas em Haskell não estou a ver.

Já estive a ler sobre memoization (http://www.haskell.org/haskellwiki/Memoization) mas sinceramente, não percebi nada.

Cumprimentos.

Share this post


Link to post
Share on other sites
Rui Carlos

O compilador normalmente já faz esse tipo de optimizações.

Como o Haskell é uma linguagem funcional, o resultado de uma função aplicada aos mesmos argumentos é sempre o mesmo, por isso ele sabe que os podes guardar (embora nunca se saiba quando ele os está mesmo a guardar).

A alternativa será as funções receberem sempre um Map com os valores previamente calculados, e antes de tudo começar por ver se o valor que se quer já está no map.

É claro que isto torna a funções um pouco menos elegantes porque precisas de acrescentar mais um argumento e um resultado (tipo, f::X->Y->Z  ----> f::Map (X,Y) Z->X->Y->(Map (X,Y) Z,Z)).

Para evitares isto, podes usar monads de estado, mas isto já é um assunto um pouco complexo.

Share this post


Link to post
Share on other sites
Rui Carlos

O Map é uma estrutura de dados do género de um dicionário (e que é usada para guardar a cache).

A implementação da função potência devia ficar mais ou menos isto:

-- sem cache
power1::Int->Int->Int
power1 x y=x^y

-- com cache
power2::Map (Int,Int) Int->Int->Int->(Map (Int,Int) Int,Int)
power2 cache x y=
  let tmp=lookup (x,y) cache
  in case tmp in
        Nothing -> (insert (x,y) x^y,x^y)  -- o valor não está na cache; calcular valor, colocá-lo na cache, e devolver valor e nova cache
        Just z -> (cache,z) -- o valor está na cache; devolver valor e cache antiga, visto que não foi modificada

-- 2^x+2^x+3^x+3^x
prog :: Int -> Int
prog x =
  let (c1,r1)=power2 empty 2 x   -- calcula e adiciona à cache
      (c2,r2)=power2 c1 2 x    -- já está na cache
      (c3,r3)=power2 c2 3 x    -- calcula e adiciona à cache
      (c4,r4)=power2 c4 3 x    -- já está na cache
  in r1+r2+r3+r4

-- fibonacci
fib_aux ::Map Int Int->Int->(Map Int Int,Int)
fib_aux cache x=
  let tmp=lookup x cache
  in case tmp in
        Nothing ->
          let (c1,fib1)=fib_aux cache (x-1)
              (c2,fib2)=fib_aux c1 (x-2)     -- aqui o valor deverá sempre vir da cache, pois ao calcular para x-1 vamos colocar na cache (c1) o valor para x-2
          in (insert x (fib1+fib2) c2,fib1+fib2)
        Just y -> (cache,y)

fib n=fib_aux empty n

Acabei por fazer também o fibonacci.

PS: Não testei o código :)

Share this post


Link to post
Share on other sites
Triton

Haskell :cheesygrin:

Não percebo nada da linguagem, mas estive a ver o código do Rui Carlos e parece fixe :)

Desculpa lá a invasão no tópico fnds :cheesygrin:


<3 life

Share this post


Link to post
Share on other sites
Betovsky

Por acaso estava/estou a escrever um artigo para a revista sobre programação dinâmica em Haskell. Infelizmente devido à falta de tempo ficou parado no tempo. Se puderes dá uma vista de olhos. Está inacabado mas já aborda o problema e tem o Fibonacci como exemplo.

http://wiki.portugal-a-programar.org/revistaprogramar:programacao_dinamica_em_haskell

É mais simples e menos poderoso que o uso do Map, pode ser que te ajude a compreender melhor.

Qualquer dúvida já sabes... :)


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
fnds

@triton

Na boa :)

Olha a linguagem é mesmo fixe, é muito fácil e rápido aprender o básico, enquanto não complicares é um espectáculo :)

Eu estava a resolver o tal problema em Python e como envolvia várias listas pensei "isto em Haskell era um mimo", fiz a mesma cena com 1/3 do código. Agora quando precisei da tal cache é que me lixei lol

@Rui Carlos

Já percebi a ideia, não percebi é o o porquê de usar o Map em vez de uma simples lista [(x,y), z].

O código não corre, mas não é grave.

@Betovsky

O que escreveste no artigo está exclarecedor, depois fala lá também dos exemplos que estão aqui http://www.haskell.org/haskellwiki/Memoization

Vou agora tentar usar os Arrays.

Share this post


Link to post
Share on other sites
Betovsky

Já percebi a ideia, não percebi é o o porquê de usar o Map em vez de uma simples lista [(x,y), z].

O problema de usar uma lista é devido à performance do lookup (O(n) pra lista; O(log n) pro Map).

No caso dos Arrays é O(1) só que estás limitado nos tipos a indexar a informação, ou seja, não dá para todos os casos...


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
Betovsky

E então? Sempre conseguiste por isso a funcionar?


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
fnds

Não acabei por desistir, estava a dar muito trabalho então resolvi o problema em Java.

O problema é este: http://code.google.com/codejam/contest/dashboard?c=188266#

A solução sem cache é muito simples em haskell.

Já agora a minha solução bruta:

import Text.Printf

main = do x<-getContents
         run x

--input/output
strToBase :: String -> Int
strToBase "2" = 2
strToBase "3" = 3
strToBase "4" = 4
strToBase "5" = 5
strToBase "6" = 6
strToBase "7" = 7
strToBase "8" = 8
strToBase "9" = 9
strToBase "10" = 10

parseInput :: String -> [[int]]
parseInput str = tail (map (\x-> map strToBase (words x)) (lines str))

printRes :: [[int]] -> Int -> IO()
printRes [] _ = return ()
printRes (l:ls) n = printf "Case #%d: %d\n" n (lowMultiBaseHappy l)
             >> printRes ls (n+1)

run :: String -> IO()
run str = printRes (parseInput str) 1

--calculate
dec2baseB :: Int -> Int -> [int]
dec2baseB 0 _ = []
dec2baseB n b = (n`mod`b: dec2baseB (n`div`b) b)

happiness :: Int -> Int -> [int] -> [int]
happiness n 2 ls = [1]
happiness n b ls | elem n ls = [0]
                | next==1 = [1]
                | otherwise = happiness next b (n:ls)
                where next = sum (map (^2) (dec2baseB n b))

isHappy :: Int -> Int -> Bool
isHappy n b | v==0 = False
           | v==1 = True
           where [v] = happiness n b []

multiBaseHappy :: Int -> [int] -> Bool
multiBaseHappy n ls = and (map (isHappy n) ls)

firstMultiBaseHappy :: Int -> [int] -> Int
firstMultiBaseHappy n bases | multiBaseHappy n bases = n
                           | otherwise = firstMultiBaseHappy (n+1) bases

lowMultiBaseHappy :: [int] -> Int
lowMultiBaseHappy bases = firstMultiBaseHappy 2 bases

Share this post


Link to post
Share on other sites
Betovsky

Usando o teu código como base.

import Prelude hiding (lookup)
import Text.Printf
import Data.Map hiding (map)

type HappySet = Map (Int,Int) HappyState
data HappyState = OK | NOK | Maybe

main = getContents >>= resolve

resolve = printRes 1 . run empty . parseInput

run :: HappySet -> [[int]] -> [int]
run  _   []    = []
run set (l:ls) = let (num, set') = seekHappy 2 l set
                in num : run set' ls

parseInput :: String -> [[int]]
parseInput = map (map read . words) . tail . lines

printRes :: Int -> [int] -> IO()
printRes _ [] = return ()
printRes n (l:ls) = printf "Case #%d: %d\n" n l >> printRes (n+1) ls

dec2baseB :: Int -> Int -> [int]
dec2baseB 0 _ = []
dec2baseB n b = (n`mod`b: dec2baseB (n`div`b) b)

seekHappy :: Int -> [int] -> HappySet -> (Int, HappySet)
seekHappy n bases h = fun $ isMultiBaseHappy n bases h
  where fun (check, h') | check = (n, h')
                        | otherwise = seekHappy (n+1) bases h'

isMultiBaseHappy n bases h = foldr fun (True, h) bases
  where fun   _  r@(False, set) = r
        fun base   (_    , set) = isHappy base n set

isHappy  _   1 set = (True, set)
isHappy base n set = case (lookup (base,n) set) of
                      Just OK    -> (True , set)
                      Just NOK   -> (False, set)
                      Just Maybe -> (False, set)
                      Nothing    -> let (check, set') = isHappy base next (insert (base,n) Maybe set)
                                    in if check then (True , insert (base, n) OK  set')
                                                else (False, insert (base, n) NOK set')
  where next = sum $ map (^2) $ dec2baseB n base


"Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !"

Sign on a computer system consultant's desk

Share this post


Link to post
Share on other sites
fnds

Obrigado Betovsky ;)

Vou analisar o teu código com calma e percebe-lo bem, é que ainda tenho *muito* haskell para aprender, ainda só sei o básico.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.