Infinite Bitmap [fermé]

Je voudrais construire un bitmap pendant l'exécution. Le bitmap doit être évolutif de tous les côtés et l'accès aux pixels doit être efficace et silencieux.

Quelques illustrations http://img546.imageshack.us/img546/4995/maptm.jpg

Entre et après les commandes affichées dans l'image, Map.setPixel () et Map.getPixel () doivent définir / renvoyer les données enregistrées dans le bitmap.

Je ne m'attends pas à une implémentation juste un concept sur la façon d'allouer de la mémoire de telle manière que le setPixel () / getPixel soit aussi rapide que possible.

Si l' extend()opération doit être raisonnablement rapide, un Quadtree pourrait être un bon ajustement; cela ne nécessiterait même pas d'opérations d'extension explicites. Certes, cela ne donnerait pas de performances optimales pour un accès aléatoire à des pixels individuels, mais votre commentaire dit que votre opération principale est l' itération sur les pixels, ce qu'un quadtree pourrait faire très rapidement, peut-être presque aussi rapidement qu'une implémentation basée sur une matrice (et plus rapide si l'itération ne se produit pas toujours de la même manière, la matrice est présentée).

Vos besoins sonnent en fait comme si vous essayiez d'implémenter un automate cellulaire comme le Game of Life. Vous voudrez peut-être jeter un œil à Hashlife , un moyen extrêmement performant d'implémenter le jeu de la vie sur une grille infinie. Notez qu'il est basé sur un Quadtree, mais fait quelques optimisations supplémentaires très intelligentes basées sur la localité des règles du jeu.

@SecStone a déclaré qu'il y avait suffisamment de temps disponible pour l'opération d'expansion, donc le moyen le plus simple et le plus efficace de stocker les pixels est d'utiliser un seul tableau plat ou un tableau à deux dimensions, car les pixels sont alors accessibles en temps constant.

Par la main

Si la mémoire n'est pas une ressource très rare, j'envisage de travailler en plus gros morceaux.
Voici un pseudo-code.

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;
    }
}

Cette implémentation est assez naïve.
D'une part, il crée des morceaux dans getPixel (fondamentalement, il serait bien de simplement retourner 0 ou plus, si aucun morceau n'a été défini pour cette position). Deuxièmement, il est basé sur l'hypothèse que vous disposez d'une implémentation suffisamment rapide et évolutive de Map. À ma connaissance, chaque langue décente en a une.

Vous devrez également jouer avec la taille du morceau. Pour les bitmaps denses, une grande taille de bloc est bonne, pour les bitmaps clairsemés, une taille de bloc plus petite est meilleure. En fait, pour les plus rares, une "taille de bloc" de 1 est la meilleure, rendant les "morceaux" eux-mêmes obsolètes et réduisant la structure des données en une carte int d'une carte int de pixels.

Sur l'étagère

Une autre solution pourrait être de regarder certaines bibliothèques graphiques. Ils sont en fait assez bons pour dessiner un tampon 2D dans un autre. Cela signifierait que vous alloueriez simplement un tampon plus grand et que l'original serait dessiné dedans aux coordonnées correspondantes.

En tant que stratégie générale: lorsque vous avez un "bloc de mémoire à croissance dynamique", il est judicieux d'en allouer un multiple, une fois qu'il est épuisé. Ceci est plutôt intense en mémoire, mais réduit considérablement les coûts d' allocation et de copie . La plupart des implémentations vectorielles allouent deux fois leur taille, lorsqu'elle est dépassée. Donc, surtout si vous optez pour la solution standard, ne prolongez pas la mémoire tampon d'un pixel uniquement, car un seul pixel a été demandé. La mémoire allouée est bon marché. Réaffecter, copier et publier coûte cher.

Quelques conseils:

