Haskell：从具有一百万个值的列表构造 IntMap 时，我应该得到 "Stack space overflow" 吗？

Question

我的问题是，在 Haskell 中使用任何 Map 实现时，在处理一百万个值时我总是得到 "Stack space overflow"。

我想做的是处理一个配对列表。每对包含两个 Ints（不是 Integers，我用它们失败了，所以我尝试了 Ints）。我想遍历列表中的每一对并使用第一个 Int 作为键。对于每个唯一键，我想建立第二个元素的列表，其中每个第二个元素都成对具有相同的第一个元素。所以我最后想要的是从 Int 到 Int 列表的 "Map"。这是一个例子。

给定一个像这样的对列表：

[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]

我想以这样的 "Map" 结束：

{1 : [42,79,10], 2 : [11], 3 : [18,99]}

（我在上面使用类似 Python 的符号来说明 "Map"。我知道它不是 Haskell。它只是为了说明目的。）

所以我尝试的第一件事是我自己手工构建的版本，我对 Int 对列表进行排序，然后遍历该列表构建一个新的对列表，但这次第二个元素是一个列表。第一个元素是键，即每对中第一个元素的唯一 Int 值，第二个元素是每个原始对的第二个值的列表，其中键作为第一个元素。

所以给定一个像这样的对列表：

[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]

我最终得到了这样的一对列表：

[(1, [42,79,10], (2, [11]), (3, [18,99])]

这很容易做到。但是有一个问题。 "sort" 函数在原始列表（1000 万对）上的性能非常糟糕。我可以在不到一秒的时间内生成原始的配对列表。我可以在不到一秒钟的时间内将排序后的列表处理成我手工构建的地图。但是，对原始对列表进行排序需要 40 秒。

所以我考虑使用 Haskell 中的一种内置 "Map" 数据结构来完成这项工作。我的想法是构建我的原始对列表，然后使用标准 Map 函数构建标准 Map。

这就是一切都变成梨形的地方。它在包含 100,000 个值的列表上运行良好，但是当我移动到 100 万个值时，出现 "Stack space overflow" 错误。

下面是一些存在问题的示例代码。请注意，这不是我想要实现的实际代码。它只是一个非常简化的代码版本，存在同样的问题。我真的不想把一百万个连续的数字分成奇数和偶数分区！！

import Data.IntMap.Strict(IntMap, empty, findWithDefault, insert, size)

power = 6

ns :: [Int]
ns = [1..10^power-1]

mod2 n = if odd n then 1 else 0

mod2Pairs = zip (map mod2 ns) ns

-- Takes a list of pairs and returns a Map where the key is the unique Int values
-- of the first element of each pair and the value is a list of the second values
-- of each pair which have the key as the first element.
-- e.g. makeMap [(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)] = 
--      1 -> [42,79,10], 2 -> [11], 3 -> [18,99]
makeMap :: [(Int,a)] -> IntMap [a]
makeMap pairs = makeMap' empty pairs
  where
    makeMap' m [] = m
    makeMap' m ((a, b):cs) = makeMap' m' cs
      where
        bs = findWithDefault [] a m
        m' = insert a (b:bs) m

mod2Map = makeMap mod2Pairs

main = do
  print $ "Yowzah"
  print $ "length mod2Pairs="++ (show $ length mod2Pairs)
  print $ "size mod2Map=" ++ (show $ size mod2Map)

当我运行这个时，我得到：

"Yowzah"
"length mod2Pairs=999999"
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

从上面的输出可以看出，当我尝试执行 "makeMap mod2Pairs".

时，堆栈 space 溢出发生了

但在我天真的眼中，所有这一切似乎都是通过一个对列表，并为每对查找一个键（每对的第一个元素）和 A) 如果它没有找到匹配 return 一个空列表或 B) 如果找到匹配项，return 之前插入的列表。在任何一种情况下，"cons" 都是 "found" 列表中的第二个元素，并使用相同的键将其插入回 Map 中。

（PS 而不是 findWithDefault，我也尝试查找并处理 Just 和 Nothing 用例但无济于事。）

我已经查看了关于各种 Map 实现的 Haskell 文档，从 CPU 和内存（尤其是堆栈内存）方面的性能的角度来看，似乎A) 严格的实现和 B) 键是 Int 的实现是最好的。我也试过Data.Map和Data.Strict.Map，他们也遇到同样的问题。

我确信问题出在 "Map" 实现上。我对吗？为什么我会收到堆栈溢出错误，即 Map 实现在后台执行的操作导致堆栈溢出？它是否在幕后进行了很多很多的递归调用？

任何人都可以帮助解释发生了什么以及如何解决这个问题吗？

Answer 1

我没有足够旧的 GHC 来检查（这对我来说很好用，而且我没有你那样的 7.6.3），但我猜你的 makeMap'太懒了。可能这会解决它：

makeMap' m ((a, b):cs) = m `seq` makeMap' m' cs

没有它，您将构建一个百万级深度的嵌套 thunk，而深度嵌套的 thunk 是导致 Haskell.

中堆栈溢出的传统方法

或者，我会尝试将整个 makeMap 实现替换为 fromListWith:

makeMap pairs = fromListWith (++) [(k, [v]) | (k, v) <- pairs]

Haskell：从具有一百万个值的列表构造 IntMap 时，我应该得到 "Stack space overflow" 吗？

Haskell: Should I get "Stack space overflow" when constructing an IntMap from a list with a million values?

stack-overflow

haskell