Skip to content

Latest commit

 

History

History
501 lines (413 loc) · 21 KB

README.org

File metadata and controls

501 lines (413 loc) · 21 KB
Raw

Matrizes

Este documento se refere aos exercícios da LE1, segunda lista, que pode ser encontrado neste documento.

AVISO

Para questões de comparações práticas, implementei os mesmos algoritmos nas suas versões usando Listas Encadeadas e outra usando Unboxed Arrays, que basicamente são Arrays como em C, porém imutáveis!

Em Haskell temos dois tipos de Arrays:

  1. Boxed Arrays
  2. Unboxed Arrays

Boxed Arrays

Essa estrutura é implementada como todas as outras em Haskell: de forma lazy, ou seja os elementos apenas são computadas quando necessário!

Para cada valor nesse Array existe um ponteiro na memória! Isso é perfeito pois podemos definir os elementos de forma recursiva em termos um do outro, além de ser possível de criar um Array infinito.

Porém, caso o Array seja muito grande, o gasto de memória será muito grande e sua eficiência não será notada! Junto a isso, temos que a Estrutura de Dados Array geralmente é usada para grandes operações com diversos elementos, ou seja, o acesso por índice é extremamente necessário! Para isso, existem os Unboxed Arrays.

Unboxed Arrays

Essa estrutura se assemelha com os Arrays em C! O acesso por índice é significantevamente mais rápido.

Entretanto, há algumas desvantagens, como não ser possível usar tipos de dados compostos como valores. Exemplo: o tipo String é apenas uma lista de Char ([Char]). Apenas tipos únicos podem compor um Unboxed Array!

Outra desvantagem é que perdemos a característica laziness da linguagem, pois assim que um do elementos desse Array for computado, todos os outros também serão!

Esse tipo de Array se encaixa melhor para as implementações dos algoritmos já que sua eficiência pode ser comparada com os Arrays em C!

Implementação

Array

Criei um novo tipo, que representa um Umboxed Array! Cada Array em Haskell possui um limite mínimo e máxixo de posições, representados por uma 2-Tupla ou Par. Nesse caso é uma tupla de Inteiros.

type Elem = Int
type Arr = UArray

type Matriz = Arr (Int, Int) Elem

Para criar uma Matriz, criei duas funções:

  1. para converter a partir de uma lista
  2. para criar aleatoriamente

Na fromList eu uso a função listArray do módulo Data.Array.Unboxed que recebe os limites mínimos e máximos e uma lista e devolve um UArray que nesse caso é uma Matriz.

Como esse Array tem duas dimensões, o limite mínimo e máximo são Pares, arranjados da seguinte forma:

((minLinhas, minColunas), (maxLinhas, maxColunas))

fromList :: Int -> Int -> [Elem] -> Matriz
fromList i j = listArray ((0, 0),(i-1, j-1))

Já a função matriz, devolve uma Matriz com os valores aleatoriamente gerados. Porém, como Haskell é uma linguagem puramente funcional, ela obedece a Transparência Referencial, que diz que se uma função recebe os mesmos argumentos, ela irá retornar o mesmo resultado.

Dito isso, se eu criar duas Matrizes 2x2, essa função irá me retornar a mesma Matriz duas vezes! Para solucionar isso eu poderia fazer com que essa função recebesse uma seed diferente a cada chamada (passando por parâmetro), mas achei desnecessário para fins de testes.

