Unendliche Bitmap [geschlossen]

Ich möchte zur Laufzeit eine Bitmap erstellen. Die Bitmap sollte allseitig skalierbar sein und der Pixelzugriff sollte sehr effizient sein.

Einige Abbildungen http://img546.imageshack.us/img546/4995/maptm.jpg

Zwischen und nach den im Bild gezeigten Befehlen sollten Map.setPixel () und Map.getPixel () in der Bitmap gespeicherte Daten setzen / zurückgeben.

Ich erwarte von einer Implementierung nicht nur ein Konzept, wie Speicher so zugewiesen werden kann, dass setPixel () / getPixel so schnell wie möglich ist.

Wenn die extend()Operation relativ schnell sein muss, ist ein Quadtree möglicherweise eine gute Lösung . Es würde nicht einmal explizite Erweiterungsoperationen erfordern. Zugegeben, es würde keine optimale Leistung für den wahlfreien Zugriff auf einzelne Pixel ergeben, aber Ihr Kommentar besagt, dass Ihre primäre Operation über die Pixel iteriert , was ein Quadtree sehr schnell tun könnte, vielleicht fast so schnell wie eine matrixbasierte Implementierung (und schneller) Wenn die Iteration nicht immer auf die gleiche Weise erfolgt, wird die Matrix angelegt.

Ihre Anforderungen klingen tatsächlich so, als würden Sie versuchen, einen Mobilfunkautomaten wie das Game of Life zu implementieren. Vielleicht möchten Sie einen Blick auf Hashlife werfen , eine äußerst leistungsstarke Methode, um das Spiel des Lebens in einem unendlichen Raster zu implementieren. Beachten Sie, dass es auf einem Quadtree basiert, aber einige sehr clevere zusätzliche Optimierungen basierend auf der Lokalität der Spielregeln vornimmt.

@SecStone sagte, dass genügend Zeit für den Erweiterungsvorgang zur Verfügung steht. Die einfachste und effizienteste Art, die Pixel zu speichern, ist die Verwendung eines einzelnen flachen Arrays oder eines zweidimensionalen Arrays, da auf Pixel dann in konstanter Zeit zugegriffen werden kann.

Von Hand

Wenn Speicher keine sehr spärliche Ressource ist, denke ich darüber nach, in größeren Blöcken zu arbeiten.
Hier ist ein Pseudocode.

class Chunk {
    Chunk new(int size) {...}
    void setPixel(int x, int y, int value) {...}
    int getPixel(int x, int y) {...}
}

class Grid {
    Map<int, Map<Chunk>> chunks;
    Grid new(int chunkSize) {...}
    void setPixel(int x, int y, int value) {
         getChunk(x,y).setPixel(x % chunkSize, y % chunkSize, value);//actually the modulo could be right in Chunk::setPixel and getPixel for more safety
    }
    int getPixel(int x, int y) { /*along the lines of setPixel*/ }
    private Chunk getChunk(int x, int y) {
         x /= chunkSize;
         y /= chunkSize;
         Map<Chunk> row = chunks.get(y);
         if (row == null) chunks.set(y, row = new Map<Chunk>());
         Chunk ret = row.get(x);
         if (ret == null) row.set(x, ret = new Chunk(chunkSize));
         return ret;
    }
}

Diese Implementierung ist ziemlich naiv.
Zum einen werden Chunks in getPixel erstellt (im Grunde wäre es in Ordnung, einfach 0 oder so zurückzugeben, wenn für diese Position keine Chunks definiert wurden). Zweitens wird davon ausgegangen, dass Sie eine ausreichend schnelle und skalierbare Implementierung von Map haben. Meines Wissens hat jede anständige Sprache eine.

