的执行情况（^）

我读的标准哈斯克尔库的实现（^）的代码：的执行情况（^）

(^) :: (Num a, Integral b) => a -> b -> a 
x0^y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
     | y0 == 0 = 1 
     | otherwise = f x0 y0 
    where -- f : x0^y0 = x^y 
      f x y | even y = f (x * x) (y `quot` 2) 
       | y == 1 = x 
       | otherwise = g (x * x) ((y - 1) `quot` 2) x 
      -- g : x0^y0 = (x^y) * z 
      g x y z | even y = g (x * x) (y `quot` 2) z 
        | y == 1 = x * z 
        | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

现在这部分，其中G是定义似乎有些奇怪我为什么不只是实现它像这个：

expo :: (Num a ,Integral b) => a -> b ->a 
expo x0 y0 
    | y0 == 0 = 1 
    | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
    | otherwise = f x0 y0 
    where 
     f x y | even y = f (x*x) (y `quot` 2) 
       | y==1 = x 
       | otherwise = x * f x (y-1)

但的确如此插入3^1000000显示（^）大约比展会快0,04秒。

为什么(^)比expo更快？

来源

2016-07-26 user3726947

这当然不是一个非常戏剧化的问题，但是我认为你的版本效率低下的原因是它将小数字“x”与f的一个大的结果进行了很多倍增。标准版本通过在递归调用之后一直发送剩余因子来生成更平衡的乘法树。 – leftaroundabout

'g'是尾递归，而最后一个'f'不是。我想这里很重要。 – chi

函数是尾递归的，如果递归调用的返回值按原样返回，不做进一步处理。在expo,f不是尾递归，因为otherwise = x * f x (y-1)：在返回之前返回值f乘以x。 f和g中的(^)都是尾递归，因为它们的返回值是未经修改而返回的。

这是为什么？尾递归函数可以比一般递归函数更高效地实现。因为编译器不需要为递归调用创建新的上下文（栈帧，你有什么），所以它可以重用调用者的上下文作为递归调用的上下文。这样可以节省很多调用函数的开销，就像调用一个函数比调用函数更有效。

来源

2016-07-26 13:36:47 chepner

每当你看到在标准库中的面包和奶油的功能，它的古怪实现，其原因几乎总是“因为做这样的触发一些特殊的关键性能优化[可能在不同版本的编译器]“。

这些奇怪的解决方法通常是“强制”编译器注意到某些特定的重要优化是可能的（例如，强制特定参数被认为是严格的，允许工作者/包装器转换，无论如何）。通常一些人编译了他们的程序，发现它很慢，向GHC开发者抱怨，他们看着编译后的代码，并认为“哦，GHC没有看到它可以嵌入第三个工作人员的功能......我如何解决这个问题？“结果是，如果稍微改写代码，那么所需的优化就会触发。

你说你测试过了，速度差别不大。你没有说是什么类型的。（指数是Int还是Integer？基数是多少？这很有可能在一些不太明显的情况下产生显着差异。）

偶尔函数也会被奇怪地实现以保持严格性/懒惰保证。（例如，库规范说它必须以某种方式工作，并且以最明显的方式实现它会使功能比规范声明更严格/更不严格。）

我不知道这是怎么回事具体函数，但我会建议@chi可能是东西。

来源

2016-07-26 13:08:23 MathematicalOrchid

没有什么ghc关于代码的具体细节，它只适用于任何编译器。 – augustss

作为编写代码的人，我可以告诉你为什么它很复杂。 :) 这个想法是尾递归得到循环，并且执行最小数量的乘法。我不喜欢它的复杂性，所以如果你找到更优雅的方式，请提交一份错误报告。

来源

2016-07-26 14:39:46 augustss

我在这段代码中看到'even y'后面加上'y''''''''。如果这个部门是通过一个“quotRem”调用完成的话，它的性能是否会有所提高？ – Cactus

我对此表示怀疑。一个是位测试指令，另一个是移位。 – augustss

如何换班，然后进行检查标志或类似？或者我在这里以6502的方式思考？ – Cactus

的执行情况（^）

回答

相关问题