Qual è il miglior algoritmo per trovare la somma di tutti gli elementi in un sub array arbitrario

Question

Ho un problema e una soluzione OK-ish. Spero che ci sia una soluzione migliore là fuori.

Il problema

Ho un array con circa 200.000 numeri interi. Dati due indici, i1 e i2, ho bisogno di calcolare la somma di tutti gli elementi tra i1 e i2. Ogni numero intero dell'array è compreso tra 1 e 4 inclusi. Per esempio:

a = [1, 3, 2, 4, 3, 2, 4, 1]; 
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

Questa operazione sarà eseguita circa 200.000 volte, quindi ha bisogno di essere abbastanza veloce. Un semplice contatore in un ciclo for è O (n), e troppo lento. L'array non viene mai modificato dopo la costruzione, quindi è OK avere una fase di pre-elaborazione relativamente costosa.

Il mio migliore soluzione finora

Questo algoritmo lavora in O (log n):

Il primo rilievo la matrice originale con zeri fino alla sua lunghezza è una potenza di due. Quindi, dividere l'array in due parti uguali e memorizzare la somma di ciascuno. Quindi dividere l'array in quarti e memorizzare la somma di ciascuno. Quindi ottavi. Continuare a fare ciò fino a quando l'array non viene diviso in sezioni di 2 elementi. Per la matrice 8 elementi sopra, questo richiede due fasi:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])] 
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])] 

Poi dato due indici, è ora possibile elaborare la subsection_sum in O (log n). Ad esempio, subsection_sum (a, 2, 7) == quarti [1] + metà [1].

Answer 1

Introdurre un array ausiliario che contiene la somma cumulativa. Cioè, l'elemento i dell'array ausiliario ha la somma degli elementi da 0 a i dell'array originale. La somma del sottoarray è quindi la differenza tra due elementi dell'array ausiliario. Questo darà un risultato in tempo costante, O(1).

Questo dipende da un invariante nel subsection_sum funzione data alla questione ,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

dove sto assumendo i1 <= i2. Riordinando, abbiamo:

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

Nota che le somme sul lato destro entrambi partono da 0. L'array ausiliario può essere visualizzato come il caching dei valori per le somme da zero, subsection_sum(a, 0, i), per tutti i.

Answer 2

Se si può permettere O(n) archiviazione, è possibile creare una tabella di ricerca cui i esimo elemento è la somma degli elementi a indici 0 attraverso i (compreso) nella matrice di input. In pseudocodice:

def computeLookupTable(arr): 
    let n = arr.length 
    let lookupTable = new Array() 

    lookupTable[0] = arr[0] 

    for i=1 to n: 
     lookupTable[i] = arr[i] + lookupTable[i-1] 

    return lookupTable 

quindi è possibile utilizzare questa tabella per calcolare la somma di tutti gli elementi in array tra i1 e i2 prendendo la differenza

lookupTable[i2] - lookupTable[i1] 

che richiede tempo costante.