Controlla tutte le "linee" in un array?

0

Ho una matrice 3D con booleani e ho bisogno di controllare se ci sono "linee" che contengono tutte vero o falso. Con le linee intendo orizzontalmente, verticalmente e diagonalmente all'interno della matrice. Tuttavia ho solo bisogno di controllare questo quando un elemento cambia e conosco la posizione dell'elemento modificato. L'array è sempre uguale su tutti e 3 i lati / dimensioni.

Sto cercando un modo efficace per attraversare la possibile direzione dall'elemento che è cambiato. Quello che sto facendo è in primo luogo controllare le linee rette x, yez che sono facili. Quindi controllo le 2 diagonali orizzontali:

if (element.x + element.y == arraySize || element.x == element.y)
    //Only now there can be a full diagonal line

E quello per ogni lato (x, y e z). Ora ho solo bisogno delle 4 diagonali complete per l'array. Ma mi chiedo se c'è un trucco intelligente per renderlo più efficiente.

    
posta Madmenyo 18.01.2015 - 11:49
fonte

2 risposte

2

Da un punto di vista teorico, non c'è molto che tu possa fare perché indipendentemente dal fatto che una riga contenga tutti i trues o tutti i falses non ti dice molto se le altre linee lo fanno, cioè devi "controllarle tutte" "non importa cosa.

Quello che puoi fare è assicurarti di non controllare nulla due volte. Se controlli se c'è una linea da (0,0,0) a (8,8,8), allora non dovresti controllare anche se c'è una linea da (8,8,8) a (0,0,0) più tardi nel tuo algoritmo. Ad esempio, quando controlli le linee orizzontali e verticali, esegui solo i controlli per tre dei sei lati del tuo cubo.

La struttura dei dati che utilizzi è probabilmente il fattore più importante nella pratica. Ovviamente hai bisogno di accesso casuale poiché le "linee" vanno in diverse direzioni, quindi una ArrayList sarebbe molto meglio di una LinkedList (anche se immagino che tu lo sapessi già).

Se quei suggerimenti generici non bastano, dovremmo iniziare a parlare di cose come la dimensione effettiva del tuo cubo, il codice esatto che hai provato, il modo in cui hai misurato le sue prestazioni, come tendono i trues o i falsi da distribuire, e così via.

    
risposta data 18.01.2015 - 12:10
fonte
1

Come Ixrec ha scritto in merito alle prestazioni, non c'è molto da fare, dovrai attraversare l'array molte volte. Tuttavia, posso darti uno strumento che lo rende più semplice:

public class LineEnumerator
{
    int dx, dy, dz;
    public LineEnumerator(int dx, int dy, int dz)
    {
        this.dx = dx;
        this.dy = dy;
        this.dz = dz;
    }
    public IEnumerable<bool> GetLine(bool[, ,] arr, int x0, int y0, int z0)
    {
        int xLength = arr.GetLength(0);
        int yLength = arr.GetLength(1);
        int zLength = arr.GetLength(2);

        while (x0 >= 0 && x0 < xLength &&
               y0 >= 0 && y0 < yLength &&
               z0 >= 0 && z0 < zLength)
        {
            yield return arr[x0, y0, z0];
            x0 += dx;
            y0 += dy;
            z0 += dz;
        }
    }
}

Questo è un enumeratore direzionale generale totale per un array 3D. Usando questo è facile da collegare il treversing. Ad esempio, attraversare una linea nella direzione X può essere scritto in questo modo:

var XEnumerator = new LineEnumerator(1, 0, 0);
foreach(bool b in XEnumerator.GetLine(arr, 0, 0, 0))
{
  //Do whatever
}

Oppure puoi istanziare un enumeratore diagonale come questo:

var DiagonalEnumerator1 = new LineEnumerator(1, 1, 1);

o un altro come questo:

var DiagonalEnumerator2= new LineEnumerator(1, 1, -1);
    
risposta data 18.01.2015 - 15:56
fonte

Leggi altre domande sui tag