Datenstruktur gesucht

[Gast2]

Hi,
ich habe ein kleines Problem und hoffe ihr könnt mir da ein wenig helfen.

Folgende Situation:
Ich habe ein 2D-Feld bei dem jedes Feld 2 Zustände (tod oder lebendig) annehmen kann. Ich habe es daher zuerst mit einem 2d-boolean Array versucht. Damit bekomme ich auch eigentlich alle Berechnungen hin wenn es um einen kleinen Maßstab geht.
Der Programmablauf sieht in etwa so aus: Für jede Zelle des Arrays wird überprüft wieviele Nachbarn dieser Zelle leben. Je nachdem wieviele das sind ändert sich dann der Zustand dieser Zelle oder er bleibt gleich.
(Dazu sei gesagt, dass am Anfang vllt 50% der Zellen lebendig sind, das nimmt im Laufe der Zeit aber stetig ab).
Wie gesagt, im kleinen Maßstab ist das überhaupt kein Problem. Nehme ich dann aber z.b. eine Feldgröße von 1.000.000 * 1.000.000 komme ich damit nichtmehr klar 😉 Ich habe schon Implementierungen gesehen in denen solche Zahlen verwendet wurden, es muss also irgendwie möglich sein. 🙂

Jetzt suche ich ne Datenstruktur um das ganze auf die oben genannte Größe zu bringen. Da habe ich mir folgendes überlegt:
1. 2d-boolean Array: bei 1m*1m komme ich schon auf mehrere GB an Datenvolumen.
2. ne Art Liste in der ich alle Koordinaten abspeichere auf der eine Zelle "lebt". Nachteil den ich darin sehe, ist dass diese Liste seeeehr oft durchlaufen werden muss für jeden Berechnungsschritt 😛

Habt ihr da irgendwelche Vorschläge wie ich sowas realisieren kann?

Gruß,
Eike

Programmcode:

    public void calculateNextGeneration() {
        boolean[][] nextGen = new boolean[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (currentGeneration[i][j]) {
                    // Lebende Zelle
                    if (getLivingNeighboursCount(i, j) < 2) {
                        nextGen[i][j] = false;
                    } else if (getLivingNeighboursCount(i, j) == 2 || getLivingNeighboursCount(i, j) == 3) {
                        nextGen[i][j] = true;
                    } else if (getLivingNeighboursCount(i, j) > 3) {
                        nextGen[i][j] = false;
                    }
                } else {
                    // Tote Zelle
                    if (getLivingNeighboursCount(i, j) == 3) {
                        nextGen[i][j] = true;
                    } else {
                        nextGen[i][j] = false;
                    }
                }
            }
        }

        // Neue Generation übernehmen
        currentGeneration = nextGen;
        generationCounter++;
    }

 

[0x7F800000]

Conways game of life... Es gibt eine Menge dicker Bücher dazu, hast du da schonmal reingeguggt?

Spontan würde ich einen Quadtree vorschlagen, bei dem sich die Knoten zusätzlich aktivieren bzw. deaktivieren lassen: wenn keine Änderungen in der nachbarschaft vorhanden sind, braucht man auch nicht dauernd alles neuzuberechnen. Der speicherverbrauch wäre dann linear zur größe der welt, bzw. des "viechs". Wie das konkret funktionieren soll, müsste ich mal ausprobieren...

Weißt du was, ich schreib's mal grad, hab mir sowas schon immer gewünscht^^ 🙂

 

[Marco13]

BitSet (Java Platform SE 6) würde schonmal sehr viel weiter helfen... Am besten als 1D-Bitset - die Umrechnung in 2D ist ja trivial.

Aber wie auch immer man es macht: Bei 1m*1m kommen (und da hilft selbst die beste Datenstruktur nichts) 125 GB zusammen. Auf einem 64bit-Rechner könnte das gehen 😉 aber so: Keine Chance (irgendwas mit ZIP-Dateien auf der Festplatte mal außen vor gelassen ; ) )

 

[0x7F800000]