Außerdem müssen Sie mit der Blockgröße spielen. Für dichte Bitmaps ist eine große Blockgröße gut, für spärliche Bitmaps ist eine kleinere Blockgröße besser. Tatsächlich ist für sehr spärliche eine "Blockgröße" von 1 die beste, wodurch die "Blockblöcke" selbst veraltet werden und die Datenstruktur auf eine int-Karte einer int-Karte von Pixeln reduziert wird.

Ab Lager

Eine andere Lösung könnte darin bestehen, sich einige Grafikbibliotheken anzusehen. Sie sind eigentlich ziemlich gut darin, einen 2D-Puffer in einen anderen zu zeichnen. Das würde bedeuten, dass Sie einfach einen größeren Puffer zuweisen und das Original an den entsprechenden Koordinaten darin zeichnen würden.

Als allgemeine Strategie: Wenn Sie einen "dynamisch wachsenden Speicherblock" haben, ist es eine gute Idee, ein Vielfaches davon zuzuweisen, sobald er aufgebraucht ist. Dies ist ziemlich speicherintensiv, senkt jedoch die Zuordnungs- und Kopierkosten erheblich . Die meisten Vektorimplementierungen weisen die doppelte Größe zu, wenn sie überschritten werden. Wenn Sie sich also für die Standardlösung entscheiden, sollten Sie Ihren Puffer nicht nur um 1 Pixel erweitern, da nur ein Pixel angefordert wurde. Der zugewiesene Speicher ist billig. Das Neuzuweisen, Kopieren und Freigeben ist teuer.

Nur ein paar Ratschläge:

• Wenn Sie dies als Array eines integralen Typs (oder als Array von Arrays von ...) implementieren, sollten Sie das Hintergrundarray wahrscheinlich jedes Mal um eine bestimmte Anzahl von Bits / Pixeln vergrößern, um zu vermeiden, dass Sie die Bits beim Kopieren verschieben müssen. Der Nachteil ist, dass Sie mehr Speicherplatz verwenden, der Anteil des verschwendeten Speicherplatzes jedoch abnimmt, wenn die Bitmap größer wird.

• Wenn Sie eine Map-basierte Datenstruktur verwenden, können Sie das Problem der Erweiterung der Bitmap verfeinern, indem Sie einfach die x-, y-Koordinatenargumente von getPixelund setPixelaufrufen.

• Wenn Sie eine kartenbasierte Datenstruktur verwenden, benötigen Sie nur Karteneinträge für die "Einsen". Die "Nullen" können durch das Fehlen eines Eintrags angezeigt werden. Dies spart viel Platz, insbesondere wenn die Bitmap hauptsächlich aus Nullen besteht.

• Sie müssen keine Kartenkarte verwenden. Sie können ein intx, y-Paar als einzelnes codieren long. Ein analoger Prozess kann verwendet werden, um ein Array von Arrays einem Array zuzuordnen.

Schließlich müssen Sie 3 Dinge ausbalancieren:

1. die Leistung von getPixelund setPixel,
2. die Leistung der extend*Operationen, und
3. die Raumnutzung.

Bevor Sie etwas komplizierteres ausprobieren und nicht alles im Speicher behalten können, halten Sie die Dinge einfach und verwenden Sie ein zweidimensionales Array zusammen mit den Informationen über den Ursprung Ihres Koordinatensystems. Verwenden Sie zum Erweitern dieselbe Strategie wie beispielsweise den C ++ - std :: -Vektor: Unterscheiden Sie zwischen der tatsächlichen Größe Ihres Arrays und der Kapazität des Arrays und erweitern Sie die Kapazität in Blöcken, wenn das Limit erreicht ist. "Kapazität" sollte hier in Intervallen (von_x, bis_x), (von_y, bis_y) definiert werden.

Dies erfordert möglicherweise von Zeit zu Zeit eine vollständige Neuzuweisung des Speichers. Solange dies jedoch nicht zu oft vorkommt, ist es möglicherweise schnell genug für Ihren Zweck (tatsächlich müssen Sie dies versuchen / profilieren).

