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 有什么想法我做错了什么吗？或者至少，应该从哪里着手检查？

- Drew

Answer 1

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

这是一个杀手。 fromList 将整个列表转换为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

我会修复这个问题。

浏览其余部分时没有发现明显的陷阱，但我可能会轻易地忽略一些。

- Daniel Fischer

---

谢谢！那个问题和另一个地方的相同问题都解决了。 - Drew

Answer 2

这只是对丹尼尔的补充思考。看起来你的Grids只有Colors，对于一个小的“网格”可能不会有太大影响，但相对容易为Color创建一个Unbox实例。然后，网格将包含一个未装箱的数组。在Grid.hs中，您将导入Data.Vector.Unboxed而不是Data.Vector。这通常出于许多原因要好得多，但是需要在许多定义上放置Unbox a =>约束。如果您想制作或“映射”到除Color之外的其他类型的网格，则可能会产生后果，除非它具有Unbox实例。

下面我只添加了来自vector-th-unbox的TH咒语（我最近才了解到该软件包，并借此机会再次测试它）和两个必需的定义。手写它并按照Data.Vector.Unboxed.Base中的Bool实例也不难。

{-#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  = "."

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

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

- applicative