как правильно вычислить эффективность срединной обработки

Question

Я заимствовал код, пытающийся реализовать функцию для вычисления текущей медианы для тонны данных. Текущий слишком медленный для меня (Трудная часть заключается в том, что мне нужно исключить все нули из подгонки). Ниже приведен код:

from itertools import islice 
from collections import deque 
from bisect import bisect_left,insort 

def median(s): 
    sp = [nz for nz in s if nz!=0] 
    print sp 
    Mnow = len(sp) 
    if Mnow == 0: 
     return 0 
    else: 
     return np.median(sp) 

def RunningMedian(seq, M): 
    seq = iter(seq) 
    s = [] 

    # Set up list s (to be sorted) and load deque with first window of seq 
    s = [item for item in islice(seq,M)] 
    d = deque(s) 

    # Sort it in increasing order and extract the median ("center" of the sorted window) 
    s.sort() 
    medians = [median(s)] 
    for item in seq: 
     old = d.popleft()   # pop oldest from left 
     d.append(item)    # push newest in from right 
     del s[bisect_left(s, old)] # locate insertion point and then remove old 
     insort(s, item)   # insert newest such that new sort is not required   
     medians.append(median(s)) 
    return medians 

Это хорошо работает, единственный недостаток в том, что он слишком медленный. Любой может помочь мне улучшить код, чтобы быть более эффективным? Благодарю.

После того как я исследовал все возможности, следующий простой код можно рассчитать сравнительно эффективно:

def RunningMedian(x,N): 
    idx = np.arange(N) + np.arange(len(x)-N+1)[:,None] 
    b = [row[row>0] for row in x[idx]] 
    return np.array(map(np.median,b)) 
    #return np.array([np.median(c) for c in b]) # This also works 

Спасибо @Divakar.

Answer 1

Один подход ниже:

def RunningMedian(x,N): 
    idx = np.arange(N) + np.arange(len(x)-N+1)[:,None] 
    b = [row[row>0] for row in x[idx]] 
    return np.array(map(np.median,b)) 
    #return np.array([np.median(c) for c in b]) # This also works 

я нашел гораздо быстрее, один (десятки тысяч раз быстрее), скопированный, как показано ниже:

from collections import deque 
from bisect import insort, bisect_left 
from itertools import islice 
def running_median_insort(seq, window_size): 
    """Contributed by Peter Otten""" 
    seq = iter(seq) 
    d = deque() 
    s = [] 
    result = [] 
    for item in islice(seq, window_size): 
     d.append(item) 
     insort(s, item) 
     result.append(s[len(d)//2]) 
    m = window_size // 2 
    for item in seq: 
     old = d.popleft() 
     d.append(item) 
     del s[bisect_left(s, old)] 
     insort(s, item) 
     result.append(s[m]) 
    return result 

гляньте по ссылке: running_median