Урок 24: Параллельное сканирование (префиксная сумма) — идея
Сканирование, или префиксная сумма, превращает массив в последовательность его накопительных сумм. При включающем (inclusive) сканировании выход в позиции i — это сумма всех элементов от 0 до i включительно: output[i] = in[0] + in[1] + ... + in[i]. Например, [3,1,2,4] превращается в [3,4,6,10]. Суще
Представьте ряд людей, у каждого в руках число, и каждый должен в итоге держать сумму всех, кто перед ним, включая себя самого. Вместо того чтобы медленно шептать от соседа к соседу, в каждом раунде каждый прибавляет число человека на один шаг левее, затем на два шага, затем на четыре. Прыжки удваиваются — и весь ряд заканчивает всего за несколько раундов.
- префиксная сумма / сканирование (prefix sum / scan)
- Превращение массива в его накопительные суммы. При включающем сканировании output[i] — это сумма in[0..i] включительно.
- включающее против исключающего (inclusive vs exclusive)
- Включающее: каждый выход включает элемент на своей позиции ([3,1,2,4]->[3,4,6,10]). Исключающее: начинается с нуля и сдвигает вправо ([0,3,4,6]).
- идея удвоения (doubling)
- Каждый раунд каждый элемент прибавляет соседа на расстоянии d, и d удваивается (1,2,4,...). После log2(n) раундов каждая позиция накопила всех предшественников.
- накопительная сумма (running total)
- Сумма, накопленная до определённой точки. Последовательная версия вычисляет её в одном цикле за O(n) шагов.
