假设我有以下功能

small_div :: Int -> Int
small_div n = filter (\x -> n `rem` x == 0) [2..n] !! 0

此函数的内存使用量是多少?等效的C代码将保持不变的内存使用率,并且我相信Haskell的惰性计算意味着它不会创建比第一个除数所需的[2..n]元素更多的元素,但是ghc足够聪明,可以进行跳转像...
int small_div(int n) {
    for (int x = 2; x <= n; x++) {
        if (n % x == 0) {
            return x;
        }
    }
}

最佳答案

GHC 7.10和7.8.4(我测试的版本)足够聪明,可以跳到您的优化示例。

我从互联网上查询了两个素数:15485863和67867967。当我编译并使用main = print $ small_div 15485863标志运行+RTS -s时,我的总堆分配为51 Kb。当我用67867967运行时,我也得到了51 Kb的分配。这意味着没有为该列表的生成和过滤分配任何单元格。

很有可能是通过所谓的 foldr/build 融合进行了优化(filterenumFromToInt都参与了这种融合)。

关于haskell - 过滤器foo [2..n]的内存使用情况! 0,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/29270658/

10-11 21:07
查看更多