Как бы вы оптимизировали этот простой, но медленный Python 'для' l oop?

Question

По сути, у меня есть функция, которая для каждой строки суммирует одно дополнительное значение выше, пока сумма не достигнет заданного порогового значения. Как только он достигает заданного порогового значения, он берет полученный индекс среза и использует его для возврата среднего значения этого среза другого столбца.

import numpy as np

#Random data:
values = np.random.uniform(0,10,300000)
values2 = np.random.uniform(0,10,300000)
output = [0]*len(values)

#Function that operates one one single row and returns the mean
def function(threshold,row):
    slice_sum=0
    i=1
    while slice_sum < threshold:
        slice_sum = values[row-i:row].sum()
        i=i+1        
    mean = values2[row-i:row].mean()
    return mean


#Loop to iterate the function row by row:
for i in range(15,len(values)): #let's just skip the first 15 values, otherwise the loop might get stuck. This issue is not prioritary though.
    output[i] = function(40,i)

Это упрощенная версия l oop. Это может выглядеть не медленно, но очень медленно для всех целей и практических целей. Так что мне интересно, есть ли более быстрый способ достичь этого без for l oop.

Спасибо

Answer 1

Вам не нужно пересчитывать сумму каждый раз через l oop. Вы начинаете с values[row-1:row] (одно значение) и, если оно достаточно мало, добавляете дополнительное значение. Вместо того, чтобы повторно суммировать итерации тех же значений после итерации, просто увеличьте предыдущую сумму следующим значением.

def function(threshold, row):
    slice_sum = 0
    for i in range(1, len(values)+1):
        slice_sum += values[row-i]
        if slice_sum >= threshold:
            break
    return values2[row-i-1:row].mean()

Это уменьшает количество операций сложения с O (n ^ 2) до O (n) .

Answer 2

Используйте поиск по совокупной сумме values, чтобы перейти непосредственно к следующей группе. Это даст вам производительность O (n log n), где n - количество групп в значениях:

import numpy as np

def meanBlocks(values,values2,threshold):
    sums = np.cumsum(values)
    i = j = k = 0
    output = np.zeros(values.size)
    while j < values.size:
        s = sums[j]-values[j]+threshold     # s is next cumsum to reach
        i,j = j,np.searchsorted(sums,s)     # position of next increment by threshold 
        output[k] = np.mean(values2[i:j])   # track mean of values2 for range
        k += 1
    return output[:k]

выходы:

values  = np.arange(10)
values2 = np.arange(10)*5
print(values)
print(values2)
print(meanBlocks(values,values2,13))

[0 1 2 3 4 5 6 7 8 9]           #   (0+1+2+3+4)    (5+6)     (7)   ...   
[ 0  5 10 15 20 25 30 35 40 45] # (0,5,10,15,20)  (25,30)    (35)  ...
[10.  27.5 35.  40.  45. ]      #   50/5 = 10    55/2=27.5    35   ...


print("")
values    = np.random.uniform(0,10,300000)
values2   = np.random.uniform(0,10,300000)
print(values)
print(values2)
print(meanBlocks(values,values2,40)) # takes 0.43 sec on my laptop

[6.79333765 2.22880971 1.37706989 ... 8.75649835 2.92422716 5.1280224 ]
[3.56901367 0.15243962 6.76291706 ... 4.47662928 2.61969948 8.0941208 ]
[4.88477774 3.87464821 5.42599828 ... 4.47055786 4.48768768 5.17582407]