quinta-feira, 16 de julho de 2009

ICFP2009 - estrutura de dados

Uma das partes mais importantes em um programa em linguagem funcional é a escolha da estrutura de dados. Isto, principalmente, pois acesso direto a memória fere a pureza da linguagem.

Para o ICFP2009, escolhi um IntMap como estrutura de dados. A escolha foi baseada no fato que a implementação do IntMap possui busca e inserção (que também funciona como modificação) em O(n), mas limitado por um fator constante O(32).

Se tivesse usado um Map comum, teria inserções e buscas em O(log n). Um array, mutável ou não, ofereceria inserção em O(n) e busca em O(1). Como temos 2 vezes mais buscas que inserções (a maior parte das instruções é binária), teriamos O(n+2), que é sempre pior que o O(3 log n) do Map, e muito pior que o O(32) do pior caso do IntMap.


{-# LANGUAGE BangPatterns #-}
module OBFData where

import qualified Data.IntMap as M


type OBFData=M.IntMap Double

singleton::Int->Double->OBFData
singleton=M.singleton

insert::Int->Double->OBFData->OBFData
insert !k !a !m=M.insert k a m

union::OBFData->OBFData->OBFData
union=M.union

fromList::[(Int,Double)]->OBFData
fromList=M.fromList

toList=M.toList

(!-!) :: M.IntMap Double -> Int -> Double
(!-!) = flip (M.findWithDefault 0.0)
infixl 9 !-!


Peço ao leitor que note algumas coisas:

  1. Estou forçando os tipos da estrutura de dados. Faço isso pois não tenho a necessidade de que essa estrutura de dados permaneça polimórfica. Se assim fosse, poderia usar IntMap diretamente.
  2. Uso bang patterns nos argumentos da chamada de insert. Faço isso para que não se acumulem thunks dentro do IntMap, o que seria péssimo para o desempenho
  3. Implementei um operador que retorna 0.0 caso acesse uma posição de memória não inicializada. Isto evita que eu tenha que criar o IntMap com as 16384 entradas preenchidas de cara.

Espero ter surpreendido, sim, pela simpliciade. Muito pior que fazer a estrutura, é a escolha de qual utilizar. A programação funcional força o programador a pensar no algoritmo mais eficiente, ao invés de pensar em hacks para tornar o código mais rápido.
Para quem quiser se aprofundar em estruturas de dados funcionais, sugiro dar uma lida no livro "Purely functional data structures" de Chris Okasaki, que desbrava as estruturas de dados neste universo imutável.

PS: Pensei também em amortizar o custo das inserções, mas acho que não é possível, pois todos os acessos de consulta são intercalados às buscas.

Nenhum comentário:

Postagens populares