Haskell - la conversione da Lista per Data.Vector

Question

Dopo profilatura mio programma Haskell, ho trovato che il 66% del tempo nel programma è speso indicizzazione in elenchi. La soluzione sembra utilizzare Data.Vector, ma ho problemi a convertire: quando cambio il codice per utilizzare un Vector, usa tonnellate e tonnellate di memoria e si blocca così male che non riesco nemmeno a definirlo. Cosa potrebbe causare questo?

Ecco il file vorrei convertire: https://github.com/drew-gross/Blokus-AI/blob/master/Grid.hs

e il mio tentativo di convertirlo: https://github.com/drew-gross/Blokus-AI/blob/convert-to-vector/Grid.hs

Tutte le idee che sto facendo male? O almeno, dove cercare?

Answer 1

makeEmptyGrid width height defaultCell = Grid (Data.Vector.take arraySize $ fromList $ repeat defaultCell) width height 

Questo è un killer proprio lì. fromList converte un intero elenco in un Vector, ma repeat defaultCell è un elenco infinito.

makeEmptyGrid width height defaultCell = Grid (fromListN arraySize $ repeat defaultCell) width height 

o

makeEmptyGrid width height defaultCell = Grid (fromList $ replicate arraySize defaultCell) width height 

sarebbe sistemare le cose.

Un rapido sguardo sul resto non ha comportato ulteriori trappole evidenti, ma potrebbe facilmente essere trascurato un po '.

Answer 2

Questo è solo un pensiero ulteriore in seguito ad Daniel. Sembrava il tuo Grids erano solo di Colors Probabilmente non farà molto per una piccola 'griglia', ma è relativamente facile fare un'istanza Unbox per Color. Quindi una griglia conterrà un array non inserito. In Grid.hs importerebbe Data.Vector.Unboxed anziché Data.Vector. Questo è in generale molto più per molte ragioni, ma richiede di inserire un vincolo Unbox a => su molte delle definizioni. Ciò potrebbe avere conseguenze se si desidera effettuare o "mappare" in griglie piene di cose di un altro tipo rispetto a Color, a meno che non abbia un'istanza Unbox.

Qui di seguito aggiungo l'incantesimo TH da vector-th-unbox (ho appena saputo di quel pacchetto di recente, e sto cogliendo l'occasione per testarlo di nuovo) e le due definizioni necessarie. Non sarebbe molto più difficile scriverlo a mano seguendo l'istanza Bool in Data.Vector.Unboxed.Base.

{-#LANGUAGE TemplateHaskell, TypeFamilies, MultiParamTypeClasses#-} 
module Color where 

import Display 
import Data.Vector.Unboxed.Deriving 
import qualified Data.Vector.Unboxed as V 
import qualified Data.Vector.Generic   as G 
import qualified Data.Vector.Generic.Mutable as M 
import Data.Word (Word8) 

data Color = Yellow | Red | Green | Blue | Empty  
      deriving (Show, Eq, Ord, Enum, Bounded) 

fromColor :: Color -> Word8 
{-# INLINE fromColor #-} 
fromColor = fromIntegral . fromEnum 

toColor :: Word8 -> Color 
{-# INLINE toColor #-} 
toColor x | x < 5 = toEnum (fromIntegral x) 
toColor _ = Empty 

derivingUnbox "Color" 
    [t| Color -> Word8 |] 
    [| fromColor |] 
    [| toColor |] 

-- test 
colorCycle :: Int -> V.Vector Color 
colorCycle n = V.unfoldr colorop 0 where 
    colorop m | m < n = Just (toColor (fromIntegral (m `mod` 5)),m+1) 
    colorop _ = Nothing 
-- *Colour> colorCycle 12 
-- fromList [Yellow,Red,Green,Blue,Empty,Yellow, 
-- Red,Green,Blue,Empty,Yellow,Red] 

colorBlack = "\ESC[0;30m" 
colorRed = "\ESC[0;31m" 
colorGreen = "\ESC[0;32m" 
colorYellow = "\ESC[0;33m" 
colorBlue = "\ESC[0;34m" 

instance Display Color where 
    display Red = colorRed ++ "R" ++ colorBlack 
    display Green = colorGreen ++ "G" ++ colorBlack 
    display Yellow = colorYellow ++ "Y" ++ colorBlack 
    display Blue = colorBlue ++ "B" ++ colorBlack 
    display Empty = "." 

Edit: Nelle versioni di vector-th-unbox precedenti 0.1 il seguente modello è stato utilizzato:

derivingUnbox "Color" 
    [d| instance Unbox' (Color) Word8 |] 
    [| fromColor |] 
    [| toColor |]