Algoritmo per ridimensionare efficacemente l'array booleano 2d

Naviga le tue risposte
0

Ho un array booleano 2D per esempio: 

01000000
01110000
00110000
01100000
00100000
00111100
00000000
00000000

Quello che voglio è creare in modo efficiente una rappresentazione in scala per questo array in base ad alcune dimensioni, ad esempio, se la dimensione è 4x4, l'array sopra verrà paratricolato ad alcune parti 4x4: 

0100 0000
0111 0000
0011 0000
0110 0000

0010 0000
0011 1100
0000 0000
0000 0000

e in ogni parte, se c'è almeno 1 valore vero l'intera parte diventa "vera" quindi il risultato della partizione 4x4 sarà: 

10
11

un altro esempio, partizione 3x3: 

010 000 00
011 100 00
001 100 00

011 000 00
001 000 00
001 111 00

000 000 00
000 000 00

risulterà in: 

110
110
000

La mia domanda c'è un modo per farlo in modo efficiente? tutto quello che riesco a pensare è un ciclo a 4 loop nidificati 2 per scorrere le celle grandi e 2 cicli per scorrere all'interno della cella - ma riempio come se fossi sbagliato.

    
posta yossico 02.11.2016 - 12:07
fonte

1 risposta

1

Penso che questo può essere ottenuto con un singolo loop (o due se si conta anche il ciclo init). 

init targetmatrix to zero

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

Quindi hai solo dato un'occhiata a ciascun elemento.

L'efficienza del mondo reale dipende ovviamente da come vengono memorizzati i valori, ecc., il che potrebbe rendere alcune operazioni piuttosto economiche o costose. Si noti che la determinazione della "posizione finale della cella" può essere ottenuta in diversi modi; delle operazioni di divisione e modulo vengono in mente, ma anche il conteggio e il ripristino a basso costo possono essere utilizzati.

    
risposta data 02.11.2016 - 12:51
fonte

Leggi altre domande sui tag

Ridimensionamento senza code? Console di Windows App vs servizio, Parte II