wie man laufenden Median effizient berechnet

Question

Ich lieh etwas Code aus, der versucht, eine Funktion zu implementieren, um den laufenden Median für eine Tonne von Daten zu berechnen. Der aktuelle ist zu langsam für mich (Der schwierige Teil ist, dass ich alle Nullen von der laufenden Box ausschließen muss). Unten ist der Code:

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 

Es funktioniert gut, der einzige Nachteil ist, dass es zu langsam ist. Könnte mir jemand helfen, den Code zu verbessern, um effizienter zu sein? Vielen Dank.

Nachdem ich alle Möglichkeiten erkundet, kann die folgende einfache Code vergleichbar effizient berechnen:

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 danken.

Answer 1

Ein Ansatz ist unten:

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 

ich eine viel schnellere (zig tausend Mal schneller) gefunden, kopiert, wie unten:

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 

Werfen Sie einen Blick auf den Link: running_median