基于Heap的Priority Queue在Haskell中导致大量垃圾收集

Question

我正在尝试在Haskell中开发一个启发式搜索库,并且使算法以某种方式表现的主要因素之一是数据结构; 所以我宣布了这个课:

class DataStructure ds where  
  add :: Eq a => Node a -> ds a -> ds a
  addList :: Eq a => [Node a] -> ds a -> ds a
  next :: Eq a => ds a -> (ds a, Node a)
  isEmpty :: Eq a => ds a -> Bool

然后,此类的实例用于扩展节点的常规搜索算法,如下所示:

generalSearch :: (DataStructure ds, Eq a, Hashable a)
  => ProblemSpace a   -- ^ 'ProblemSpace' to be solved
  -> Cost a           -- ^ 'Cost' function to use
  -> Heuristic a      -- ^ 'Heuristic' function to use
  -> ds a             -- ^ 'DataStructure' that manages the node expansion
  -> [Node a]         -- ^ Returns the infinite list of final nodes (solutions)

generalSearch problem g h open
  | isEmpty open                    = []
  | getGoalF problem (getState n)   = n : generalSearch problem g h open'
  | otherwise                       = generalSearch problem g h open''
  where (open', n) = next open
        expanded = expand n g h (getActions problem)
        open'' = addList expanded open'

如果没有模块的完整上下文,最后一段代码很难理解,但重要的部分是最后一行:它使用该DataStructure方法addList将刚刚扩展的节点与执行的开放列表的其余部分合并在一起携带.

一些算法要求打开列表以某种方式排序:升序成本,升序启发式...我使用该heap包来构建这样的PriorityQueue实现:

data PriorityQueue a =
  PriorityQueue { priorityQueueToHeap :: MinPrioHeap Double (Node a)
                , valueFunction :: Node a -> Double }

因此,此队列按照升序按升序存储节点valueFunction.这个问题的相关方法addList实现如下:

addList :: Eq a => [Node a] -> PriorityQueue a -> PriorityQueue a
addList xs (PriorityQueue h f) = PriorityQueue (union h xs') f
  where xs' = fromList $ map (\n -> (f n, n)) xs

从我对Haskell的经验来看,这似乎是一个很好的方法,但事实证明,在测试它时,执行速度非常慢.经过一些分析后,我能够发现由于垃圾收集问题导致问题很多,成本中心发现该union方法addList是最昂贵的一个(由于排序,我可以理解)在太空中(它是迄今为止分配最多的那个).

COST CENTRE   MODULE             SRC                                     %time %alloc

union         Data.Heap.Internal Data/Heap/Internal.hs:(134,1)-(141,79)   42.8   32.7
visited       Search.General     src/Search/General.hs:77:43-53           14.6    0.0
expand        Search.General     src/Search/General.hs:(70,40)-(76,78)    13.6   14.0
cost          Search.General     src/Search/General.hs:74:70-81            7.8    7.9
generalSearch Search.General     src/Search/General.hs:(52,1)-(58,37)      6.7   13.6
fromList      Data.Heap          Data/Heap.hs:137:1-34                     4.7   11.7
size          Data.Heap.Internal Data/Heap/Internal.hs:(98,1)-(99,23)      3.4    8.3
rank          Data.Heap.Internal Data/Heap/Internal.hs:(93,1)-(94,23)      2.7    8.0
expand        Search.General     src/Search/General.hs:(69,1)-(77,53)      1.4    3.4

时间问题似乎只有在开放节点列表很大的时候才会发生,所以我猜它与堆的不可变性有关,在每次新的扩展中都被写入和擦除.有没有办法防止这种行为,并减少垃圾收集？我应该使用不同类型的数据结构来构建优先级队列吗？