Aula 24: Scan Paralelo (Soma de Prefixos) — a Ideia
Um scan, ou soma de prefixos, transforma um array na sequência das suas somas acumuladas. Num scan inclusivo, a saída na posição i é a soma de todos os elementos de 0 até i, incluindo i: output[i] = in[0] + in[1] + ... + in[i]. Por exemplo, [3,1,2,4] vira [3,4,6,10]. Também existe uma variante exclu
Imagine uma fileira de pessoas, cada uma segurando um número, e cada uma precisa terminar segurando a soma de todos que vêm antes dela, incluindo ela mesma. Em vez de sussurrar de vizinho para vizinho lentamente, a cada rodada todo mundo soma o número da pessoa um passo à sua esquerda, depois dois passos, depois quatro. Os saltos dobram — e a fileira inteira termina em poucas rodadas.
- soma de prefixos / scan
- Transformar um array nas suas somas acumuladas. Num scan inclusivo, output[i] é a soma de in[0..i], incluindo i.
- inclusivo vs exclusivo
- Inclusivo: cada saída inclui o elemento na sua posição ([3,1,2,4]->[3,4,6,10]). Exclusivo: começa em zero e desloca para a direita ([0,3,4,6]).
- a ideia da duplicação
- A cada rodada, todo elemento soma o vizinho a uma distância d, e d dobra (1,2,4,...). Depois de log2(n) rodadas, cada posição acumulou todos os predecessores.
- total acumulado
- A soma acumulada até um determinado ponto. A versão sequencial a calcula num único loop, em O(n) passos.