Aber wie auch immer man es macht: Bei 1m*1m kommen (und da hilft selbst die beste Datenstruktur nichts) 125 GB zusammen.

Ähm, wenn man jede einzelne inaktive tote zelle abspeichern will, dann schon. Wenn man nur die lebenden speichert, ist (zumindest beim klassischen Game) eine enorme ersparnis möglich, auch wenn der zugriff nur noch in O(ln(n)) im worst case funzt. (Also: ich widerspreche schon wieder ohne lange nachforschungen^^ Erzähle ich irgendwie Unsinn oder doch nicht? 😉 )

 

[Gast2]

Genau, es handelt sich um Conways Game of Life. Da bin ich während des Mathe lernens drauf gestoßen und musste das direkt mal ausprobieren 😉

Ich werde mir Quadtree und das BitSet mal anschauen. Auch die Idee nicht immer alles komplett neu zu berechnen hört sich gut an.

Hier ist übrigens dier Version die 1miox1mio schaffen soll:
Untitled Document

 

[Painii]

Evtl. könntest du auch deine if-Abfragen verbessern...
Du rufst ja in jeder Abfrage die Methode [c]getLivingNeighboursCount(i, j)[/c] bis zu 4 mal auf. Ruf sie doch einfach am Anfang der Methode einmal auf, die ändert sich ja eh nicht bis zum nächsten Generationswechsel, den du ja grad erst berechnest.

Hilft vielleicht auch etwas gegen das Speicher-Problem.

 

[Marco13]

Hab mal ein BigBitSet gebastelt, das die Bits in einem File-MappedByteBuffer speichert, und ein BigBitSet2D, das eine 2D-Ansicht auf ein BigBitSet bietet, und ein LargeBitSet2D, das mehrere "Tiles" aus BigBitSet2D zusammenfasst, so dass man (theoretisch) "virtuell" auch ein 50-Millionen x 50-Millionen-Universum anlegen könnte. Dabei werden die eigentlichen Tiles erst erzeugt, wenn es nötig ist, und was passiert, wenn wirklich viele Tiles nötig wären, habe ich noch nicht getestet - aber es wäre zumindest ein möglicher Ansatz. Anders kriegt man 125 GB eben nicht unter....

// By Marco13 for [url]http://www.java-forum.org/java-basics-anfaenger-themen/89748-datenstruktur-gesucht.html[/url]

import java.io.*;
import java.nio.*;
import java.nio.channels.*;


public class LargeData
{
    public static void main(String[] args) throws Exception
    {

        LargeBitSet2D lbs = new LargeBitSet2D(5000000,5000000);

        System.out.println("Setting true-false-true");

        lbs.set(39999,1999999, true);
        lbs.set(40000,2000000, false);
        lbs.set(40001,2000001, true);

        System.out.println(lbs.get(39999,1999999));
        System.out.println(lbs.get(40000,2000000));
        System.out.println(lbs.get(40001,2000001));

        System.out.println("Setting false-true-false");

        lbs.set(39999,1999999, false);
        lbs.set(40000,2000000, true);
        lbs.set(40001,2000001, false);

        System.out.println(lbs.get(39999,1999999));
        System.out.println(lbs.get(40000,2000000));
        System.out.println(lbs.get(40001,2000001));


    }
}


class LargeBitSet2D
{
    // Max 130000 for 2GB files!
    private static final int tileSizeX = 40000;
    private static final int tileSizeY = 40000;

    private BigBitSet2D bbs[][];

    public LargeBitSet2D(long sizeX, long sizeY)
    {
        int numTilesX = (int)Math.ceil((double)sizeX / tileSizeX);
        int numTilesY = (int)Math.ceil((double)sizeY / tileSizeY);

        bbs = new BigBitSet2D[numTilesX][numTilesY];
    }