Der absolut schnellste Weg, um auf Pixel zuzugreifen, ist ein zweidimensionales Array von individuell adressierbaren Pixeln.

Beginnen Sie bei Erweiterungen mit einer einfachen Implementierung, die jedes Mal neu zugewiesen und kopiert wird (da Sie diesen Code sowieso benötigen). Wenn die Profilerstellung nicht bedeutet, dass Sie viel Zeit damit verbringen, müssen Sie sie nicht weiter verfeinern.

Wenn bei der Profilerstellung festgestellt werden muss, dass die Anzahl der Neuzuweisungen gering gehalten werden muss und Sie nicht an Speicherbeschränkungen gebunden sind, sollten Sie eine Überzuweisung in jeder Richtung um einen Prozentsatz in Betracht ziehen und einen Versatz zum Ursprung speichern. (Wenn Sie beispielsweise eine neue Bitmap bei 1x1 starten und ein 9x9-Array zuweisen, um sie zu halten, sind die Anfangs- xund yOffsets 4.) Der Kompromiss besteht darin, dass Sie beim Pixelzugriff zusätzliche Berechnungen durchführen müssen, um den Offset anzuwenden.

Wenn sich Erweiterungen als sehr teuer herausstellen, können Sie eine oder beide der folgenden Methoden ausprobieren:

• Behandeln Sie vertikale und horizontale Verlängerungen unterschiedlich. Das vertikale Erweitern eines Arrays in eine beliebige Richtung kann erreicht werden, indem ein neuer Block zugewiesen und eine einzelne Kopie des gesamten vorhandenen Arrays dem entsprechenden Versatz im neuen Speicher zugewiesen wird. Vergleichen Sie dies mit horizontalen Erweiterungen, bei denen Sie diese Operation einmal pro Zeile ausführen müssen, da die vorhandenen Daten im neuen Block nicht zusammenhängend sind.

• Verfolgen Sie die häufigste Menge und Richtung der Ausdehnung. Verwenden Sie diese Informationen, um eine neue Größe und einen neuen Versatz auszuwählen, wodurch die Wahrscheinlichkeit verringert wird, dass für eine Erweiterung eine Neuzuweisung und ein erneutes Kopieren erforderlich sind.

Persönlich bezweifle ich, dass Sie eines davon benötigen werden, es sei denn, das Verhältnis von Pixelzugriff zu Erweiterung ist niedrig.

• Kacheln mit konstanter Größe (z. B. 256 x 256, aber mit unendlich vielen Kacheln)
• Stellen Sie einen Bitmap- Wrapper bereit , der negative Pixelkoordinaten zulässt (um den Eindruck zu erwecken, dass ein Bild in alle vier Richtungen erweitert werden kann, ohne dass Verweise auf vorhandene Koordinatenwerte neu berechnet / synchronisiert werden müssen).
  • Die eigentliche Bitmap-Klasse (die unter dem Wrapper arbeitet) sollte jedoch nur absolute (nicht negative) Koordinaten unterstützen.
• Stellen Sie unter dem Wrapper den Zugriff auf Kachelebene (Blockebene) mithilfe von speicherabgebildeten E / A bereit
• Stellen Sie zusätzlich zu Map.setPixel()und Map.getPixel(), die jeweils nur ein Pixel modifizieren, auch Methoden bereit, mit denen jeweils ein Rechteck von Pixeln kopiert und geändert wird. Auf diese Weise kann der Anrufer abhängig von den dem Anrufer verfügbaren Informationen die effizientere Form des Zugriffs auswählen.
  • Kommerzielle Bibliotheken bieten auch Methoden zum Aktualisieren: eine Pixelreihe, eine Pixelspalte, Streu- / Sammelaktualisierungen und Arithmetik- / Logik-Blitter-Operationen in einem Schritt (um das Kopieren von Daten zu minimieren).

(Lassen Sie uns die lustigen Antworten nicht positiv bewerten ...)

