Сегментированное сканирование

В информатике сегментированное сканирование — это модификация префиксной суммы с помощью массива битов флагов одинакового размера для обозначения границ сегмента, на котором должно выполняться сканирование.

Пример

Далее биты флага «1» указывают начало каждого сегмента.

${\begin{array}{|rrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\\hline 1&0&0&1&0&1&{\text{flag bits}}\\\hline 1&3&6&4&9&6&{\text{segmented scan +}}\\\end{array}}$

Группа1

• 1 = 1
• 3 = 1 + 2
• 6 = 1 + 2 + 3

Группа2

• 4 = 4
• 9 = 4 + 5

Группа3

• 6 = 6

Альтернативный метод, используемый High Performance Fortran, — начинать новый сегмент при каждом переходе значения флага. Преимущество этого представления состоит в том, что оно полезно как при префиксном, так и при суффиксном (обратном) сканировании без изменения его интерпретации. В HPF для представления сегментов используется логический тип данных Фортрана. Таким образом, эквивалентный массив флагов для приведенного выше примера будет следующим:

${\begin{array}{|rrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\\hline T&T&T&F&F&T&{\text{flag values}}\\\hline 1&3&6&4&9&6&{\text{segmented scan +}}\\\end{array}}$

См. также

• Сглаживающее преобразование