    public void set(long x, long y, boolean flag)
    {
        int tileX = (int)(x / tileSizeX);
        int tileY = (int)(y / tileSizeY);
        if (bbs[tileX][tileY] == null)
        {
            if (!flag)
            {
                return;
            }
            System.out.println("Creating tile "+tileX+" "+tileY+" for position "+x+" "+y);
            try
            {
                bbs[tileX][tileY] = new BigBitSet2D(tileSizeX, tileSizeY);
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }
        int localX = (int)(x % tileSizeX);
        int localY = (int)(y % tileSizeY);
        bbs[tileX][tileY].set(localX, localY, flag);
    }

    public boolean get(long x, long y)
    {
        int tileX = (int)(x / tileSizeX);
        int tileY = (int)(y / tileSizeY);
        if (bbs[tileX][tileY] == null)
        {
            return false;
        }
        int localX = (int)(x % tileSizeX);
        int localY = (int)(y % tileSizeY);
        return bbs[tileX][tileY].get(localX, localY);
    }


}



class BigBitSet
{
    private MappedByteBuffer mappedByteBuffer;

    public BigBitSet(long numBits) throws IOException
    {
        long numBytes = (long)Math.ceil((double)numBits / 8);

        System.out.println("Creating BigBitSet with "+
            numBits+" bits ("+numBytes+" bytes)");

        File file = File.createTempFile("BigBitSet", "txt");
        RandomAccessFile raf = new RandomAccessFile(file, "rw");
        mappedByteBuffer = raf.getChannel().map(
            FileChannel.MapMode.READ_WRITE, 0, numBytes);
        for(int i = 0; i < numBytes; i++)
        {
            mappedByteBuffer.put((byte)0);
        }
    }

    public void set(int index, boolean flag)
    {
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        byte b = mappedByteBuffer.get(byteIndex);
        int bit = 1 << bitIndex;
        if (flag)
        {
            b |= bit;
        }
        else
        {
            b &= ~bit;
        }
        mappedByteBuffer.put(byteIndex, b);
    }

    public boolean get(int index)
    {
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        byte b = mappedByteBuffer.get(byteIndex);
        int bit = 1 << bitIndex;
        return (b & bit) != 0;
    }
}

class BigBitSet2D
{
    private int sizeX;
    private int sizeY;

    private BigBitSet bbs;

    public BigBitSet2D(int sizeX, int sizeY) throws IOException
    {
        this.sizeX = sizeX;
        this.sizeY = sizeY;
        bbs = new BigBitSet((long)sizeX * sizeY);
    }

    public void set(int x, int y, boolean flag)
    {
        int index = y * sizeX + x;
        bbs.set(index, flag);
    }

    public boolean get(int x, int y)
    {
        int index = y * sizeX + x;
        return bbs.get(index);
    }
}

 

[Landei]

Hier ist eine fast funktionierende Implementierung. Da ist noch ein Bug in LongQuadTree: die Koordinate 7,7 wird unbegreiflicherweise nicht gesetzt. Irgendwelche Ideen? Hab' leider keine Zeit, leider will mich meine Firma (ebenfalls unbegreiflicherweise) nicht für QuadTrees bezahlen :-/

public abstract class QuadTree {

  abstract public boolean get(int x, int y);

  abstract public void flip(int x, int y);

  abstract public void set(int x, int y, boolean value);

  abstract public boolean isEmpty();

  private static class LongQuadTree extends QuadTree {
    private long data = 0L;

    public boolean get(int x, int y) {
      return (data & (1L << (x + 8 * y))) > 0;
    }

    public void flip(int x, int y) {
      data ^= (1L << (x + 8 * y));
    }

    public void set(int x, int y, boolean value) {
      if (value) {
        data |= (1L << (x + 8 * y));
      } else {
        data &= ~(data & (1L << (x + 8 * y)));
      }
    }

    public boolean isEmpty() {
      return data == 0;
    }
  }

  private static class BigQuadTree extends QuadTree {
    private final int factor;
    private final int split;
    private QuadTree[] trees;
    
    private BigQuadTree(int factor) {
      this.factor = factor;
      this.split = 1 << (factor - 1);
    }
    
    public boolean get(int x, int y) {
      if (trees == null) {
        return false;
      } else {
        QuadTree tree = trees[(x < split ? 0 : 1) + (y < split ? 0 : 2)];        
        return tree == null ? false : tree.get(x % split, y % split);
      }
    }

