提高 JavaScript 函数的速度

Question

我在 CodeWars 上找到了一个任务，我设法解决了它，但是，提交后说：

执行超时：（12000 毫秒）

当我尝试测试该函数是否通过时，但我猜它太慢了。在你谴责我没有自己找到答案之前。我并不真正关心将其作为回复提交，但我不知道如何使其更快，这就是我在这里的原因。这是函数：

const ls = [0, 1, 3, 6, 10]

const partsSums = (ls) => {
    const sum = []
    for(let i = 0, len = ls.length; i < len + 1; i++) {
        let result = ls.slice(i).reduce( (accumulator, currentValue) => accumulator + currentValue, 0)
        sum.push(result)
    }
    return sum
}

以下是说明：

让我们考虑这个例子（以通用格式编写的数组）：

ls = [0, 1, 3, 6, 10]

其以下部分：

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

相应的和是（放在一个列表中）：[20, 20, 19, 16, 10, 0]

函数parts_sums（或其在其他语言中的变体）将把一个列表ls作为参数，并返回一个上面定义的各部分总和的列表。

Answer 1

对于这种数组操作，最好不要使用内置方法，例如slice或reduce，因为与for循环或任何其他循环方法相比，它们速度较慢。

这种方法采用单循环，并使用索引获取给定数组的值，并获取新数组的最后一个总和。

Codewars 的一些速度测试：部分总和：

• 稀疏数组为5621 毫秒sum = []; sum[i] = 0;（此答案的第一个版本），
• 有Array(i + 1).fill(0)和没有3452 毫秒sum[i] = 0;，
• 1261毫秒与Array(i + 1)和sum[i] = 0;（在下面找到），
• Icepickle 的第一次尝试耗时3733 毫秒。

const
    partsSums = (ls) => {
        let i = ls.length;
        const sum = Array(i + 1);

        sum[i] = 0;
        while (i--) sum[i] = sum[i + 1] + ls[i];

        return sum;
    },
    ls = [0, 1, 3, 6, 10];

console.log(...partsSums(ls));

Answer 2

您仍然可以采用更实用的方法，但要优化您进行计算的方式。

这是一个想法 - 因为你试图对所有项目求和，然后对除第一个以外的所有项目求和，然后对除第二个以外的所有项目求和，等等，在数学上等同于获得总和，然后按顺序从中减去每个数字并保持总数.

[sum([41, 42, 43]), sum([42, 43]), sum([43]), sum([])]

是相同的：

total = sum([41, 42, 43])
[total - 0, total - 0 - 41, total - 0 - 41 - 42, total - 0 - 41 - 42- 43]

是相同的：

total = sum([41, 42, 43])
[total -= 0, total -= 41, total -= 42, total -= 43]

概括地说，这看起来像：

total = sum([a1, a2, ..., aN])
[total -= 0, total -= a1, total -= a2, ..., total -= aN]

使用trusty，Array#reduce我们可以得出一次总和。然后我们可以使用Array.mapusing派生新数组ls.map(num => total -= num)。

这里唯一的问题是我们少了一个项目——我们不计算total -= 0所有项目必须存在的初始值。一种方法是将它附加到开始[0].concat(ls)将创建正确的数组来映射。不过，既然我们已经知道会有什么值了，我们可以跳过这一步，直接用with替换total（毕竟total -= 0istotal和leaves的结果total不变）。所以，我们可以直接使用[total].concat(ls.map(num => total -= num))to start with 来total添加其余的项目。到最后。

[sum([41, 42, 43]), sum([42, 43]), sum([43]), sum([])]