如何最小化数学调用？ (JavaScript)

Question

我正在做一个 Codewars challenge，其中我必须创建一个函数，其参数 a、b 和 c 对应于二次方程 ax^2 + bx + c = 0 并求解 x。我们的目标不仅是解决 x，而且要尽量减少花费 Math.sqrt 的调用次数。（您还必须 return 一个具有唯一解的数组）。

我想出了一个解决办法：

function solveQuadratic(a, b, c) {
  if ((4*a*c > b*b) || ((a === 0) && (b === 0))) { return undefined;}
  else if (a === 0) {return [-c/b];}
  else {
   var xVals = [];
   var sqrt = Math.sqrt(b*b - 4*a*c);
   xVals.push((-b - sqrt)/2*a);
   xVals.push((-b + sqrt)/2*a);
   if (xVals[0] === xVals[1]) {xVals.pop();}
   return xVals;
  }
}

我收到错误消息：

You passed the tests using 6 Math.sqrt calls. You should be able to pass these tests with 4 Math.sqrt calls or less.

我认为将表达式的平方根部分的结果存储在变量 (sqrt) 中可以防止多次调用它来计算表达式并为变量赋值。但事实并非如此。

所以我有几个问题：

有没有一种方法可以存储（静态）值，以便在您的代码中使用它时无需重新计算？
除了调用太多 Math.sqrt 之外，我是否从这个解决方案中明显遗漏了什么？

Answer 1

一个简单的方法是使用 memoization 。使用闭包来保留所用值的静态列表，这样您就不会为已经计算出的值调用 Math.sqrt

var cachingSqrt = (function() {
    var inputs = {};
    return function(val) {
        if (inputs.hasOwnProperty(val)) {
            return inputs[val];
        } else {
            return inputs[val] = Math.sqrt(val);
        }
    }
})();

这个过程的概括是

function createCachedResults(fn, scope) {
    var inputs = {};
    return function(val) {
        if (inputs.hasOwnProperty(val)) {
            return inputs[val];
        } else {
            return inputs[val] = fn.call(scope, val);
        }
    }
}

cachingSqrt  = createCachedResults(Math.sqrt, Math);

你可以像这样使用它

var cachingSquareRoot = createCachedResults(Math.sqrt, Math);
function solveQuadratic(a, b, c) {
    if ((4*a*c > b*b) || ((a === 0) && (b === 0))) { 
        return undefined;
    }
    else if (a === 0) {
         return [-c/b];
    } else {
        var xVals = [];
        var sqrt = cachingSquareRoot(b*b - 4*a*c);
        xVals.push((-b - sqrt)/2*a);
        xVals.push((-b + sqrt)/2*a);
        if (xVals[0] === xVals[1]) { 
            xVals.pop();
        }
        return xVals;
    }
}

Answer 2

您应该为 discriminant 为零的情况添加快捷方式。

...
else if (b*b == 4*a*c) return [-b / (2*a)];
...

Answer 3

添加 c 为零时的情况：

....
var sqrt = c==0?Math.abs(b):Math.sqrt(b*b - 4*a*c);
....

[编辑]

此外，为了通过所有测试，您的解决方案在此处划分时需要括号：

xVals.push((-b - sqrt)/(2*a));
xVals.push((-b + sqrt)/(2*a));

Answer 4

关键是在x === 0和x === b^2时避免Math.sqrt(x)，因为答案是已知的。这两种情况发生在 b^2 === 4ac 和 4ac === 0 时，因此代码需要将这两种情况短路以避免额外的 Math.sqrt() 调用。

所以，所有的特殊情况是：

当b^2 - 4ac < 0或a === 0 && b === 0使得答案undefined.
当 a === 0（在这种情况下，方程是线性的，而不是二次方程）所以答案是 -c / b。
当 c === 0 使得 4ac === 0 所以它只是 -b / a 和 0.
当 b^2 - 4ac === 0 在这种情况下答案只是 -b / (2 * a)

结合使用 Ruud 的建议和 Joanvo 的固定版本的建议，只需调用 4 Math.sqrt() 次即可通过：

function solveQuadratic(a, b, c) {
    var delta = (b * b) - (4 * a * c), sqrt;
    if ((delta < 0) || ((a === 0) && (b === 0))) {
        return undefined;
    } else if (a === 0) {
        return [-c / b];
    } else if (c === 0) {
        return b === 0 ? [0] : [-b / a, 0];
    } else if (delta == 0) {
        return [-b / (2 * a)];
    } else {
        sqrt = Math.sqrt(delta);
        return [(-b - sqrt) / (2 * a), (-b + sqrt) / (2 * a)];
    }
}

这是一个基于上述版本的版本，并添加了 Juan 的回答中的缓存。在最初的标准测试中，这只报告了一个 Math.sqrt() 操作。

function solveQuadratic(a, b, c) {
    var delta = (b * b) - (4 * a * c), sqrt;
    if ((delta < 0) || ((a === 0) && (b === 0))) {
        return undefined;
    } else if (a === 0) {
        return [-c / b];
    } else if (c === 0) {
        return b === 0 ? [0] : [-b / a, 0];
    } else if (delta == 0) {
        return [-b / (2 * a)];
    } else {
        sqrt = sqrt2(delta);
        return [(-b - sqrt) / (2 * a), (-b + sqrt) / (2 * a)];
    }
}

var sqrt2 = (function() {
    var cache = {0:0, 1:1, 4:2, 9:3};
    return function(x) {
        if (cache.hasOwnProperty(x)) {
            return cache[x];
        } else {
            var result = Math.sqrt(x);
            cache[x] = result;
            return result;
        }
    }
})();

如何最小化数学调用？ (JavaScript)

How to minimize Math calls? (Javascript)

javascript

math