• Si vous implémentez cela comme un tableau d'un type intégral (ou un tableau de tableaux de ...), vous devriez probablement agrandir le tableau de sauvegarde d'un certain nombre de bits / pixels à chaque fois pour éviter d'avoir à déplacer les bits lorsque vous les copiez. L'inconvénient est que vous utilisez plus d'espace, mais la proportion d'espace gaspillé diminue à mesure que le bitmap s'agrandit.

• Si vous utilisez une structure de données basée sur une carte, vous pouvez résoudre le problème de l'agrandissement du bitmap en déplaçant simplement les arguments de coordonnées x, y des appels getPixelet setPixel.

• Si vous utilisez une structure de données basée sur une carte, vous n'avez besoin que des entrées de carte pour les «uns». Les "zéros" peuvent être indiqués par l'absence d'entrée. Cela économise beaucoup d'espace, surtout si le bitmap est principalement composé de zéros.

• Vous n'avez pas besoin d'utiliser une carte de cartes. Vous pouvez encoder une intpaire x, y comme une seule long. Un processus analogue peut être utilisé pour mapper un tableau de tableaux sur un tableau.

Enfin, vous devez équilibrer 3 choses:

1. la performance de getPixelet setPixel,
2. la performance des extend*opérations, et
3. l'utilisation de l'espace.

Avant d'essayer autre chose de plus compliqué, et à moins que vous ne puissiez pas tout garder en mémoire, gardez les choses simples et utilisez un tableau à deux dimensions avec les informations sur l'origine de votre système de coordonnées. Pour l'étendre, utilisez la même stratégie que, par exemple, le vecteur C ++ std ::: faites une distinction entre la taille réelle de votre tableau et la capacité du tableau, et étendez la capacité en segments chaque fois que la limite est atteinte. La "capacité" doit ici être définie en termes d'intervalles (from_x, to_x), (from_y, to_y).

Cela peut nécessiter une réallocation complète de la mémoire de temps en temps, mais tant que cela ne se produit pas trop souvent, cela peut être assez rapide pour votre objectif (en fait, vous devez essayer / profiler cela).

Le moyen le plus rapide et absolu d'accéder aux pixels est un tableau bidimensionnel de pixels adressables individuellement.

Pour les extensions, commencez par une implémentation simple qui réaffecte et copie à chaque fois (puisque vous aurez quand même besoin de ce code). Si le profilage n'indique pas que vous y passez beaucoup de temps, il n'est pas nécessaire de l'affiner davantage.

Si le profilage révèle un besoin de réduire le nombre de réallocations et que vous n'êtes pas limité en mémoire, pensez à surallouer un pourcentage dans chaque direction et à stocker un décalage par rapport à l'origine. (Par exemple, si vous démarrez un nouveau bitmap à 1x1 et allouez un tableau 9x9 pour le conserver, le décalage initial xet le yserait 4.) Le compromis ici doit faire des calculs supplémentaires lors de l'accès aux pixels pour appliquer le décalage.

Si les extensions s'avèrent vraiment coûteuses, vous pouvez essayer l'une ou les deux:

• Gérez différemment les extensions verticales et horizontales. L'extension d'un tableau verticalement dans n'importe quelle direction peut être accomplie en allouant un nouveau bloc et en effectuant une seule copie de l'ensemble du tableau existant au décalage approprié dans la nouvelle mémoire. Comparez cela aux extensions horizontales, où vous devez effectuer cette opération une fois par ligne car les données existantes ne sont pas contiguës dans le nouveau bloc.

• Gardez une trace du montant et de la direction d'extension les plus fréquents. Utilisez ces informations pour sélectionner une nouvelle taille et un nouveau décalage qui réduiront la probabilité de devoir réallouer et copier pour n'importe quelle extension.

Personnellement, je doute que vous ayez besoin de l'un ou de l'autre à moins que le rapport accès pixel / extension soit faible.

