可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
I'm trying to solve an algorithm problem,consider the following list:
l = [100, 20, 50, 70, 45]
in this problem I have to find the average of the elements up to index i:
i = 0
100
i = 1
(100 + 20) //2 = 60
i = 2
(100+20+50) // 3 = 56
...
the final result should be stored in a list:
[100, 60, 56, 60, 57]
this is my code so far:
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)]
It works fine the problem is that when I submitted it, I faced a time limit execution.I think the problem is the for loop since it takes a lot of time when len(l)
is more than ten-thousand. Previously I used sum()
to do the averaging but that took a lot of time too, when I turned that sum()
to reduce(lambda a, b: a+b,x)//len(x)
the algorithm got faster(It solved more test cases).I think that if instead of an for loop I use another function(like lambda) then the problem is solved.So do you think there is a way? thank you for your time.
回答1:
You can try to use numpy.cumsum
and get the average dividing by the index+1 of the cumsum list.
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]
It should be pretty fast, O(n), since numpy.cumsum
is very optimized already. If you still want it faster you could multithread it.
回答2:
That is because you sum the whole array each time so the cost is quadratic, but can be linear if you reuse the previous result each time. Think about it.
回答3:
Some ideas:
- Each time you run the
av
function, it reduces the whole list. Since calling av
in your list comprehension, you're calling av
more times than you need. You should be calculating your list of sums (using av
) only once, and deriving your sums as you iterate through l
.
- Since you are only summing up to
i
, you shouldn't be reducing the whole list. You should be slicing the first list l[:i]
, then running your reduce()
against the shortened list.
回答4:
As complete solutions have already spoiled the game, here is a working one in O(n).
Note that you can very often avoid manipulating indices yourself in Python. Here, we can use enumerate
with a start value of 1 to keep track of the number of values we summed.
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
Some tests:
lst = [100, 20, 50, 70, 45]
print(means(lst))
# [100.0, 60.0, 56.666666666666664, 60.0, 57.0]
print(means([]))
# []
回答5:
What you want to do is iterate only once on the list:
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]
For using the previous results i take the previous sum (which is the prev avg * i), add the new number, and divide it by i+1.
回答6:
It can be implemented with linear time complexity i.e O(n). A sample can be as follows just to give you an idea, how can you do it.
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]