时间戳

首页 > 解决方案 > Haskell：大量读写时IOArray太慢

haskell - Haskell：大量读写时IOArray太慢

问题描述

我在 Haskell 中写了一个小代码。你能给出一个提高性能的解决方案吗？

4 4
##..
#...
...#
……

0 0 1 2
0 1 2 1
1 2 1 0
2 3 2 1

为了将大量数字设置成网格，我使用了二维IOArray来降低修改成本。处理一个 500x500 的网格需要一分钟多的时间，而我用 Python 编写的替代代码只需要 5 秒。

不到 16 秒将不胜感激！

import Data.List
import Data.Array.IO
import Control.Monad

type Point = (Int, Int)
type Grid = IOArray Point Int

main :: IO ()
main = do
  [height, width] <- (map read . take 2 . words) <$> getLine
  points <- zeroPoints width <$> getContents
  grid <- newArray ((1,1), (height, width)) (-1)
  wfs grid points 0
  printArray grid

zeroPoints :: Int -> String -> [Point]
zeroPoints width str = [(i `div` width + 1, i `mod` width + 1) | (i, c) <- chars, c == '#']
  where chars = zip [0..] (concat $ words str)

wfs :: Grid -> [Point] -> Int -> IO [Point]
wfs grid [] _ = return []
wfs grid points distance = do
  mapM_ (\p -> writeArray grid p distance) points
  (_, (height, width)) <- getBounds grid
  newPoints <- neighbors grid height width points
  wfs grid newPoints (distance + 1)

neighbors :: Grid -> Int -> Int -> [Point] -> IO [Point]
neighbors grid height width points =
  filterM (isEmpty grid) $ nub $ filter inArea $ [up, down, left, right] <*> points
  where
    up    (x, y) = (x - 1, y)
    down  (x, y) = (x + 1, y)
    left  (x, y) = (x, y - 1)
    right (x, y) = (x, y + 1)
    inArea (x, y) = x > 0 && x <= height && y > 0 && y <= width
    isEmpty grid p = (< 0) <$> readArray grid p

printArray :: Grid -> IO ()
printArray grid = do
  (_, (height, width)) <- getBounds grid
  forM_ [(h, w) | h <- [1..height], w <- [1..width]] $ \(h, w) -> do
    i <- readArray grid (h, w)
    if w == width then putStrLn $ show i else putStr $ show i ++ " "

标签： haskellmultidimensional-array

解决方案

我没有做任何分析，但这是跳出我的行：

  filterM (isEmpty grid) $ nub $ filter inArea $ [up, down, left, right] <*> points

特别是，nub是一个 O(n^2) 操作。您可以从尝试使用ordNubfrom开始Data.Containers.ListUtils。

我看到的另一件事是您使用的是盒装数组。盒装数组有间接成本和额外的 GC 成本；他们可以很容易地使用它们来编写比应有速度慢几倍的代码。作为一般规则，您应该只在需要它们的多态性或惰性时才使用盒装数组。我在这里没有立即看到任何内容。

最后，进行微优化：如果您需要商和余数，请使用divMod或quotRem仅使用一个硬件部门来完成这项工作。这不是你的代码慢的原因，但这是一个好习惯。如果数字是正数，请使用quotRem速度。如果不是，请务必阅读文档以确定您应该使用哪个。

推荐阅读