• Taille constante carrelage (disons, 256x256, mais avec un nombre infini de tuiles)
• Fournir un wrapper bitmap qui permet des coordonnées de pixels négatives (pour donner l'impression qu'une image peut être développée dans les quatre directions sans avoir à recalculer / synchroniser les références aux valeurs de coordonnées existantes)
  • Cependant, la classe bitmap réelle (fonctionnant sous le wrapper) ne doit prendre en charge que les coordonnées absolues (non négatives).
• Sous l'encapsuleur, fournissez un accès au niveau de la tuile (niveau bloc) à l'aide d'E / S mappées en mémoire
• En plus de Map.setPixel()et Map.getPixel()qui modifie un seul pixel à la fois, fournissez également des méthodes qui copient et modifient un rectangle de pixels à la fois. Cela permettra à l'appelant de choisir la forme d'accès la plus efficace en fonction des informations dont il dispose.
  • Les bibliothèques commerciales fournissent également des méthodes de mise à jour: une ligne de pixels, une colonne de pixels, des mises à jour de dispersion / collecte et des opérations d'arithmétique / logique blitter en une seule étape (pour minimiser la copie des données).

(Ne votons pas contre les réponses hilarantes ...)

L'implémentation la plus flexible et peut-être la plus fiable est une liste chaînée avec des structures donnant la coordonnée x, la coordonnée y et la valeur de bit. Je construirais cela en premier et le ferais fonctionner.

Ensuite, s'il est trop lent et / ou trop gros, essayez les moyens habituels pour l'accélérer: tableau, matrice, bitmap, compression, mise en cache, inversion, stockage uniquement des valeurs '1', etc.

Il est plus facile de faire une implémentation correcte lente plus rapidement que de corriger une implémentation rapide en buggy. Et tout en testant votre deuxième implémentation «rapide», vous disposez d'une norme de référence pour la comparer.

Et, qui sait, vous découvrirez probablement que la version lente est assez rapide. Tant que la structure entière reste en mémoire, les choses sont déjà incroyablement rapides.

Je propose l'implémentation suivante en Python:

class Map(dict): pass

Il présente les avantages suivants:

1. Obtenir / Définir l'accès via map[(1,2)]peut être envisagé O(1).
2. La nécessité d'étendre explicitement la grille disparaît.
3. Il y a peu d'espace pour les bugs.
4. Il est facilement mis à niveau en 3D, si jamais nécessaire.

Si vous avez réellement besoin d'un bitmap de n'importe quelle taille arbitraire - et je veux dire n'importe quoi de 1x1 à 1000000x1000000 et que vous en avez besoin extensible à la demande ... une façon possible est d'utiliser une base de données. Cela peut sembler contre-intuitif au premier abord, mais ce que vous avez vraiment, c'est un problème de stockage. Une base de données vous permettra d'accéder à des pixels individuels et de stocker essentiellement toute quantité de données. Je ne veux pas nécessairement dire un SQL db, btw.

Sera-t-il assez rapide pour vos besoins? Que je ne peux pas répondre, car il n'y a pas de contexte ici concernant ce que vous faites avec ce bitmap. Mais si c'est pour l'affichage à l'écran, considérez que vous n'avez généralement besoin que de retirer les lignes de numérisation supplémentaires pour les afficher lorsque l'écran défile, pas toutes les données.

Cela étant dit, je ne peux pas m'empêcher de me demander si vous allez quelque chose de mal. Devriez-vous plutôt utiliser un graphique vectoriel et suivre les entités individuelles en mémoire, puis rendre une image bitmap aussi grande que nécessaire pour l'écran?

Voici les étapes pour le faire fonctionner correctement:

1. utiliser le transfert d'une interface à une autre pour construire un arbre d'objets qui représentent ensemble le bitmap
2. chaque "extension" du bitmap allouera sa propre mémoire et lui fournira une autre interface

3. exemple de mise en œuvre serait:

   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;
   };
   

Évidemment, pour une implémentation réelle, XSize () et YSize () ne fonctionneraient pas, mais vous aurez besoin de MinX (), MaxX (), MinY (), MaxY () ou quelque chose comme ça pour garder les numéros d'index cohérents.