Haskell - Konvertierung von List zu Data.Vector

Question

Nach Profiling meiner Haskell-Programm habe ich festgestellt, dass 66% der Zeit in dem Programm die Indexierung in Listen ausgegeben wird. Die Lösung scheint Data.Vector zu verwenden, aber ich habe Probleme beim Konvertieren: Wenn ich den Code für die Verwendung eines Vectors ändere, verwendet er Tonnen und Tonnen Speicher und hängt so stark, dass ich es nicht einmal profilieren kann. Was könnte das verursachen?

Hier wird die Datei würde Ich mag konvertieren: https://github.com/drew-gross/Blokus-AI/blob/master/Grid.hs bei der Umwandlung von

und mein Versuch es: https://github.com/drew-gross/Blokus-AI/blob/convert-to-vector/Grid.hs

Alle Ideen, was ich falsch mache? Oder zumindest, wohin?

Answer 1

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

Das ist ein Killer genau dort. fromList konvertiert eine vollständige Liste in eine Vector, aber repeat defaultCell ist eine unendliche Liste.

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

oder

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

wäre das in Ordnung bringen.

Ein flüchtiger Blick über den Rest führte nicht zu weiteren offensichtlichen Fallen, aber ich könnte leicht einige übersehen haben.

Answer 2

Dies ist nur ein weiterer Gedanke nach Daniel. Es sah aus wie Ihre Grids waren nur Colors Es wird wahrscheinlich nicht viel für ein kleines 'Grid' tun, aber es ist vergleichsweise einfach, eine Unbox Instanz für zu machen. Dann enthält ein Raster ein ungepacktes Array. In Grid.hs würden Sie Data.Vector.Unboxed statt Data.Vector importieren. Dies ist im Allgemeinen viel aus vielen Gründen besser, aber Sie müssen eine Unbox a => Einschränkung auf viele der Definitionen setzen. Dies kann Konsequenzen haben, wenn Sie Gitter mit Objekten eines anderen Typs als erstellen oder "abbilden" möchten, es sei denn, es gibt eine Unbox Instanz.

Unten füge ich einfach die TH-Beschwörung von hinzu (ich habe gerade erst von diesem Paket erfahren, und ich nutze die Gelegenheit, es noch einmal zu testen) und die zwei erforderlichen Definitionen. Es wäre nicht viel schwieriger, es von Hand nach der Bool-Instanz in Data.Vector.Unboxed.Base zu schreiben.

{-#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: In Versionen von vector-th-unbox0.1 die folgende Vorlage wurde vorhergehenden verwendet:

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