Attraversa una matrice usando un indice lineare per ottenere un campione con valori distribuiti uniformemente

Question

Attraversa una matrice usando un indice lineare per ottenere un campione con valori distribuiti uniformemente

#1 da (1 voti)
#2 da (0 voti)

0

Sto cercando un'idea di algoritmo su come attraversare una matrice usando un indice lineare evitando gli attraversamenti basati su righe / colonne per ottenere una distribuzione dei valori più diversificata.

Per capire meglio, pensa a un'immagine divisa in blocchi, con N righe & M colonne. Ho bisogno di elaborare ogni blocco immagine in modo sequenziale (da 1 a NxM ), ma non so in anticipo quale sarà il tempo di elaborazione per ogni blocco (i blocchi ravvicinati tendono ad avere un tempo di elaborazione simile, con piccole variazioni).

Durante l'elaborazione, devo essere in grado di stimare al meglio il tempo di elaborazione rimanente in base al numero di blocchi che sono già stati elaborati e amp; il loro tempo di elaborazione associato. Per questo motivo, attraversare i blocchi per colonne o per righe non darà una stima accurata, quindi ho bisogno di trovare un altro modo di attraversare la matrice che selezionerebbe i valori da diverse zone dell'immagine.

È anche importante poter determinare l'ordine di elaborazione dei blocchi basato su un indice lineare (da 1 a NxM), senza calcolarli in anticipo. L'algoritmo che restituisce row & column corrispondente all'indice lineare dovrebbe essere il più veloce possibile.

Versione più breve della domanda

Per un indice di linea chiamato idx , ho bisogno di ottenere un row corrispondente e amp; column coppia da una matrice con N righe & M colonne evitando una traversata basata su riga / colonna.

Per ogni idx tra 1 e NxM , l'algoritmo restituisce una coppia [row, column] in modo che tutte le righe e amp; le combinazioni di colonne vengono restituite esattamente una volta.

Esempio

(i valori nella matrice rappresentano il valore dell'indice lineare associato a quella riga e alla posizione della colonna)

 1 17 13  9  5
 6  2 18 14 10
11  7  3 19 15
16 12  8  4 20

L'esempio sopra è per un attraversamento diagonale che produrrebbe una migliore distribuzione dei valori su una traversata basata su riga / colonna.

Un'altra possibile soluzione sarebbe quella di dividere la matrice in blocchi più piccoli e amp; attraversare quei blocchi in righe / colonne. Ad esempio una matrice 4x5 potrebbe essere virtualmente suddivisa in blocchi 2x2 e quei blocchi più piccoli potrebbero essere attraversati da righe o colonne (ad esempio idx(1) = block1[1, 1] , idx(2) = block2[1, 1] , ecc.). L'attraversamento sarebbe simile a questo:

 1 13 |  3 15 |  5
 7 17 |  9 18 | 11
------+-------+---
 2 14 |  4 16 |  6
 8 19 | 10 20 | 12

Qualsiasi altra idea di attraversamento è benvenuta.

Idealmente, questo algoritmo si tradurrebbe in una formula matematica per calcolare la riga & colonna basata sull'indice lineare, possibilmente con alcune condizioni (dichiarazioni IF ) per compensare i valori mancanti, ecc.

language-agnostic algorithms

posta dcro 11.07.2014 - 16:52

fonte

2 risposte

Leggi altre domande sui tag language-agnostic algorithms

Organizzazione di entità aziendali e di presentazione Struttura dati di gioco 2D in OpenGL ES 2.0

score 1 · Answer 1

Metti tutti gli interi da 0 a NxM-1 in un array, mischia l'array in modo casuale e scegli i risultati uno dopo l'altro (il mapping su riga / colonna potrebbe essere qualcosa di banale come row=idx mod M , col=idx/M ).

Un buon algoritmo shuffle è il rimescolamento di Fisher-Yates, vedi qui .

score 0 · Answer 2

Hai indicato che non vuoi fare un attraversamento riga / colonna, ma quello potrebbe essere un metodo utile. Calcola un valore di modifica dell'indice per l'array in modo che ogni nuovo indice si traduca in una posizione riga / colonna che campiona un'area diversa della matrice. L'unico requisito è che il valore di modifica dell'indice deve essere coprimo con la lunghezza dell'array. Ciò garantisce che ciascuna posizione della matrice venga scelta una volta senza calcolarla in anticipo. Il primo indice è 0 che è 0,0, ma potrebbe essere calcolato da m / 2, n / 2 per centrarlo.

// matrix dimensions are
// image height and width
var m = 600;
var n = 800;
// length of image array (number of matrix elements)
var l = m * n;
// potential coprime value
// for this expression
// number of rows is smaller of m and n
// while number of columns is larger of m and n
var p = floor( ( floor( min( m, n ) * 0.4) + 0.6) * max( m, n ) );
// greatest common denominator
// Euclidian algorithm
var gcd = function( a, b ){
    if( b === 0 ){
        return a;
    }
    return gcd( b, a % b );
}
// find coprime equal to or greater
while( p > 1 && gcd( l, p ) > 1 ){
    // increase coprime by 1
    p ++;
}
// starting index
var s = 0;
// center index
// center row plus center column
s = floor(m/2)*n + floor(n/2);
// loop through number of index positions
for( var j = 0; j < l; j ++ ){
    // index is start plus j times coprime mod array length
    var i = ( s + j * p ) % l;
    // row is index divided by number of columns rounded down
    var r = floor( i / n );
    // column is index mod number of columns
    var c = i % n;
}