Die flexibelste und möglicherweise zuverlässigste Implementierung ist eine verknüpfte Liste mit Strukturen, die x-Koordinaten, y-Koordinaten und Bitwerte angeben. Ich würde das zuerst bauen und es zum Laufen bringen.

Wenn es dann zu langsam und / oder zu groß ist, versuchen Sie es mit den üblichen Methoden, um es zu beschleunigen: Array, Matrix, Bitmap, Komprimierung, Caching, Inversion, Speichern von nur '1'-Werten usw.

Es ist einfacher, eine langsame korrekte Implementierung schneller durchzuführen, als eine fehlerhafte schnelle Implementierung zu beheben. Und während Sie Ihre 'schnelle' zweite Implementierung testen, haben Sie einen Referenzstandard, mit dem Sie sie vergleichen können.

Und wer weiß, Sie werden wahrscheinlich feststellen, dass die langsame Version schnell genug ist. Solange die gesamte Struktur in Erinnerung bleibt, geht es schon erstaunlich schnell.

Ich schlage folgende Implementierung in Python vor:

class Map(dict): pass

Es hat folgende Vorteile:

1. Get / Set-Zugriff über map[(1,2)]kann berücksichtigt werden O(1).
2. Die Notwendigkeit, das Raster explizit zu erweitern, verschwindet.
3. Es gibt wenig Platz für Fehler.
4. Es kann bei Bedarf problemlos auf 3D aktualisiert werden.

Wenn Sie tatsächlich eine Bitmap beliebiger Größe benötigen - und ich meine alles von 1x1 bis 1000000x1000000 amd up und sie bei Bedarf erweiterbar benötigen ... besteht eine Möglichkeit darin, eine Datenbank zu verwenden. Es mag zunächst kontraintuitiv erscheinen, aber was Sie wirklich haben, ist ein Speicherproblem. Über eine Datenbank können Sie auf einzelne Pixel zugreifen und im Wesentlichen jede Datenmenge speichern. Ich meine übrigens nicht unbedingt eine SQL-Datenbank.

Wird es für Ihre Zwecke schnell genug sein? Das kann ich nicht beantworten, da es hier keinen Zusammenhang gibt, was Sie mit dieser Bitmap machen. Wenn dies jedoch für die Bildschirmanzeige vorgesehen ist, müssen Sie im Allgemeinen nur die zusätzlichen Scanzeilen zurückziehen, um sie beim Scrollen des Bildschirms anzuzeigen, nicht alle Daten.

Davon abgesehen kann ich nicht anders, als mich zu fragen, ob Sie etwas falsch machen. Sollten Sie vielleicht stattdessen vektorbasierte Grafiken verwenden und einzelne Entitäten im Speicher verfolgen und dann eine Bitmap nur so groß rendern, wie es für den Bildschirm erforderlich ist?

Hier sind die Schritte, damit es richtig funktioniert:

1. Verwenden Sie die Weiterleitung von einer Schnittstelle zur anderen, um einen Baum von Objekten zu erstellen, die zusammen die Bitmap darstellen
2. Jede "Erweiterung" der Bitmap weist ihren eigenen Speicher zu und stellt eine andere Schnittstelle dafür bereit

3. Beispiel Implementierung wäre:

   template<class T, class P>
   class ExtendBottom {
   public:
      ExtendBottom(T &t, int count) : t(t), count(count),k(t.XSize(), count) { }
      P &At(int x, int y) const { if (y<t.YSize()) return t.At(x,y); else return k.At(x, y-t.YSize()); }
      int XSize() const { return t.XSize(); }
      int YSize() const { return t.YSize()+count; }
   private:
      T &t;
      int count;
      MemoryBitmap k;
   };
   

Für eine echte Implementierung würden XSize () und YSize () natürlich nicht funktionieren, aber Sie benötigen MinX (), MaxX (), MinY (), MaxY () oder ähnliches, um die Indexnummern konsistent zu halten.