11

我在 Haskell 中实现了一个过滤器，即一个我可以从命令行调用的程序，如下所示：

$ cat inputfile.txt | myFilter > outputfile.txt

在大约 80 MB 的文件上运行程序时，出现堆栈溢出（堆栈空间溢出：当前大小 8388608 字节。）。我在 cygwin 下使用 GHC 版本 6.12.3。

我认为问题来自sort我在程序中使用的功能，但是在我寻找问题三天后，我不知道如何解决这个问题，所以我希望有人能给我提示。

以下是关于我的程序的基本细节。

我的过滤器程序将标准输入读入字符串，将其拆分为行并将每一行解析为某种类型的记录Event

data Event = ...

这是一个实例Ord

instance Ord Event where
    x < y = ...

这样我就可以使用内置sort函数对事件进行排序。

拆分成行并解析事件（每行一个事件）由函数执行

p :: String -> [Event]

它在内部使用标准功能lines。

我还有一个函数 g 可以对事件进行分组：

g :: [Event] -> [[Event]]

g 使用了一些与此处无关的标准；每个组最多可以包含 4 个事件。

我使用（即，每个组内的所有事件都被排序）对每组事件（表示为列表）进行sort排序，最后使用函数将所有事件组格式化为字符串

f :: [[Event]] -> String

主函数如下所示：

main = interact (f . (map sort) . g . p)

如前所述，在大约 80 MB 的文件上运行此程序会导致堆栈溢出。

如果我用以下函数替换排序函数（一个简单的快速排序实现）：

mySort :: [Event] -> [Event]
mySort [] = []
mySort (e:es) = let h = [j | j <- es, j < e]
                    t = [j | j <- es, e < j]
                in
                  (mySort h) ++ [e] ++ (mySort t)


main = interact (f . (map mySort) . g . p)

我没有堆栈溢出！

如果在函数中，mySort我将定义替换为t以下内容：

                    t = [j | j <- es, e <= j]

即我替换<为<=，堆栈溢出又出现了！

所以我不知道这里发生了什么。我看不出我引入了任何无限递归。我的另一个假设是惰性评估可以在这里发挥作用（确实会<=产生比？更大的声音<？）。

我对 Haskell 有一些经验，但我不是真正的专家，所以我很高兴能得到一些有用的提示，因为过去三天​​我一直在努力理解这一点。

4

2 回答 2

23

罪魁祸首是

instance Ord Event where
    x < y = ...

这是定义Ord实例的错误方法。Ord实例的最小完整定义定义了compare或之一(<=)。有 的 的默认定义compare，(<=)以及所有Ord成员函数的的默认定义compare。因此，如果您定义(<)，那是您可以使用的唯一Ord成员，所有其他成员在调用时将无限循环，因为它们调用compare，调用(<=)，调用compare...

该Data.List.sort函数用于compare确定顺序，因此它在第一次比较时循环。您的自定义快速排序仅使用(<)，因此有效。

于 2012-08-30T19:22:12.097 回答
1

在尝试分析代码并获得快速结果之前 - 尝试增加堆栈大小。

在启用 RTS 的情况下编译您的程序并指定所需的堆栈大小。

http://book.realworldhaskell.org/read/profiling-and-optimization.html

于 2012-08-30T18:45:15.543 回答