查找expmod的三元条件？

debugcn 发表于 Dev

结石

我正在阅读JS中的SICP，以了解三元条件的非终止示例：

function is_even(n) {
    return n % 2 === 0;
}

function expmod(base, exp, m) {
    const half_exp = expmod(base, exp / 2, m);
    return exp === 0 ? 1
           : is_even(exp) ? half_exp * half_exp % m
           : base * expmod(base, exp - 1, m) % m;
}

console.log(expmod(4, 3, 5))

它解释说：

这将使函数不仅效率低下，而且实际上是不终止的！问题在于常量声明出现在条件表达式的外部，这意味着即使满足基本情况exp === 0，它也会被执行。

我只是不明白它的想法，当exp === 0时，它以1结尾，但是为什么要执行half_exp？

防区

您误解的部分是变量的初始化方式和时间，而不是三元的工作方式。如果口译员到达，三元会按照您的想法工作。

您已将half_exp变量放入条件表达式中，并期望它在使用之前不求值其初始化程序。

但是，这不是它的工作方式。

所有变量初始化语句（两者var，let和const）评估其立即初始化当控制到达语句，而不检查变量是否以后使用; 并将初始值设定项的值存储到变量中。

您可以通过运行以下代码段查看它：

const foo = console.log("I'm executed!")
//`foo` is never used, but the code will print "I'm executed!" anyway

您也可以通过查看ECMAScript规范来确认这一点。

LexicalBinding ： BindingIdentifier 初始化程序

令bindingId为BindingIdentifier的StringValue 。

设lhs为ResolveBinding（bindingId）。

如果IsAnonymousFunctionDefinition（Initializer）为true，则

一种。令value为带有参数bindingId的Initializer的NamedEvaluation。

其他，

一种。令rhs为评估Initializer *的结果。
b。让价值成为？GetValue（rhs）。

返回InitializeReferencedBinding（lhs，value）。

_{*：重点是我的。}

因此，如您所见，解释器不会等待变量被使用。

这意味着在您的代码中：

      // v-------------------------------------------+
function expmod(base, exp, m) {                   // |
    const half_exp = expmod(base, exp / 2, m); // ---+
                  // ^^^^^^--- This will always be called
    // This line is not even reached!
    return exp === 0 ? 1
           : is_even(exp) ? half_exp * half_exp % m
           : base * expmod(base, exp - 1, m) % m;
}

...您可以无限递归。

要解决此问题，我们必须将该调用移至条件部分。在您的代码中，这很容易，因为我们可以自己将值提高到第二幂，而不用自己编写乘法，从而消除引用之一：

function is_even(n) {
    return n % 2 === 0;
}

function expmod(base, exp, m) {
    return exp === 0 ? 1
           : is_even(exp) ? expmod(base, exp / 2, m) ** 2 % m
           : base * expmod(base, exp - 1, m) % m;
}

console.log(expmod(4, 3, 5)) //4

在其他情况下，如果没有这样简单的方法，我们可以通过其他方式重构代码，例如，使用ifs：

function is_even(n) {
    return n % 2 === 0;
}

function expmod(base, exp, m) {
    if(exp === 0)
      return 1;
    if(is_even(exp)){
      // We are in a conditional statement, so it's safe to call:
      const half_exp = expmod(base, exp / 2, m)
      return half_exp * half_exp % m
    }
    return base * expmod(base, exp - 1, m) % m;
}

console.log(expmod(4, 3, 5)) //4

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。