Home
 

24 dias de Hackage, 2015 - dia 18 - vector, vector-algorithms: Libere seu alter-programador C

por Franklin Chen

traduzido por Pedro Yamada

Esse é um artigo escrito por Franklin Chen e traduzido para o português. Ler original.

Encontro HaskellBR São Paulo

Vamos nos encontrar em São Paulo em 25 de Janeiro de 2016. Marque sua presença e comente se não puder vir.

Índice de toda a série

O índice de toda a série está no topo do artigo para o dia 1.

Dia 18

(Discussão no Reddit)

É comum em programação, que a estrutura de dados a ser usada é um array estilo C, seja ele tratado como mutável ou imutável.

Idealmente, eu não teria que escrever esse artigo, mas eu tenho a impressão de que muitos recem chegados ao Haskell não sabem sobre o vector, a biblioteca para arrays estilo C, e usam listas onde arrays se encaixariam melhor no problema. Arrays são eficientes para indexar e também são eficientes quanto ao cache da CPU e a memória, sendo alocados em um bloco de memória, ao invés de espalhados por meio de um monte de ponteiros.

A terminologia usada para arrays no ecossistema do Haskell é confusa porque Haskell, nos anos 90, originalmente veio com uma estrutura de dados chamada Array, e há até um pacote array, mas na prática eu nunco o uso porque ele é mais genérico e estranho que a estrutura de dados simples exposta mais tarde chamada “vetores” [N.T. “vectors”] (pela falta de um nome melhor).

Há bons tutoriais sobre o vector que eu recomendo:

Achei que seria útil dar um exemplo completo de usar vetores imutáveis e mutáveis. Em particular, vamos usar vetores unboxed que são especializados e, portanto, não contém nenhuma indireção e são basicamente equivalentes aos arrays estilo C. Vamos fazer um pouco de programação de baixo nível estilo C.

O problema a ser resolvido: encontrar a mediana de um array de inteiros de 8-bits

Aqui está um problema encontrado no Programming Praxis:

A mediana de um array é o valor no meio se o array estivesse ordenado: se o array tiver um número impar de items n, a mediana é o (n+1)/2nth maior item no array (que também é o (n+1)/2nth menor item no array), e se o array tiver um número par de items n, a mediana é a média aritmética do n/2th menor item e do n/2th maior item no array. Por exemplo, a mediana do array [2,4,5,7,3,6,1] é 4 e a mediana do array [5,2,1,6,3,4] é 3.5.

Sua tarefa é escrever um programa que recebe um array de inteiros de 8-bits (possivelmente mas não necessariamente ordenados) e encontra o valor da mediana do array; você deve encontrar um algoritmo que tome tempo linear e espaço constante.

Instalação do vector

O Stackage LTS ainda está no vector-0.10, mas eu queria usar a versão 0.11 porque a API mudou um pouco, então eu adicionei uma restrição de versão apropriada ao arquivo Cabal.

A importância de ir unboxed

Já que temos que escrever código específico a um array de inteiros de 8-bits, vamos usar vetores unboxed ao invés de boxed (genéricos): vetores boxed contém elementos que são ponteiros para valores, enquanto os unboxed tem elementos que são os próprios valores. Isso é importante para a eficiência, se você sabe de cara qual é o valor dos seus elementos.

Alguns testes

Vamos escrever alguns testes antes de mais nada, assumindo que vamos escrever um módulo VectorExample.

Primeiro, alguns imports. Nós vamos usar o operador de indexing em tempo constante para vetores !.

module VectorExampleSpec where

import VectorExample
       ( Value, MedianValue, averageValue
       , spaceInefficientMedian, constantSpaceMedian
       )

import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Radix as Radix

Vamos usar HSpec e QuickCheck, e escrever nossos próprios geradores de vetores aleatórios:

import Test.Hspec (Spec, hspec, describe, it, shouldBe)
import Test.Hspec.QuickCheck (prop)
import Test.QuickCheck (Arbitrary(arbitrary, shrink), choose, sized, shrinkList)

