Ottimizzazione del livellamento esponenziale di un grande array

Question

Ottimizzazione del livellamento esponenziale di un grande array

#1 da (2 voti)

2

Ho un ampio set di valori (diciamo 1M voci) dove devo applicare un algoritmo smoothing esponenziale , ma solo incrementando un valore alla volta (tutto altri decadono a zero). L'implementazione banale sarebbe (pseudo-codice):

function smooth_once(index, x):
    // Decay everything
    for s in s_vec:
        s = s * (1 - alpha)
    // Only increase one value, for the other x=0
    s_vec[index] += alpha * x

function get_s(index):
    return s_vec[index]

Questo è piuttosto lento, poiché ogni elemento di s_vec deve essere scansionato ad ogni iterazione, mentre solo uno deve essere incrementato. Inoltre, ho solo bisogno di controllare alcuni valori da s_vec di tanto in tanto (molto meno frequentemente della frequenza con cui viene chiamato smooth_once ).

Nota: la sequenza di levigatura e lettura è imprevedibile ed è solitamente interlacciata, ad esempio:

smooth_once(6573, 1.23)
get_s(8892)
smooth_once(3345, 2.45)
smooth_once(6874, 1.10)
get_s(3345)
get_s(1254)
...etc...

Per accelerare ciò, stavo pensando di moltiplicare il valore x di un fattore ( scale ) che viene moltiplicato ogni volta e dividendo tutto quando il fattore diventa troppo grande. Fondamentalmente, questo si riduce a ridimensionare tutto con un fattore di incremento esponenziale .

scale = 1
k = 1 / (1 - alpha)
function optimized_smooth(index, x):
    // Rescale everything
    scale = scale * k
    if scale > scale_max:
        // Switch back scale to 1
        for s in s_vec:
            s = s / scale
        scale = 1
    s_vec[index] = v + alpha * x * scale

function get_s(index):
    // Scale back for reading
    return s_vec[index] / scale

IMHO questo sarebbe molto più veloce (supponendo che k non sia troppo grande), poiché devi solo scansionare s_vec quando l'overflow della scala e ridimensionare l'intero array.

Cosa ne pensi di questo metodo?
È già noto e ha un nome?
Oltre a perdere qualche bit di precisione sui valori (a seconda di beta_max), vedi qualche svantaggio?

Addendum. Un piccolo programma dimostrativo mostra che entrambi gli algoritmi finiscono con lo stesso risultato su una sequenza controllata di indici uniformi.

performance algorithms math algorithm-analysis

posta Laurent Grégoire 17.05.2016 - 14:20

fonte

1 risposta

Leggi altre domande sui tag performance algorithms math algorithm-analysis

Progettazione dello storage per diversi sistemi temporali In SemVer 2.0.0, che tipo di categoria di modifica dell'API pubblica è l'aggiunta di una nuova eccezione?

score 2 · Answer 1

Dopo aver riflettuto due volte sulla tua soluzione, sono sicuro che il tuo algoritmo funziona bene. IMHO potrebbe essere visto come una variante della valutazione pigra . Ecco un'altra variante.

Modifica smooth_once in modo che inserisce le coppie (index,x) in una coda (consente di chiamare le matrici indexes e xs ).

function smooth_once(index, x):
   indexes.append(index)
   xs.append(x)

Ecco il metodo per calcolare contemporaneamente il livellamento per l'intera coda:

function nth_smooth(indexes, xs):
    n = size(indexes)  // equal to size(xs)
    if n==0: 
        return
    cn = (1-alpha) ** n // (1-alpha) to the power of n
    for s in s_vec:
        s = s * cn
    c=1
    for i = 0 to n-1:
       s_vec[indexes[i]] += alpha * xs[i] *c
       c = c * (1-alpha)

Ed ecco il metodo per recuperare il risultato:

function get_s(index):
    nth_smooth(indexes,xs)
    indexes.clear()
    xs.clear()
    return s_vec[index]

Suppongo che non sia troppo difficile capire perché funzioni, sostituisce semplicemente le moltiplicazioni ripetute di s_vec con 1-alpha di una moltiplicazione con (1-alpha) ** n , e aggiunge le aggiunte "x * alfa" in seguito, prendendo l'influenza di 1-alpha su quelle pertensanze in considerazione.

Tuttavia, se questo sarà più veloce o più lento della tua proposta dipende dal numero di chiamate di smooth_once prima del prossimo get_s , rispetto alla frequenza di avere la condizione scale > scale_max soddisfatta (nella tua variante ).