¿Cuál es el mejor algoritmo para encontrar la suma de todos los elementos en una matriz secundaria arbitraria

Question

Tengo un problema y una solución OK-ish. Espero que haya una mejor solución por ahí.

El problema

que tienen una matriz con alrededor de 200.000 números enteros. Dado dos índices, i1 e i2, necesito calcular la suma de todos los elementos entre i1 e i2. Cada número entero en la matriz está entre 1 y 4 inclusive. Por ejemplo:

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

Esta operación se realizará alrededor de 200.000 veces, por lo que tiene que ser bastante rápido. Un contador simple en un ciclo for es O (n), y demasiado lento. La matriz nunca se modifica después de la construcción, por lo que está bien tener una etapa de procesamiento previo relativamente costosa.

Mi mejor solución hasta ahora

Este algoritmo trabaja en O (log n) tiempo:

primera almohadilla de la matriz original con ceros hasta su longitud es una potencia de dos. Luego, divida la matriz en dos partes iguales y almacene la suma de cada una. Luego divida la matriz en cuartos y almacene la suma de cada uno. Luego octavos. Continúa haciendo esto hasta que la matriz se divida en secciones de 2 elementos de largo. Para la matriz de 8 elementos anteriormente, esto da dos pasos:

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])] 

Entonces da dos índices, ahora es posible trabajar a cabo la subsection_sum en O (log n). Por ejemplo, subsection_sum (a, 2, 7) == trimestres [1] + mitades [1].

Answer 1

Introduzca una matriz auxiliar que contenga la suma acumulativa. Es decir, el elemento i de la matriz auxiliar tiene la suma de los elementos 0 a i de la matriz original. La suma del subcampo es entonces solo la diferencia de dos elementos de la matriz auxiliar. Esto dará un resultado en tiempo constante, O(1).

Esto depende de una invariante en el subsection_sum función dada en la pregunta ,:

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

donde yo estoy asumiendo i1 <= i2. Reordenando, tenemos:

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

Tenga en cuenta que las sumas en el lado derecho de ambos parten de 0. La matriz auxiliar se puede ver como almacenar en caché los valores de las sumas desde cero, subsection_sum(a, 0, i), para todos i.

Answer 2

Si se lo puede permitir O(n) almacenamiento adicional, puede crear una tabla de consulta cuya i ésimo elemento es la suma de los elementos a través de los índices 0i (ambos inclusive) en la matriz de entrada. En pseudocódigo:

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 

continuación, puede utilizar esta tabla para calcular la suma de todos los elementos en array entre i1 y i2 tomando la diferencia

lookupTable[i2] - lookupTable[i1] 

que lleva tiempo constante.