Haskell - 从List转换为Data.Vector

Question

在对我的haskell程序进行概要分析后,我发现该程序中有66%的时间用于索引到列表中.解决方案似乎是使用Data.Vector,但我在转换时遇到问题:当我将代码更改为使用Vector时,它使用了大量的内存,并且挂得很严重,我甚至无法对其进行分析.什么可能导致这个？

这是我想要转换的文件:https://github.com/drew-gross/Blokus-AI/blob/master/Grid.hs

我尝试转换它:https://github.com/drew-gross/Blokus-AI/blob/convert-to-vector/Grid.hs

我有什么想法我做错了吗？或者至少,在哪里看？

Answer 1

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

那是一个杀手.fromList将整个列表转换为a Vector,但是repeat defaultCell是无限列表.

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

要么

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

会解决这个问题.

粗略地看一下其余部分并没有导致更明显的陷阱,但我可能很容易忽略一些.

Answer 2

这只是丹尼尔的另一个想法.它看起来像你Grids只是Colors 它可能不会对一个小的'网格'做太多,但它是相对容易的一个Unbox实例Color.然后网格将包含一个未装箱的数组.在Grid.hs你进口Data.Vector.Unboxed而不是Data.Vector.由于许多原因,这通常要好得多,但需要您Unbox a =>对许多定义进行约束.如果你想要制作或"映射"到满足其他类型的东西的网格Color,除非它有一个Unbox实例,否则这可能会产生影响.

下面我只是添加TH咒语vector-th-unbox(我最近刚刚了解了这个包,并且正在借此机会再次测试它)和两个必要的定义.在Bool实例之后用手写它不会困难得多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  = "."

编辑:在vector-th-unbox前面0.1的版本中使用了以下模板:

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