¿Cuál es el mejor algoritmo para encontrar la suma de todos los elementos de un " sub matriz

Question

Tengo un problema, y un OK-ish solución.Tengo la esperanza de que hay una mejor solución que existe.

El problema

Tengo un array con alrededor de 200.000 enteros.Dadas dos índices, i1 e i2, necesito calcular la suma de todos los elementos entre i1 e i2.Cada entero en el array es de entre 1 y 4, ambos 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 realiza alrededor de 200.000 veces, así que debe ser bastante rápido.Un simple contador en un bucle es O(n), y demasiado lento.La matriz no se modifica nunca, después de la construcción, por lo que está bien tener un relativamente caro pre-etapa de procesamiento.

Mi mejor solución hasta el momento

Este algoritmo funciona en O(log n) tiempo:

Primera almohadilla de la matriz original con ceros hasta que su duración es de una potencia de dos.Siguiente, dividir el conjunto en dos partes iguales y almacenar la suma de cada uno.A continuación, dividir la matriz en cuartos y almacenar la suma de cada uno.Entonces octavos.Siga haciendo esto hasta que la matriz se divide en las secciones 2 elementos de largo.Para el 8-elemento de la matriz anterior, esto se hace en 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 se dan dos índices, ahora es posible trabajar la subsection_sum en O(log n) tiempo.Por ejemplo, subsection_sum(a, 2, 7) == cuartas partes[1] + mitades[1].

Answer 1

Introducir un auxiliar de la matriz que contiene la suma acumulativa.Eso es, el elemento i de los auxiliares de la matriz de la suma de los elementos de la 0 a la i de la matriz original.El subarray suma es entonces sólo la diferencia de dos elementos de la auxiliar de la matriz.Esto dará un resultado en tiempo constante, O(1).

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

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

donde estoy suponiendo i1 <= i2.Reordenando, tenemos:

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

Tenga en cuenta que la suma en el lado derecho de puesta en marcha de 0.El auxiliar de la matriz puede ser visto como el almacenamiento en caché de los valores de las sumas de cero, subsection_sum(a, 0, i), para todos i.

Answer 2

Si usted puede permitirse el lujo de O(n) espacio de almacenamiento adicional, usted puede crear una tabla de búsqueda cuyo ith elemento es la suma de los elementos en los índices de 0 a través de i (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

A 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 toma tiempo constante.