gpt4 book ai didi

performance - Haskell 中是否很好地定义了部分或柯里化(Currying)函数的性能?

转载 作者:行者123 更新时间:2023-12-03 11:38:03 25 4
gpt4 key购买 nike

在以下代码中:

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
where maxel = maximum l

main = do
let mylist = [1, 2, 3, 5]
let ismax = ismaxl mylist
--Is each call O(1)? Does each call remember maxel?
let c1 = ismax 1
let c2 = ismax 2
let c3 = ismax 3
let c5 = ismax 5
putStrLn (show [c1, c2, c3, c5])

偏函数是max,计算maxel吗?特别是,有人可以指出关于 Haskell 中偏函数复杂性的规则吗?编译器必须在上面的例子中只调用一次最大值吗?换句话说,部分函数是否保留了对内部 where 子句的先前调用的引用?

我有一些受 CPU 限制的代码的性能无法接受,我正在寻找可能的错误来推理复杂性。

最佳答案

作为一个演示,你可以从分析你的 Haskell 代码中学到什么,这里是对你的代码进行一些小的修改的结果。首先,我替换了 mylist[0..10000000]以确保计算最大值需要一段时间。

这是运行该版本后分析输出中的一些行:

COST CENTRE                    MODULE               %time %alloc

ismaxl Main 55.8 0.0
main Main 44.2 100.0

individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF:main_c5 Main 225 1 0.0 0.0 15.6 0.0
main Main 249 0 0.0 0.0 15.6 0.0
ismaxl Main 250 1 15.6 0.0 15.6 0.0
CAF:main_c3 Main 224 1 0.0 0.0 15.6 0.0
main Main 246 0 0.0 0.0 15.6 0.0
ismaxl Main 247 1 15.6 0.0 15.6 0.0
CAF:main_c2 Main 223 1 0.0 0.0 14.3 0.0
main Main 243 0 0.0 0.0 14.3 0.0
ismaxl Main 244 1 14.3 0.0 14.3 0.0
CAF:main_c1 Main 222 1 0.0 0.0 10.4 0.0
main Main 239 0 0.0 0.0 10.4 0.0
ismaxl Main 240 1 10.4 0.0 10.4 0.0
CAF:main8 Main 221 1 0.0 0.0 44.2 100.0
main Main 241 0 44.2 100.0 44.2 100.0

很明显,这里重新计算了最大值。

现在,替换 ismaxl有了这个:
ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = let maxel = maximum l in (== maxel)

...并再次进行分析:
COST CENTRE                    MODULE               %time %alloc

main Main 60.5 100.0
ismaxl Main 39.5 0.0

individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc

MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF:main_c5 Main 227 1 0.0 0.0 0.0 0.0
main Main 252 0 0.0 0.0 0.0 0.0
ismaxl Main 253 1 0.0 0.0 0.0 0.0
CAF:main_c3 Main 226 1 0.0 0.0 0.0 0.0
main Main 249 0 0.0 0.0 0.0 0.0
ismaxl Main 250 1 0.0 0.0 0.0 0.0
CAF:main_c2 Main 225 1 0.0 0.0 0.0 0.0
main Main 246 0 0.0 0.0 0.0 0.0
ismaxl Main 247 1 0.0 0.0 0.0 0.0
CAF:main_c1 Main 224 1 0.0 0.0 0.0 0.0
CAF:main_ismax Main 223 1 0.0 0.0 39.5 0.0
main Main 242 0 0.0 0.0 39.5 0.0
ismaxl Main 243 2 39.5 0.0 39.5 0.0
CAF:main8 Main 222 1 0.0 0.0 60.5 100.0
main Main 244 0 60.5 100.0 60.5 100.0

...这次它把大部分时间都花在了一次调用 ismaxl 上。 ,其他人太快了,甚至都没有注意到,所以它必须在这里只计算一次最大值。

关于performance - Haskell 中是否很好地定义了部分或柯里化(Currying)函数的性能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4166924/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com