6

我正在尝试解决 Haskell 中的整个 Advent of Code 系列。

我在解决2015/06 练习时遇到了内存问题，其中有一堆指令可以打开、关闭和切换网格上的灯。目标是计算最后点亮的灯的数量。

给定指令被解析并存储在一个Instruction类型中，这是类型定义：

data Instruction = Instruction Op Range deriving Show
data Op = Off | On | Toggle | Nop deriving Show
data Range = Range Start End deriving Show
type Start = Point
type End = Start
data Point = Point Int Int deriving Show

这是计算结果的代码。我试图通过使用类型类来抽象出灯光是布尔值的事实

gridWidth, gridHeight :: Int
gridWidth = 1000
gridHeight = 1000

initialGrid :: Togglable a => Matrix a
initialGrid = matrix gridWidth gridHeight (const initialState)

instance Monoid Op where
  mempty = Nop

instance Semigroup Op where
  _ <> On = On
  _ <> Off = Off
  x <> Nop = x
  Off <> Toggle = On
  On <> Toggle = Off
  Toggle <> Toggle = Nop
  Nop <> Toggle = Toggle

class Togglable a where
  initialState :: a
  apply :: Op -> a -> a

instance Togglable Bool where
  initialState = False
  apply On = const True
  apply Off = const False
  apply Toggle = not
  apply Nop = id

-- Does the Range of the instruction apply to this matrix coordinate?
(<?) :: Range -> (Int, Int) -> Bool
(<?) (Range start end) (x, y) = let
  (Point x1 y1) = start
  (Point x2 y2) = end
  (mx, my) = (x-1, y-1) -- translate from matrix coords (they start from 1!)
  in and [
    mx >= min x1 x2, mx <= max x1 x2,
    my >= min y1 y2, my <= max y1 y2
  ]

stepGenerator :: Instruction -> Matrix Op
stepGenerator (Instruction op r) = let
  g coord = if r <? coord then op else Nop
  in matrix gridWidth gridHeight g

allStepsMatrix :: [Instruction] -> Matrix Op
allStepsMatrix = mconcat.map stepGenerator

finalGrid :: Togglable a => Matrix a -> Matrix Op -> Matrix a
finalGrid z op = fmap apply op <*> z

countOn :: Matrix Bool -> Integer
countOn = toInteger.foldr (\x -> if x then (+1) else id) 0

partA :: Challenge (String -> Integer)
partA = Challenge $ countOn.finalGrid initialGrid.allStepsMatrix.parse

解决方案将是由 inside 返回的整数partA。parse工作并且有类型parse :: String -> [Instruction]

代码编译并使用小矩阵（例如 10x10）运行，一旦我转向1000 gridWidth，gridHeight我就会遇到out of memory错误，显然是从allStepsMatrix函数生成的。

这里有什么可能出错的提示吗？完整代码在 GitHub 上

4

1 回答 1

5

我强烈建议不要使用类型类。类型类应该有规律，它们应该是“稀有的”，因为每种类型只有几个有效的实现。我建议将initialStateandtoggle作为参数，但即使这样也太过分了，因为给定的指令对于任何不是Bool. 只需Matrix Bool直接对 a 进行操作，您就可以剪切出您编写的大部分代码。但是，我不会为我的答案做出任何改变。

无论如何，我认为问题可能是懒惰。1000 * 1000 = 1000000，所以每个Matrix大小都是几兆字节。在 64 位机器上，一个指针是 8 个字节，所以每个 Matrix 至少有 8 MB，加上后面的数据还要多一些。您将mconcat其中的 300 个（这就是我从该站点得到的）放在一起，但是，因为您是懒惰地这样做，所以所有 300 个矩阵都是同时驻留的，所以至少是2.4 GB，仅用于结构本身。用 thunk 填充这 3 亿个指针中的每一个的成本也是众所周知的——一个 thunk 至少是一个指针（8 个字节，指向静态内存中的代码，另外还有 2.4 GB）加上它的有效负载，在这里，这意味着更多指针，每个指针都会给您的计算机带来另外 2.4 GB 的内存压力。我建议deepseq：

instance NFData Op where
  rnf Off = ()
  rnf On = ()
  rnf Toggle = ()
  rnf Nop = ()
  -- rnf x = x `seq` () but I like to be explicit
allStepsMatrix :: [Instruction] -> Matrix Op
allStepsMatrix = foldl' (\x y -> force (x <> y)) mempty . map stepGenerator

Usnig 让它foldl'在恒定的堆栈空间中运行，但foldlorfoldr也可以工作，因为 300 左右的堆栈深度什么都不是。这force意味着对每个元素的所有元素Matrix进行评估。以前，每个矩阵都通过保存对它的引用来保持前一个矩阵的存在，但现在在计算元素时会删除引用，因此 GC 可以及时将它们丢弃。我已经对此进行了测试，它会在合理的时间内以更好的空间使用率终止。

于 2019-06-08T16:13:35.673 回答