Lección 24: Scan paralelo (suma de prefijos) — la idea
Un scan, o suma de prefijos, convierte un arreglo en la secuencia de sus sumas acumuladas. En un scan inclusivo, la salida en la posición i es la suma de todos los elementos de 0 a i inclusive: output[i] = in[0] + in[1] + ... + in[i]. Por ejemplo, [3,1,2,4] se convierte en [3,4,6,10]. También existe
Imagina una fila de personas, cada una con un número, y cada una debe terminar con la suma de todos los que están antes, incluida ella misma. En lugar de susurrar de vecino en vecino lentamente, en cada ronda cada una suma el número de quien está un paso a su izquierda, luego dos pasos, luego cuatro. Los saltos se duplican — y toda la fila termina en unas pocas rondas.
- suma de prefijos (prefix sum / scan)
- Convertir un arreglo en sus sumas acumuladas. En un scan inclusivo, output[i] es la suma de in[0..i] inclusive.
- inclusiva vs. exclusiva (inclusive vs exclusive)
- Inclusiva: cada salida incluye el elemento en su posición ([3,1,2,4]->[3,4,6,10]). Exclusiva: empieza en cero y se desplaza a la derecha ([0,3,4,6]).
- la idea de duplicación (doubling)
- En cada ronda, cada elemento suma al vecino que está a una distancia d, y d se duplica (1,2,4,...). Después de log2(n) rondas, cada posición ha acumulado a todos sus predecesores.
- suma acumulada (running total)
- La suma acumulada hasta un punto dado. La versión secuencial la calcula en un bucle en O(n) pasos.