Vamos implementar tanto uma versão simples de referência e a inteligente desejada, então vamos estar ambas:

spec :: Spec
spec = do
  describe "compute median of vector of 8-bit unsigned integers" $ do
    medianSpec "inefficientSpaceMedian" inefficientSpaceMedian
    medianSpec "constantSpaceMedian" constantSpaceMedian

Testamos os exemplos fornecidos, assim como propriedades genéricas. Para ordenamento, nós convenientemente usamos a ordenação radix do pacote vector-algorithms:

medianSpec :: String
            -> (V.Vector Value -> Maybe MedianValue)
            -> Spec
medianSpec description findMedian =
  describe description $ do
    describe "some examples" $ do
      it "handles odd number of elements" $ do
        findMedian (V.fromList [2, 4, 5, 7, 3, 6, 1]) `shouldBe` Just 4.0
      it "handles nonzero even number of elements" $ do
        findMedian (V.fromList [5, 2, 1, 6, 3, 4]) `shouldBe` Just 3.5
    describe "properties" $ do
      it "handles no elements" $ do
        findMedian V.empty `shouldBe` Nothing
      prop "handles one element" $ \v ->
        findMedian (V.singleton v) == Just (fromIntegral v)
      prop "handles odd number of elements" $
        \(VectorWithOdd values) ->
          let len = V.length values
              midIndex = pred (succ len `div` 2)
              sorted = V.modify Radix.sort values
          in findMedian values == Just (fromIntegral (sorted ! midIndex))
      prop "handles positive even number of elements" $
        \(VectorWithPositiveEven values) ->
          let len = V.length values
              midIndex = pred (succ len `div` 2)
              sorted = V.modify Radix.sort values
          in findMedian values ==
            Just (averageValue (fromIntegral (sorted ! midIndex))
                               (sorted ! succ midIndex))

Os testes de propriedades especificam o que a mediana deve ser, para todos os casos possíveis.

Uma nota sobre mutação

A ordenação radix opera sobre vetores mutáveis, mas estamos usando um vetor função modify que tem um tipo pomposo:

modify :: Unbox a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a

Ela recebe um callback que recebe um vetor mutável e transforma um vetor imutável em outro vetor imutável (possivelmente o mesmo vetor mutado “secretamente” por baixo dos panos). Usa tipos de alta ordem e o monad transformer de estado ST, mas tudo o que você tem de saber é que Radix.sort tem um tipo compatível de callback e pode portanto ser composto com modify:

sort :: forall e m v. (PrimMonad m, MVector v e, Radix e) => v (PrimState m) e -> m ()

Geradores customizados do QuickCheck

Aqui estão alguns geradores rápidos de vetores do tipo que queremos para os testes. Se estivéssemos fazendo isso de verdade, provavelmente gostariamos de escrever shrinkers customizados, ao invés de percorrer listas.

-- | Gene um vetor com um número impar de elementos.
newtype VectorWithOdd a =
  VectorWithOdd { getVectorWithOdd :: V.Vector a }
  deriving (Show)

instance (Arbitrary a, V.Unbox a) => Arbitrary (VectorWithOdd a) where
  arbitrary = sized $ \n -> do
    k <- choose (0, n `div` 2)
    VectorWithOdd <$> V.replicateM (2*k+1) arbitrary
  shrink = map (VectorWithOdd . V.fromList)
           . shrinkList shrink
           . V.toList
           . getVectorWithOdd

-- | Gere um vetor não vazio com um número par de elementos.
newtype VectorWithPositiveEven a =
  VectorWithPositiveEven { getVectorWithPositiveEven :: V.Vector a }
  deriving (Show)