    public void flip(int x, int y) {
      if (trees == null) {
        trees = new QuadTree[4];
      }
      int k = (x < split ? 0 : 1) + (y < split ? 0 : 2);
      QuadTree tree = trees[k];        
      if (tree == null) {
        tree = create(factor-1);
        trees[k] = tree;
      }  
      tree.flip(x % split, y % split);
      if (tree.isEmpty()) {
        trees[k] = null;
        if (trees[0] == null && trees[1] == null && trees[2] == null && trees[3] == null) {
          trees = null;
        }
      }
    }

    public void set(int x, int y, boolean value) {
      if (trees == null) {
        trees = new QuadTree[4];
      }
      int k = (x < split ? 0 : 1) + (y < split ? 0 : 2);
      QuadTree tree = trees[k];        
      if (tree == null) {
        tree = create(factor-1);
        trees[k] = tree;
      }  
      tree.set(x % split, y % split, value);
      if (! value && tree.isEmpty()) {
        trees[k] = null;
        if (trees[0] == null && trees[1] == null && trees[2] == null && trees[3] == null) {
          trees = null;
        }
      }
    }

    public boolean isEmpty() {
      return trees == null;
    }
  }  

  public static QuadTree create(int factor) {
    if (factor < 3) {
      throw new IllegalArgumentException("Factor must be at least 3");
    } else if (factor == 3) {
      return new LongQuadTree();
    } else {
      return new BigQuadTree(factor);
    }
  }
}

 

[ice-breaker]

ich würde da eher zu einem kd Tree greifen, da der Speicherplatz bei dir stetig abnehmen würden und der Baum für Bereichsabfragen sehr gut geeignet ist.

 

[Gast2]

Ich danke euch beiden, werde beide Implementierungen heute abend mal ausprobieren.

 

[Marco13]

Hab' bei meinem mal getestet, ob man damit wirklich so ein großes Universum repräsentieren könnte - das geht so unmittelbar erstmal nicht.. 🙁 Hab noch versucht den MappedByteBuffer nur in einer SoftReference zu halten, aber da haut's ihn immernoch mit einem OutOfMemoryError raus - sollte eigentlich nicht sein ... :autsch: hab' aber gerade keine Zeit, daran weiterzumachen...

 

[Landei]

Dir ist schon klar, dass auf dem Riesenfeld normalerweise nur ein paar Pixel rumwuseln?

 

[Marco13]

Es gibt kein "normal" :bae:
In der Beschreibung des Programmes steht, dass dort beliebige Sachen (z.B. auch Bitmaps) eingelesen werden können. Selbst wenn es "meistens" weniger als 2GB "echte" Daten sind, muss der Fall, dass es DOCH mehr als 2GB sind, abgedeckt sein - und egal ob mit einem Quadtree oder einem numTilesX*numTilesY-Tree: Ohne irgendeine Form von File-Mapping wird das nicht hinhauen....

 

[Landei]

Aber wenn ich das richtig sehe, belegst du auch für leere Bereiche Speicher, oder täusche ich mich da?

 

[Marco13]

Erstmal nicht direkt - es wird ein numTilesX*numTilesY-Array erstellt, und nur wirklich ein Tile reingelegt, wenn dort ein Bit auf 'true' gesetzt wird - ähnlich wie bei deinem QuadTree. Theoretisch könnte man sich ja noch 1000 Sachen überlegen (mitzählen, wie viele bits gesetzt sind, und bei 0 gesetzen bits das Tile wieder löschen und so).

Wenn man davon ausgehen könnte, dass IMMER nur "wenige" Bits gesetzt sind, könnte man ihn ähnlichen Anwendungsszenarien auch in Erwägung ziehen (!) dem einfach eine HashSet<Coordinates> zugrunde zu legen, um zu speichern, an welchen Koordinaten ein bit gesetzt ist.... Aber wie gesagt: Bei 40 Milliarden ("zufällig") gesetzten Bits passt's einfach nicht mehr in dem RAM....