小编典典

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

algorithm

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

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)]

很好的问题是,当我提交时,我遇到了时间限制执行。我认为问题是for循环,因为当len(l)超过一万时它会花费很多时间。以前我用sum()做平均而是花了很多时间太长,当我把那sum()reduce(lambda a, b: a+b,x)//len(x)算法速度越来越快(它解决了多个测试案例)。我认为,如果不是一个for循环我用另一个函数(如拉姆达)那么问题就解决了。那么您认为有办法吗?感谢您的时间。


阅读 208

收藏
2020-07-28

共1个答案

小编典典

您可以尝试使用numpy.cumsum并获得平均值除以汇总列表的index
+ 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已经非常优化了。如果仍然希望更快,则可以对其进行多线程处理。

2020-07-28