Segmenterad skanning

Inom datavetenskap är en segmenterad skanning en modifiering av prefixsumman med en lika stor array av flaggbitar för att ange segmentgränser på vilka skanningen ska utföras.

Exempel

I det följande indikerar "1"-flaggabitarna början av varje segment.

${\begin{array}{|rrrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\\hline 1&0&0&1&0 {\text{flaggabitar}}\\\hline 1&3&6&4&9&6&{\text{segmenterad skanning +}}\\\end{array}}$

Grupp1

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

Grupp 2

• 4 = 4
• 9 = 4 + 5

Grupp3

• 6 = 6

En alternativ metod som används av High Performance Fortran är att starta ett nytt segment vid varje övergång av flaggvärde. En fördel med denna representation är att den är användbar med både prefix och suffix (bakåt) skanningar utan att ändra dess tolkning. I HPF används Fortran logisk datatyp för att representera segment. Så motsvarande flaggarray för exemplet ovan skulle vara följande:

${\begin{array}{|rrrrrrr|l|}1&2&3&4&5&6&{\text{input}}\\ \hline T&T&T&F&F&T&{\text{flaggavärden}}\\\hline 1&3&6&4&9&6&{\text{segmenterad skanning +}}\\\end{array}}$