How to reduce execution time in algorithm by repla

Question

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.

Answer 1

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.

Answer 2

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] 

Answer 3

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([]))
# []

Answer 4

Some ideas:

1. 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.
2. 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.

Answer 5

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.

Answer 6

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.