14

我正在使用 GHC 7.4 编译以下函数：

nodups' :: [Int] -> Bool
nodups' = ok empty
  where ok _ [] = True
        ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns
        member n word = testBit word n
        insert n word = setBit word n
        empty = 0 :: Int

该函数在小整数列表中查找重复元素。该集合seen是将一组小整数表示为位向量。分析器（使用 运行ghc -prof -auto-all）声称该ok函数占总体分配的 22%。查看带有 的输出-ddump-simpl，我不明白为什么要分配此代码。我检查了一下，据我所知，它没有为调用分配 thunk 到insert.

我应该看什么来识别正在分配的代码部分？

4

1 回答 1

1

一般来说

我知道函数式语言的简单（科学）实现，如果我没记错的话，有可以与 Haskell 一起使用的G-Machine 。

这意味着（再次，如果我没记错的话）您的程序状态表示为“树”，其中节点（为了简单起见）是您在代码中使用的函数。叶子将是它的论据。然后，“G-Maschine”沿着“Spine”（节点的左侧链）查找并在可用的“Functions”（“Supercombinators”？）集合中查找它可以应用的模式匹配。如果从定义的左侧识别出物质匹配，则将其替换为定义的右侧。

这意味着即使是简单的行

ok seen (n:ns) = not (n `member` seen) && ok (n `insert` seen) ns

甚至

(n:ns) = ns

在计算机内存中做某事，即匹配模式

       ...
     ...
    (:)
   /   \
  n     ns

并将其替换为

       ...
     ...
    ns

最终结果可能会比输入消耗更少的内存，但这是一个动态步骤，因此必须在某个地方进行。如果一遍又一遍地重复（在“紧密循环”中），那么这会让你的 CPU 很忙，你的内存也会很忙——只是因为 G-Machine 正在运行。（正如我所说，我不确定 G-Machine 概念是否适用于此，但我想它是类似的）。

具体猜测

    member n word = testBit word n
    insert n word = setBit word n

除此之外，我还有一些怀疑。testBit并且setBit看起来像列表上的索引操作。如果是的话，可能需要一些工作。如果它们是正确的数组，那就没问题了。如果它们是一种地图或集合......嗯......可能涉及昂贵的散列？还是通过使用大量（昂贵？）比较操作的平衡树来实现？

于 2012-12-18T09:45:49.123 回答