instance (Arbitrary a, V.Unbox a) => Arbitrary (VectorWithPositiveEven a) where
  arbitrary = sized $ \n -> do
    k <- choose (1, 1 `max` (n `div` 2))
    VectorWithPositiveEven <$> V.replicateM (2*k) arbitrary
  shrink = map (VectorWithPositiveEven . V.fromList)
           . shrinkList shrink
           . V.toList
           . getVectorWithPositiveEven

Uma versão ineficiente que viola o requisito de espaço

Para referência (nós podíamos quase ler a partir dos testes do QuickCheck):

{-# LANGUAGE BangPatterns #-}

module VectorExample where

import qualified Data.Word as Word
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M
import qualified Data.Vector.Algorithms.Radix as Radix

-- | Assuma um inteiro unsigned de 8-bits
type Value = Word.Word8

-- | O que retornar como a mediana, se existir
type MedianValue = Double

-- | A implementação óbvia; basicamente a especificação. O uso da ordenação
-- radix toma tempo linear, mas uma cópia do array original é necessária.
inefficientSpaceMedian :: V.Vector Value -> Maybe MedianValue
inefficientSpaceMedian values
  | V.null values = Nothing
  | odd len = Just (fromIntegral (atSorted midIndex))
  | otherwise = Just (averageValue (atSorted midIndex)
                                   (atSorted (succ midIndex)))
  where
    len = V.length values
    midIndex = pred (succ len `div` 2)

    -- Faz uma cópia local mutável para ordenar
    atSorted = V.unsafeIndex (V.modify Radix.sort values)

-- | A média de dois valores
averageValue :: Value -> Value -> MedianValue
averageValue a b = (fromIntegral a + fromIntegral b) / 2

Uma nota sobre operações unsafe

Eu prometi que iríamos fazer programação estilo C. Poderíamos usar indexing com um bounds-check (que atira uma exceção durante runtime quando acessamos elementos que não estão em um vetor), mas vamos nos “divertir” um pouco, e usar o unsafeIndex. Note que isso é inseguro mesmo: vamos pegar o centésimo elemento de um vetor com 1 Int:

Data.Vector.Unboxed> unsafeIndex (singleton (5 :: Int)) 100
4931475852

Porque usar operações unsafe? Para ilustração e também porque acontece de que podemos provar (fora do type system) que nós nunca vamos tentar acessar um elemento fora do vetor. Na vida real, eu hesitaria em usar operações unsafe a não ser que ter a performance máxima fosse crítico! Mas nós podemos nos candidatar ao mundo de desastres em potencial do C se quisermos.

Não quero promover usar operações unsafe!! Substitua todas as funções de hoje chamadas unsafeXyz por xyz para ficar tranquilo.

Uma solução inteligente

A função inteligente aloca uma tabela de todas as contegens possíveis (porque sabemos que os valores são inteiros unsigned de 8-bits) e a preenche, então itera pela tabela e descobre onde a mediana deve estar, e quando bate no lugar certo, retorna o valor do meio (se tiver um número impar de valores) ou o meio de dois valores (se tiver um número par de valores).

-- | O número de ocorrências de um inteiro de 8-bits unsigned.
-- Assumimos que não overflow além dos limites de um 'Int'.
type CountOfValue = Int

-- | Create a table of counts for each possible value, since we know
-- the number of values is small and finite.
-- | Crie uma tabela de contagens para cada valor possível, já que sabemos que
-- o número de valores é pequeno e finito.
constantSpaceMedian :: V.Vector Value -> Maybe MedianValue
constantSpaceMedian values
  | V.null values = Nothing
  | odd len = Just (findMid 0 (numToCount - countOf 0))
  | otherwise = Just (findMid2 0 (numToCount - countOf 0))
  where
    len = V.length values

    -- Quantos elementos ordenados que precisamos contar, para chegar ao
    -- primeiro valor mediano.
    numToCount = succ len `div` 2

    -- Crie a tabela de contagens para cada valor possível.
    countOf = V.unsafeIndex (makeCountsMutably values)

    findMid !i !numRemaining
      | numRemaining <= 0 = fromIntegral i
      | otherwise = findMid (succ i) (numRemaining - countOf (succ i))

    findMid2 !i !numRemaining =
      case numRemaining `compare` 0 of
        LT -> fromIntegral i -- median is duplicated, don't need average
        GT -> findMid2 (succ i) (numRemaining - countOf (succ i))
        EQ -> midAverage (succ i) (countOf (succ i))
          where
            midAverage j 0 = midAverage (succ j) (countOf (succ j))
            midAverage j _ = averageValue (fromIntegral i) (fromIntegral j)

Note o uso da extensão do GHC BangPatterns, coberta em um dia de extensões do GHC de 2014, para nos assegurarmos da avaliação estrita em loops recursivos “pela cauda” (tail-recursive loops).

Formas mutáveis e imutáveis de criar a tabela de contagens

O que é makeCountsMutably?

Mutável

A versão da função que usa mutação usa a função create:

-- | Use local mutation for efficiency in creating a table of counts,
-- looping through to update it, and freezing the result to return.
-- | Use mutabilidade local para eficiência em criar uma tabela de contagens,
-- fazendo um laço para a atualizar e congelando o valor retornado.
makeCountsMutably
  :: V.Vector Value        -- ^ values seen
  -> V.Vector CountOfValue -- ^ value => count
makeCountsMutably values = V.create $ do
  counts <- M.replicate numPossibleValues 0
  V.forM_ values $
     M.unsafeModify counts succ . fromIntegral
  return counts

-- | 256, no nosso caso.
numPossibleValues :: Int
numPossibleValues = fromIntegral (maxBound :: Value) + 1

create tem tipo:

create :: Unbox a => (forall s. ST s (MVector s a)) -> Vector a

E inteligentemente “congela” o vetor retornado no lugar, dentro do contexto do monad ST, em um vetor imutável, o que evita qualquer cópia, porque a mutação acontece dentro do callback e não é visível fora dele.

Imutável

Mas espere, também há uma forma de criar a tabela usando somente Vectors imutáveis, sem nenhum vetor MVector intermediário!

-- | Crie a tabela de contagens sem usar 'MVector'.
makeCountsPurely
  :: V.Vector Value
  -> V.Vector CountOfValue
makeCountsPurely =
  V.unsafeAccumulate (+) (V.replicate numPossibleValues 0)
  . V.map (\v -> (fromIntegral v, 1))

Isso é elegante de direto, mas parece criar um vetor intermediário usando map, que não é o que queremos já que todo o ponto é ter eficiência de espaço.

Fusion

Acontece que o vector vem com sofisticado suporte para fusion.

Um dia de Hackage posterior (agora disponível no dia 19) vou esplicar o que acontece nos bastidores. Efetivamente, o GHC reescreve as chamadas para unsafeAccumulate e map para evitar o vetor intermediário!

Conclusão

Arrays de tamanho fixo são uma peça importante para a construção muitas computações. Uso o vector quando preciso fazer operações (sequenciais) sobre arrays. Espero que esse pequeno exemplo mostre como escrever código imperativo baseado em vetores em Haskell, escondendo a maior quantidade de estado possível, por meio de APIs orientadas a tipos que operam entre os dois mundos da mutabilidade e imutabilidade. É até possível escrever código que dependa no fusion e não crie vetores mutáveis intermediários.

(Esses são arrays sequenciais. Para arrays paralelos, veja um dia de Hackage de 2013, que cobriu o repa, uma biblioteca para “arrays paralelos de alta performance, regulares, multi-dimensionais e polimórficos”.)

Todo o código

Todo o código para a série estará nesse repositório do GitHub.

Nota do tradutor

Se você quer ajudar com esse tipo de coisa, agora é a hora. Entre no Slack ou no IRC da HaskellBR e contribua. Esse blog e outros projetos associados estão na organização haskellbr no GitHub e em haskellbr.com/git.

Há um milestone no GitHub com tarefas esperando por você..

Share Comente no Twitter