Suche nach Änderungen zwischen 2 großen Arrays

Question

Der Einfachheit halber habe ich einen sehr großen 2D-Raum einem einfachen Bit-Array zugeordnet (in Wirklichkeit sind es etwa 200.000 Elemente).

Nehmen wir nun an, dass ich einen kleinen Algorithmus verwende, der einen "Kreis" von 1 s mit einem Mittelpunkt und einem Radius zeichnet.

Hier ist ein Beispiel, in dem auf der linken Seite ein Kreis gezogen wird, und auf der nächsten Berechnung, es ist Zentrum von 1. bis bewegt

0000000  0001000 
0001000  0011100 
0011100 -> 0011100 
0011100  0001000 
0001000  0000000 
0000000  0000000 

Jetzt habe ich viele Schichten dieser Karten, und nachdem ich berechnen Ich muss sie "flattern" (so ähnlich wie Photoshop-Füllmethoden) - und ich wiederhole jedes Mal das gesamte Array und kombiniere die gesamten Arrays - obwohl sich 95% davon nicht wirklich ändern.

Psuedo Code

for(int x = 0; x < width; x++) 
    for(int y = 0; y < height; y++) 
     int index = x + y * width 
     result[index] = layer1[index] * layer2[index] 

Dies ist sehr ineffizient, und ich brauche, um meine Leistung zu verbessern.

UPDATE: Was wir am Ende

Sparse-Matrizen waren genau tun, was wir brauchten, und wir am Ende mit dem Wörterbuch der Tasten (DOK), die unsere Anwendung am besten geeignet (dynamisch jedes Gebäude Ebene und "Mischen" sie zusammen).

Die Lösung uns mit aufkommen betrug 3 Arrays zu verwenden:

1. float-Array als die maximale Anzahl von Mitgliedern bemessen wir könnten (Wert)
2. Bitfeld (gleiche Größe), Markierung, das Mitglied haben im value - Array ist gültig
3. int - Array (gleiche Größe), Speichern der Indizes im Value - Array (um es später zu iterieren) + eine inkrementelle int, die als eine Art Zeiger auf die Anzahl der Mitglieder in der verwendet wird Indexfeld

Da unsere Anforderungen stark von der Speicherauslastung und der CPU abhängen, haben wir jede dünn besetzte Matrix in eine doppelte Pufferform gebracht, um bei jeder Mischung keine neuen Arrays zu generieren.

Schließlich gab uns diese Lösung um ein x15-x20 besseres Ergebnis CPU-weise (als unsere vorherige naive Brute-Force-Ansatz), und speichermäßig haben wir die RAM-Auslastung um 98% gesenkt.

Answer 1

Von dem, was ich verstehe, und mit Hilfe der photoshop Schicht Analogie:

Sie haben Ihr unterschwelliges „Bild“, als „dicht“ 2D-Array gespeichert ist, und natürlich, da das Ihre Daten, jedes „Pixel“ ist wichtig. So weit, ist es gut.

Die zusätzlichen Schichten repräsentieren kleine Änderungen: Wenn sie als 2D-Array dargestellt, fast alle seiner Einträge werden Nullen sein.

In diesem Fall mögen Sie in Sparse Matrix Darstellungen aussehen: Statt einen vollständigen 2D-Array zu speichern, speichern Sie nur eine Liste von Tupeln [(i1,j1), (i1, j2), ..., ], die die Koordinaten der Nicht-Null-Zellen aufzeichnet.

Auf diese Weise läuft jeder Algorithmus, der auf diesen Matrizen arbeitet, in der Reihenfolge, wie viele Nicht-Nullen es gibt, anstatt basierend darauf, wie viele Einträge die Matrix insgesamt hat.