matriz :: Int -> Int -> Matriz
matriz m n = fromList m n values'
  where format _ 0 _    = []
	format m' n' xs = (take m' xs) : format m' (n'-1) (drop m' xs)
	values          = format m n (take (m*n) (randomRs (3, 10) (mkStdGen (m*n))))
	values'         = concat values

Soma de Matrizes! Caso os limites sejam diferentes, eu devolvo um Array vazio, caso contrário crio um novo Array, porém somo cada elemento da Matriz A com seu correspondente na Matriz B, gerando uma Matriz C

somaMatriz :: Matriz -> Matriz -> Matriz
somaMatriz a b
  | bounds a /= bounds b = array ((0,0),(-1,0)) []
  | otherwise            = listArray (bounds a) $ zipW (+) xs ys
  where xs = elems a
        ys = elems b

Multiplicação de Matrizes! Essa foi um pouco mais complicada, porém, vamos lá:

Primeiro, verifico se o número máximo de colunas da Matriz A é diferente do número máximo de linhas da Matriz B! Se for, eu retorno um Array vazio.

Quando forem iguais, eu crio ranges ou “distância” do número mínimo de linhas e colunas de A e número de colunas de B, respectivamente.

Depois, crio uma compreensão de listas de duas dimensões (os elementos de Array são representados por uma lista, porém internamente eles são otimizados para agir como Arrays) e para cada liinha de A e colunas de B eu realizo a soma da multiplicação de cada elemento de A na posição (linhaA, colunaA) com seu correspondente elementos em B na posição (colunaA, colunaB).

multiplicaMatriz :: Matriz -> Matriz -> Matriz
multiplicaMatriz a b
  | y0' /= x1'   = array ((0,0),(-1,0)) []
  | otherwise    = array ((0, 0), (x0', y1')) resultado
    where ((x0, y0), (x0', y0')) = bounds a
	  ((_, y1), (x1', y1'))  = bounds b
	  linhasA                = range (x0, x0')
	  colunasA               = range (y0, y0')
	  colunasB               = range (y1, y1')
	  resultado              =
	    [ ((la, cb),
	       sum
	       [ a ! (la, ca) * b ! (ca, cb)
	       | ca <- colunasA
	       ])
	    | la <- linhasA
	    , cb <- colunasB
	    ]

Funções extras

Algumas funções para manipular Matrizes!

Funções para:

  1. Calcular a Matriz absoluta a partir de outra Matriz
  2. Negar uma Matriz
  3. Retornar todas as linhas de uma Matriz
  4. Retornas todas colunas de uma Matriz
  5. Criar a transposta de uma Matriz
  6. Imprimir uma Matriz formatada
absMatriz :: Matriz -> Matriz
absMatriz a = listArray (bounds a) $ map (abs) xs
  where xs = elems a

negateMatriz :: Matriz -> Matriz
negateMatriz a = listArray (bounds a) $ map (negate) xs
  where xs = elems a

linhas :: Matriz -> Int
linhas m = numLinhas + 1
  where (_, (numLinhas, _)) = bounds m

colunas :: Matriz -> Int
colunas m = numColunas + 1
  where (_, (_, numColunas)) = bounds m

transpose :: Matriz -> Matriz
transpose a = array (bounds a)
  [ ((linha, coluna), a ! (coluna, linha))
  | linha  <- [sl..el]
  , coluna <- [sc..ec]
  ]
  where ((sl, sc), (el, ec)) = bounds a

printMatriz :: Matriz -> IO ()
printMatriz m = putStrLn $ concat
   [ "┌ ", unwords (replicate (colunas m) blank), " ┐\n"
   , unlines
   [ "│ " ++ unwords (map (\j -> fill . show $ m ! (i,j)) [0..cols]) ++ " │" | i <- [0..lin] ]
   , "└ ", unwords (replicate (colunas m) blank), " ┘"
   ]
 where xs                   = elems m
       strings              = map (show) xs
       widest               = maximum $ map (length) strings
       fill str             = replicate (widest - length str) ' ' ++ str
       blank                = fill ""
       cols                 = (colunas m) - 1
       lin                  = (linhas m ) - 1

Funções de ajuda

Minha própria implementação da função zipWith, que aplica uma função ao mesmo tempo que junta duas listas!

zipW :: (a -> b -> c) -> [a] -> [b] -> [c]
zipW _ [] _          = []
zipW _ _ []          = []
zipW f (x:xs) (y:ys) = f x y : zipW f xs ys

Lista

Já para a implementação de Lista eu criei uma nova Estrutura dados (Pública) que representa uma Matriz! O Construtor M possui linhas e colunas do tipo Int e os valores são representados como uma lista de duas dimensões do tipo fornecido. Note que em Haskell, as funções linhas, colunas e valores são automaticamente implementadas!

Essa Matriz também deriva das classes de tipo Eq e Ord, ou seja, cada Matriz pode ser comparada com outras!

data Matriz a = M { linhas  :: Int
                  , colunas :: Int
                  , valores :: [[a]]
                  } deriving (Eq, Ord, Show, Generic, Generic1, NFData, NFData1)

Também defino algumas instâncias de outras classes de tipo:

  1. A classe de tipoe Foldable permite eu implementar as funções length, foldr e foldMap, porém, nesse caso, preciso apenas da length
  2. Fazer parte da classe de tipo Functor significa que essa estrutura pode ser mapeada, ou seja, transforma algo da categoria a para b. A função map é uma implementação da fmap da classe de tipo Functor, porém especializada em Listas.

    Essa instância permite que eu use fmap diretamente numa Matriz ao invés de eu ter que pegar os valores dela e mapear.

  3. Geralmente não devemos usar a instância da classe de tipos Show, porém, como os valores são representados por uma lista, decidi implementar essa instância.
  4. A instância princicpal! A classe de tipo Num permite que eu use os operadores (+), (*) entre outras funções! É nessa instância que defino as guard clauses, ou seja, decido se uma Matriz é válida para ser somada ou multiplicada.

    Também defino as funções abs, negate, que possuem a mesma finalidade que a absMatriz e negateMatriz na implementação com Arrays.

    Já função signum retorna 1 caso o número seja positivo, -1 se for negativo e 0 se o argumento for 0. Implementei ela para caso receba uma Matriz mXn ela retorne uma Matriz Identidade de m linhas e n colunas, a partir de uma lista infinita.

  5. Além das instâncias, derivo da classe de tipo Generic, de forma simplória, implementa uma instância genérica que possui duas funções: 
    class Generic a where
  -- Codifica a representação do tipo abstrato do usuário
  type Rep a :: * -> *
  -- Converte do tipo abstrato para a representação
  from  :: a -> (Rep a) x
  -- Converte da representação para o tipo abstrato
  to    :: (Rep a) x -> a

    Programação genérica em Haskell é muito mais profundo do que isso, e apenas utilizei pela facilidade que ela traz. Ainda preciso me aprofundar nisso.

    E a Generic1, é a variação que aceita parâmetros de tipos no ADT do usuário.

    Explicarei o porquê de precisar dela no decorrer deste documento.

  6. Também derivo da classe de tipo NFData tem a função de implementar a função rnf, que significa Reduce a value to Normal Form. Aqui vai uma breve explicação: Haskell é uma linguagem lazy, e, na prática, isso acontece: 
    #include <stdio.h>

int soma(int x, int y) {
  return x + y;
}

int main() {
  int cinco = soma(1 + 1, 1 + 2);
  int sete = soma(1 + 2, 1 + 3);

  printf("Cinco: %d\n", five);
  return 0;
}

    Neste trecho de código, o seguinte acontece:

    • Antes da função soma ser chamada, o programa computa o resultado de 1 + 1 e 1 + 2
    • Depois, chamamos a função com 2 e 3 como argumentos e 5 é devolvido, inserindo o valor no endereço de

memória em que a variável cinco aponta.

  • Fazemos o mesmo procedimento para a variável sete
  • Imprimimos na tela apenas a variável cinco

Vamos ver o mesmo códigom em Haskell:

soma :: Int -> Int -> Int
soma x y = x + y

main :: IO ()
main = do
  let cinco = soma (1 + 1) (1 + 2)
      sete = soma (1 + 2) (1 + 3)

  putStrLn $ "Cinco: " ++ show cinco

Aqui acontece o seguinte:

  • Ao invés de computar 1 + 1 e 1 + 2, o compilador vai alocar na memória uma referência ou “promesa” dessa computação

passar ela para a função soma

  • A variável cinco guarda uma promesa da computação de soma que guarda as promessas das duas computações anteriores
  • Quando finalmente imprimimos a variável cinco, ela é computada, o que desencadeia a computação da função soma, que

por consequência, computa 1 + 1 e 1 + 2

  • Por curiosidade, a variável sete não é computada em momento algum, então ela é descartada (:

Só que esse comportamento laziness ou “preguiçoso” me atrapalhou na hora de fazer as medições de tempo na soma e multiplicação das matrizes… Então precisei forçar a computação dos valores. Mas como todo conhecimento sempre tem suas dependências, vamos para mais uma explicação:

Em Haskell, podemos usar a função seq :: a -> b -> b, que recebe dois argumentos e devolve o segundo, porém ela força a computação dos dois. No caso, b só será computado se a também for! Mas tem um porém: o seq só computa o valor em WHNF Weak Head Normal Form. Exemplos práticos:

-- | só irá computar o cabeçalho da lista (1)
two = [1,2,3] `seq` 2

-- | Apenas irá computar a Mônada Maybe e remover o Just, o undefined não será computado...
maybeError = Just undefined `seq` 2

Por isso existe o deepseq, que irá forçar a computação, recursivamente da estrutura.

Derivando a classe de tipo NFData, a função rnf é implementada automaticamente para meu ADT Matriz, e a NFData1, tem a mesma finalidade que a Generic1: aceitar parâmetros de tipos!

instance Foldable Matriz where
  length (M _ _ xs) = length $ concat xs
  foldMap           = undefined
  foldr             = undefined

instance Functor Matriz where
 fmap f (M n m xs) = M n m (map (map f) xs)

instance Show m => Show (Matriz m) where
  show (M _ _ [])  = "[]"
  show m@(M _ _ _) = printMatriz m

instance Num a =>  Num (Matriz a) where
  (+) (M m n xs) (M m' n' ys)
    | m /= m'   = M 0 0 []
    | n /= n'   = M 0 0 []
    | otherwise = M m n (soma xs ys)

  fromInteger = undefined

  signum (M m n _)
    | m /= n    = M 0 0 []
    | otherwise = M m n (take m (take m <$> sign))

  abs (M m n xs) = M m n (map (map abs) xs)

  negate (M m n xs) = M m n (map (map negate) xs)

  (*) a@(M _ n _) b@(M m' _ _)
    | n /= m'   = M 0 0 []
    | otherwise = multiplica a b

Já a soma e a multiplicação, ao contrário da implementação com Arrays, recebem apenas os valores da Matriz, que são uma lista bidimensional!

A soma é tão simples quanto compor a função zipW, passando como argumento os valores da Matriz A e Matriz B (veja na instância da classe de tipo Num).

Na função multiplica, uso outro algoritmo: crio a transposta de B e mapeio os valores de A aplicando uma função que mapeia cada coluna fazendo a multiplicação de cada coluna da transposta de B e depois somo todos os valores.

Isso significa que tenho dois loop:

  1. aplica uma função em cada coluna de A
  2. para cada coluna de A, mapeio as colunas da transposta de B
  3. uso a zipW para multiplicar, a partir de uma closure as linhas de A e B
  4. por fim, somo a lista multiplicada

closure: uma função que encapsula o escopo acima dela, ou seja, ela “lembra” do estado anterior.

soma :: Num a => [[a]] -> [[a]] -> [[a]]
soma = (zipW . zipW) (+)

multiplica :: Num a => Matriz a -> Matriz a -> Matriz a
multiplica (M m _ xs) b@(M _ n _) = M m n resultado
  where (M _ _ tys) = transpose b
	dot x y     = sum $ zipW (*) x y
	resultado   = map (\col -> map (dot col) tys) xs

Funções extras

Basicamente as mesmas funções da implementação com Arrays, porém modificadas para aceitar a Estrutura de Dados Matriz

transpose :: Num a => Matriz a -> Matriz a
transpose (M m n [])           = M m n []
transpose (M m n ([]:xss))     = transpose (M m n xss)
transpose (M m n ((x:xs):xss)) = M m n (hd:ys)
  where hd         = (x : [h | (h:_) <- xss])
	(M _ _ ys) = transpose (M m n (xs : [t | (_:t) <- xss]))

printMatriz :: Show a => Matriz a -> String
printMatriz m = concat
   [ "┌ ", unwords (replicate (colunas m) blank), " ┐\n"
   , unlines
   [ "│ " ++ unwords (fmap (\j -> fill $ strings ! (i,j)) [1..colunas m]) ++ " │" | i <- [1..linhas m] ]
   , "└ ", unwords (replicate (colunas m) blank), " ┘"
   ]
  where strings@(M _ _ v) = fmap show m
        widest            = maximum $ fmap length v
	fill str          = replicate (widest - length str) ' ' ++ str
        blank             = fill ""

Funções de ajuda

Tirando a zipW, temos novas funções de apoio!

  1. sign -> cria uma lista infinita na qual representa uma Matriz Identidade
  2. (!) -> crio um novo operador, para acessar o elemento da posição (i, j) de uma lista bidimensional
  3. encode -> um pequeno cálculo para tornar o uso do operador (!!) mais seguro, sem exeções
sign :: Num a => [[a]]
sign = (1:repeat 0) : fmap (0:) sign

(!) :: Matriz a -> (Int,Int) -> a
(!) (M _ n xs) (i, j) = v !! (encode n (i, j))
  where v = concat xs

encode :: Int -> (Int,Int) -> Int
encode m (i,j) = (i - 1) * m + j - 1

zipW :: (a -> b -> c) -> [a] -> [b] -> [c]
zipW _ [] _          = []
  zipW _ _ []          = []
zipW f (x:xs) (y:ys) = f x y : zipW f xs ys

Medidores

Funções para medir o tempo de cada operação!

Funciona da seguinte maneira:

  1. crio um novo “cronômetro” com a função start, que devolve uma Ref envolvida pela Mônada IO.
  2. para cada “checkpoint”, ou seja, cada momento que eu preciso delimitar e gravar o tempo, uso a função timerc.
  3. depois, uso a getVals - passando o resultado de start - que retorna todos os valores gravados a partir de timerc.
  4. passo o resultado de getVals para o timert que formata e devolve todos os checkpoints com o tempo calculado.
start :: IO (IORef [a])
start = newIORef []

getVals :: IORef a -> IO a
getVals = readIORef

timert :: [(String, T.UTCTime)] -> [String]
timert (_:[]) = error "1???"
timert ([]) = error "2???"
timert ((s,x):b@(s',y):z) = ((pure $ mconcat [s, " -> ", s', ": ", show (T.diffUTCTime y x)]) ++) $ case z of
			   [] -> []
			   zz -> timert (b : zz)

timerc :: IORef [(String, T.UTCTime)] -> String -> IO ()
timerc vr s = do
  vvv  <- readIORef vr
  vvv' <- timerb s vvv
  writeIORef vr vvv'

Resultados

Aqui apresento as tabelas com os resultados de tempo e número de operações para cada implementação

Array

Tamanho /n/Soma de MatrizesMultiplicação de Matrizes
Tempo (ms)N° Oper.Tempo (ms)/N° Oper.
1003.24624x10^414.04661x10^5
30029.378336x10^4542.89519x10^5
50053.60581x10^62854.719125x10^5
1000124.81104x10^629771.69011x10^7

Na soma eu realizo essas operações:

  1. extrair elementos da Matriz A
  2. extrair elementos da Matriz B
  3. somar os elementos
  4. criar Matriz C

Já na multiplicação eu realizo 10 operações:

  1. os limites de A
  2. os limites de B
  3. as linhas de A
  4. as colunas de A
  5. as colunas de B
  6. a soma dos resultados
  7. acesso por index Matriz A
  8. acesso por index Matriz B
  9. multiplição
  10. criação da nova Matriz C

Lista

Tamanho /n/Soma de MatrizesMultiplicação de Matrizes
Tempo (ms)N° Oper.Tempo (ms)/N° Oper.
10014.11992x10^458.741720200
30063.277218x10^41007.2398180600
500153.60675x10^54938.1908501000
1000590.90472x10^643807.41362002000

Percebemos que apenas pelo fato de usarmos uma Estrutura de Dados como uma Lista Encadeada, o tempo exigido chega a ser incalculável!

Mesmo que na soma o número de operações seja menor do que em Arrays, o acesso a cada elemento é mais demorado, pois os elementos no são gravados continuamente na memória!

Já na multiplicação, mesmo eu realizando a transposta de cada lista, o número de operações também é menor, entretanto, sofre da mesma desvantagem de acesso das Listas Encadeadas!

Referências