优化从文件读取Haskell数据

Question

我试图在一个3.5米的行文件上实现Kosaraju的图算法,其中每行是两个(空格分隔)Ints代表图形边缘.首先,我需要创建一个摘要数据结构,其中包含节点及其传入和传出边的列表.下面的代码实现了这一点,但需要花费一分多钟,而我可以从MOOC论坛上的帖子看到使用其他语言的人在"10"中完成.(getLines在我读到的基准测试中,与10岁以下相比需要10分钟.)

我是Haskell的新手,已经实现了一种使用累积方法foldl'(这'是一种突破性的终止方法),但它在风格方面感觉相当紧迫,我希望这就是它运行缓慢的原因.此外,我目前正计划使用类似的模式进行深度优先搜索,我担心这一切都会变得太慢.

我发现这个演示文稿和博客谈论这些问题,但在专家级别上.

import System.IO
import Control.Monad
import Data.Map.Strict as Map
import Data.List as L

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored (Edges, Edges) deriving (Show)

type Graph1 = Map NodeName Node

getLines :: FilePath -> IO [[Int]]
getLines = liftM (fmap (fmap read . words) . lines) . readFile

getLines' :: FilePath -> IO [(Int,Int)]
getLines' = liftM (fmap (tuplify2 . fmap read . words) . lines) . readFile

tuplify2 :: [a] -> (a,a)
tuplify2 [x,y] = (x,y)

main = do
    list <- getLines "testdata.txt"  -- [String]
    --list <- getLines "SCC.txt"  -- [String]   
    let
        list' = createGraph list
    return list'

createGraph :: [[Int]] -> Graph1
createGraph xs = L.foldl' build Map.empty xs
    where
        build :: Graph1-> [Int] -> Graph1
        build = \acc (x:y:_) ->
            let tmpAcc = case Map.lookup x acc of
                Nothing -> Map.insert x (Node False ([y],[])) acc
                Just a -> Map.adjust (\(Node _ (fwd, bck)) -> (Node False ((y:fwd), bck))) x acc
            in case Map.lookup y tmpAcc of
                Nothing -> Map.insert y (Node False ([],[x])) tmpAcc
                Just a -> Map.adjust (\(Node _ (fwd, bck)) -> (Node False (fwd, (x:bck)))) y tmpAcc

Answer 1

使用地图:

• 使用IntMap或HashMap尽可能使用.两者Int都比键快得多Map.HashMap通常比IntMap使用更多内存更快,但库更少.
• 不要做不必要的查找.该containers软件包具有大量专用功能.与问题中alter的createGraph实现相比,查找次数可以减半.

示例createGraph:

import Data.List (foldl')
import qualified Data.IntMap.Strict as IM

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored Edges Edges deriving (Eq, Show)
type Graph1 = IM.IntMap Node

createGraph :: [(Int, Int)] -> Graph1
createGraph xs = foldl' build IM.empty xs
    where
        addFwd y (Just (Node _ f b)) = Just (Node False (y:f) b)
        addFwd y _                   = Just (Node False [y] [])
        addBwd x (Just (Node _ f b)) = Just (Node False f (x:b))
        addBwd x _                   = Just (Node False [] [x])

        build :: Graph1 -> (Int, Int) -> Graph1
        build acc (x, y) = IM.alter (addBwd x) y $ IM.alter (addFwd y) x acc 

使用向量:

• 考虑有效的构造函数(累加器,展开,generate,iterate,constructN,等等).这些可能在幕后使用突变,但比实际的可变载体使用起来要方便得多.
• 在更一般的情况下,使用盒装向量的懒惰来在构造向量时启用自引用.
• 尽可能使用未装箱的向量.
• 当你完全确定边界时,使用不安全的函数.
• 只有在没有纯替代品时才使用可变载体.在这种情况下,更喜欢ST monad到IO.此外,避免创建许多可变堆对象(即更喜欢可变向量到可变引用的不可变向量).

示例createGraph:

import qualified Data.Vector as V

type NodeName = Int
type Edges = [NodeName]
type Explored = Bool

data Node = Node Explored Edges Edges deriving (Eq, Show)
type Graph1 = V.Vector Node

createGraph :: Int -> [(Int, Int)] -> Graph1
createGraph maxIndex edges = graph'' where
    graph    = V.replicate maxIndex (Node False [] [])
    graph'   = V.accum (\(Node e f b) x -> Node e (x:f) b) graph  edges
    graph''  = V.accum (\(Node e f b) x -> Node e f (x:b)) graph' (map (\(a, b) -> (b, a)) edges)

请注意,如果节点索引的范围存在间隙,那么任何一个都是明智的

1. 在做任何其他事情之前,连续重新标记指数.
2. 引入一个空构造函数来Node表示缺少的索引.

更快的I/O:

• 使用Data.Text或的IO功能Data.ByteString.在这两种情况下,还有用于将输入分解为行或单词的有效功能.

例:

import qualified Data.ByteString.Char8 as BS
import System.IO

getLines :: FilePath -> IO [(Int, Int)]
getLines path = do
    lines <- (map BS.words . BS.lines) `fmap` BS.readFile path
    let pairs = (map . map) (maybe (error "can't read Int") fst . BS.readInt) lines
    return [(a, b) | [a, b] <- pairs]

标杆:

总是这样做,不像我在这个答案中.使用criterion.