Algorithm for efficient scale down of 2d boolean array

I have a 2D boolean array for example:

``````01000000
01110000
00110000
01100000
00100000
00111100
00000000
00000000
``````

What I want is to efficiently create a scaled representation for this array according to some size, in example, if the size is 4x4 then the above array will be paratitioned to some 4x4 parts:

``````0100 0000
0111 0000
0011 0000
0110 0000

0010 0000
0011 1100
0000 0000
0000 0000
``````

and in every part, if there is at least 1 true value the whole part gets "true" so the result of 4x4 partition will be:

``````10
11
``````

another example, 3x3 partition:

``````010 000 00
011 100 00
001 100 00

011 000 00
001 000 00
001 111 00

000 000 00
000 000 00
``````

will result in:

``````110
110
000
``````

My question is there a way to do this efficiently? all I can think of is a 4 nested loop 2 loops to iterate over the big cells and 2 loops to iterate inside the cell - but I fill like I'm doing it wrong.

• You only need to iterate over (range of) the smaller data structure in order to populate it: assuming the bits in the larger data structure corresponding to each smaller segment are contiguous, you can test them all in one operation. Commented Nov 2, 2016 at 16:55
• How "efficient" does it need to be? SIMD/SWAR bit twiddling can be used but the code could be 10 times longer. Commented Nov 2, 2016 at 17:59

I think this can be achieved with a single loop (or two if you count the init loop as well).

``````init targetmatrix to zero

foreach bit in source
let tpos = final-cell-position in target
targetmatrix[tpos] |= bit
``````

So you only did one look at each element.

Real-world efficiency is of course dependent on how you store the values etc., which might make some operations quite cheap or expensive. Note that determining the "final cell position" can be obtained in different ways; of division and modulo operation come into mind, but cheap counting and resetting mit be used as well.

• I think that having nested for-loops could be more efficient, as you could short-circuit the calculation of an outer cell as soon as you found a single `1` in the content. Commented Nov 2, 2016 at 13:17
• Indeed one could go the other way round, and there may be many optimisations available. It really depends a lot on the underlying data - how large, how stored, and of course how the data is populated (spare, i.e. few 1s ore many?).
– Eiko
Commented Nov 2, 2016 at 13:47