当我注意到我的 HashMap
不支持时,我一直在尝试使用 ghc-heap-view 包及其提供的 utils 确保 Haskell 程序的内存模型的严格性t 似乎在一系列插入物上处于 NF 状态。我尝试打印堆树,确实它显示了一些重击。然后,我尝试了另一种插入元素的方法(使用 union
和 singleton
),这次结果是严格的。
有人可以解释一下为什么会这样,并建议我是否可以采取任何措施使 insert
的行为与其他方法相同?
这是我的测试代码:
module Main where
import Control.Exception (evaluate)
import Data.Foldable
import Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HM
import GHC.HeapView
test1 :: HashMap Int Int
test1 = foldl' (\m v -> HM.insert v v m) HM.empty [0..5]
test2 :: HashMap Int Int
test2 = foldl' (\m v -> HM.union (HM.singleton v v) m) HM.empty [0..5]
main :: IO ()
main = do
putStrLn "HeapTree for test1"
t1 <- evaluate test1
buildHeapTree 10 (asBox t1) >>= print . ppHeapTree
putStrLn "HeapTree for test2"
t2 <- evaluate test2
buildHeapTree 10 (asBox t2) >>= print . ppHeapTree
这是输出:
HeapTree for test1
"BitmapIndexed ([ (_thunk (I# 0) (I# 0) 0), (_thunk (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
HeapTree for test2
"BitmapIndexed ([ (Leaf (I# 0) (I# 0) 0), (Leaf (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
(0.02 secs, 1,067,672 bytes)
最佳答案
将新的非冲突键插入 Leaf
节点时,insert
使用名为 two
的辅助函数来生成二元键元素图。 two
函数在键值上是惰性的,这导致 GHC 创建 thunk 来创建两个新的 Leaf
节点。整件事非常愚蠢,因为那时 key 实际上肯定位于 WHNF 中。但是(大概是因为递归 go
函数)GHC 没有意识到这一点。该问题应该在 unordered-containers
的下一版本中得到解决。
关于haskell - 为什么 HashMap 在一系列插入后不处于正常形式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55994488/