如何通过替换 python 中的 for 循环来减少算法的执行时间

Question

我正在尝试解决算法问题，请考虑以下列表：

l =  [100, 20, 50, 70, 45]

在这个问题中，我必须找到索引 i:

之前的元素的平均值

i = 0
100
i = 1
(100 + 20) //2 = 60
i = 2
(100+20+50) // 3 = 56
...

最终结果应存储在列表中：

[100, 60, 56, 60, 57]

到目前为止，这是我的代码：

from functools import reduce
def meanScores(l):
      def av(x):
            return reduce(lambda a, b: a+b,x)//len(x)

      return [av(l[:i]) for i in range(1,len(l)+1)]

它工作正常问题是当我提交它时，我遇到了时间限制execution.I认为问题是for循环，因为当len(l)超过时它需要很多时间一万。以前我用 sum() 做平均，但是这也花了很多时间，当我把 sum() 变成 reduce(lambda a, b: a+b,x)//len(x) 算法变得更快（它解决了更多的测试用例）。我认为如果我使用另一个函数（如 lambda）而不是 for 循环，那么问题是 solved.So 你认为有办法吗？谢谢你的时间。

Answer 1

这是因为每次对整个数组求和，所以成本是二次方的，但如果每次都重复使用以前的结果，则可以是线性的。想想看。

Answer 2

您可以尝试使用 numpy.cumsum 并得到除以 cumsum 列表的索引+1 的平均值。

import numpy as np

l =  [100, 20, 50, 70, 45]

l_cumsum = np.cumsum(l)
l_indices = np.arange(1,len(l)+1,1)
l_average = np.divide(l_cumsum, l_indices).tolist()

print(l_average) # Outputs [100.0, 60.0, 56.666666666666664, 60.0, 57.0]

它应该很快，O(n)，因为 numpy.cumsum 已经非常优化了。如果你仍然想要它更快，你可以多线程它。

Answer 3

您要做的是在列表中只迭代一次：

i = [10,20,30,40,50,60,70]


def meanScores(l):
    if len(l) == 0: #Check is its an empty list
        return []
    res = [l[0]] #the first item is the first item in both lists(l)):
        res.append(float((res[i-1]*i + l[i])) / (i+1)) #Use the previous result to calculate the new result
    return [int(x) for x in res]

为了使用之前的结果，我取之前的总和（即 prev avg * i），加上新的数字，然后除以 i+1。

Answer 4

一些想法：

每次运行 av 函数时，它都会减少整个列表。由于在您的列表理解中调用 av，您调用 av 的次数超出了您的需要。您应该只计算一次总和列表（使用 av），并在迭代 l.
由于您只对 i 求和，因此不应减少整个列表。您应该对第一个列表 l[:i] 进行切片，然后运行将您的 reduce() 与缩短的列表相对应。

Answer 5

由于完整的解决方案已经破坏了游戏，这里是 O(n) 中的有效解决方案。

请注意，在 Python 中，您通常可以避免自己操作索引。在这里，我们可以使用起始值为 1 的 enumerate 来跟踪我们求和的值的数量。

def means(lst):
    sum = 0
    out = []
    for n, new_val in enumerate(lst, 1): # we enumerate starting with n=1
        sum += new_val
        out.append(sum/n)
    return out

一些测试：

lst =  [100, 20, 50, 70, 45]
print(means(lst))
# [100.0, 60.0, 56.666666666666664, 60.0, 57.0]

print(means([]))
# []

Answer 6

它可以用线性时间复杂度实现，即O(n)。一个例子可以如下只是给你一个想法，你怎么做。

l =  [100, 20, 50, 70, 45]

a = [0] * len(l)

a[0] = l[0]

temp = a[0]

for i in range(1, len(l)):
    a[i] = (temp + l[i]) / (i + 1)
    temp = temp + l[i]

print(a)

Output
[100, 60.0, 56.666666666666664, 60.0, 57.0]

如何通过替换 python 中的 for 循环来减少算法的执行时间

How to reduce execution time in algorithm by replacing for loop in python

python

algorithm

execution-time