执行超时(12000 毫秒):如何优化这个简单的 kata 以更快地运行

Question

经过长时间的休息后，我正在练习我的编码技巧，并在CodeWars上遇到了这个kata。

在数组中输入数字，返回其各部分的总和。所以例如：

def parts_sums(ls)
 sums = []
  until ls.size == 0
    sums << ls.inject(:+)
    ls.shift
  end
  sums << 0
end
######### INPUT #######
parts_sums([0, 1, 3, 6, 10])
######### EXPECTED OUTPUT ######
[20, 20, 19, 16, 10, 0]
0 + 1 + 3 + 6 + 10 = 20
1 + 6 + 3 + 10 = 20
3 + 6 + 10 = 19
6 + 10 = 16
10 = 10 
0 = 0

我的解决方案解决了kata，但是一旦我达到大约30,000+的数组，我的解决方案就需要很长时间才能解决。

所以我的问题是社区，我如何尝试让它更快。我知道递归通常很慢，而 for 循环及其变体通常足以完成工作。失败时会发生什么？有哪些事情可以尝试使我的上述代码更快？

我正在寻找一些建议和一些例子，如果有人有的话。感谢输入。谢谢。

Answer 1

def parts_sums(ls)
  ls.each_with_object([ls.sum]) { |n,arr| arr << arr.last - n }
end
parts_sums([0, 1, 3, 6, 10])
  #=> [20, 20, 19, 16, 10, 0] 

Answer 2

代码的问题在于，您在循环的每次迭代中都执行inject，这太慢了。

您只需在任何循环之外对数组的元素求和一次。获得该总和后，您可以遍历数组的元素，并从当前总和中执行恒定时间减法并将其推送到sums数组中。

def part_sums(ls)
  sum = ls.inject(:+)
  sums = [sum]
  ls.each do |val|
    sum -= val
    sums << sum
  end
  sums
end

如果您使用 each 迭代器遍历数组或保留计数器并使用 while 循环，也无需移位。

Answer 3

此版本的函数运行速度要快得多：

def parts_sums_2(ls)
 sums = []
 last_sum = 0
 (ls.length - 1).downto(0).each do |i|
   last_sum += ls[i]
   sums.prepend last_sum
 end
 sums + [0]
end

这里的键是向后浏览数组 - 从最小的总和(只有最后一个元素(开始。随后的每个步骤都会将一个索引移向开头，并将该值添加到前一个总和中。

由于问题陈述要求您移动每个步骤，因此您的结果必须在开始时具有最大的总和，即使这些是最后要计算的总和。这就是为什么我的代码使用前置而不是推送。

这是 O(N( 时间复杂度，而不是 O(N^2(，这是一个数量级的差异。

对于 100_000 个输入，您的原始函数需要 7.040443 秒，而我的函数需要 0.000008 秒

此外，一般来说，您应该尽量避免改变方法的输入(就像您在 shift 中所做的那样(。