Code Optimierung

Dein Thema passt einfach in kein Forum? Dann probiers mal hier.
Antworten
MaXgOeKy
Beiträge: 5
Registriert: 30. Dezember 2012 09:55

Code Optimierung

Beitrag von MaXgOeKy »

Hallo Programmierer,

Ich habe ein Performanceproblem bei meinem Hobbyprojekt. Wie schon unter der Rubrik QT-Programmierung genannt entwickel ich eine SImulation. Da die Frage hier nicht so ganz bei QT-Programmierung reinpasst, stelle ich sie hier:

In der folgenden Methode wird meine Spielwelt initialisiert. Das funktioniert bei einem Spielfeld von 100 x 100 einwandfrei. Die einzelnen Lebewesen sind schön ungleichmäßig über die ganze Karte verteilt. Sobalt es an 300 x 300 geht dauert die Initialisierung bereits eine Minute. Bei 600 x 600 habe ich nach 5 Minuten abgebochen...

Was brauche ich? Ich brauche eine Mölichkeit, wie ich einen Container der STL wahlfrei Initialisieren kann, also nicht von 0 bis n sonder ich möchte zufällige Positionen im Vektor ansteuern bis alle Felder initialisiert worden. Ich habe da schon ein wenig bei der STL (std::generade) geschaut aber keine wirklich gute Variante gefunden.

Nun hoffe ich, dass Euch eine Möglichkeit einfällt.

Code: Alles auswählen

void TWorldWator::_initializeWorld()
{
	//Variablen
	TIndividual     *newIndividual = 0; //Fuer das Erstellen eines neuen Lebewesens
    std::vector<std::pair<int, int> > positions;
    TWorldSize       worldSize;
    long             randomPos = 0;
    
    //Hole Groesze der Spielwelt
	worldSize = getWorldSize();
    
    //Initialisiere Zufallszahlengenerator
    srand(time(NULL));
    
    //Initialisiere Vectoren
    for (int z = 0; z < worldSize.second; z++) //Zeilen
    {
        for (int s = 0; s < worldSize.second; s++) //Spalten
        {
            positions.push_back(std::pair<int, int>(z, s));
        }//end for
        
    }//end for Zeilen
    
    //Wiederhole bis alle Positionen vergeben
    while(positions.size() > 0)
    {
        //Generiere Zufallszahl für Position
        randomPos = rand() % positions.size();
        
        //Erstelle neues Individuum
        newIndividual = _createRandomIndividual();
        
        //Setze neues Individuum auf Spielfeld
        _setPlayingFieldValue(positions.at(randomPos).first,
                              positions.at(randomPos).second,
                              *newIndividual);
        
        //Entferne die gerade genutzten Positionen aus den Vectoren
        //Suche Iterator zum Wert
        std::vector<std::pair<int, int> >::iterator pIt = std::find(positions.begin(),
                                                                    positions.end(),
                                                                    positions.at(randomPos));
        
        //Entferne Element aus dem Vector
        positions.erase(pIt);
        
    }//end while

}//end initilizeWorld

Das eigentliche und langse Problem im Code ist dieses hier:

Code: Alles auswählen

//Entferne die gerade genutzten Positionen aus den Vectoren
        //Suche Iterator zum Wert
        std::vector<std::pair<int, int> >::iterator pIt = std::find(positions.begin(),
                                                                    positions.end(),
                                                                    positions.at(randomPos));
        
        //Entferne Element aus dem Vector
        positions.erase(pIt);
Hat jemand eine Idee zur Optimierung?

Grüße
MaX
veeman
Beiträge: 277
Registriert: 3. Oktober 2012 01:43
Kontaktdaten:

Re: Code Optimierung

Beitrag von veeman »

Das Problem bei deiner Implementierung ist, so wie ich das sehe, dass du ein List mit Objektkoordinaten hast.
Und sobald du ein Objekt positionieren möchtest musst du nach diesen Koordinate suchen, dies verbraucht ummengen an Such/Rechenleistung.

Möglichkeit 1: Du erstellst dir ein zweidimensionales Array und greifst über den X/Y-Index auf die Position zu und platzierst deine Objekte in dieser Matrix.
Möglichkeit 2: Du erstellst eine Objektliste mit den dazugehörigen Positionen und alle Objekte die nicht gebraucht werden, werden auch nicht platziert.

-> Eventuell ist auch die Kombination dieser zwei sinnvoll.
-> Versuch dein Algorithmus dahingehend umzuändern dass du in möglichst keinem Fall nach irgendwelchen Objekt suchen musst.

Mfg veeman
MaXgOeKy
Beiträge: 5
Registriert: 30. Dezember 2012 09:55

Re: Code Optimierung

Beitrag von MaXgOeKy »

Moin,

habe folgende Lösung gefunden:

Code: Alles auswählen

	//Variablen
	TIndividual     *newIndividual = 0; //Fuer das Erstellen eines neuen Lebewesens
    std::vector<std::pair<int, int> > positions;
    TWorldSize       worldSize;

    
    //Hole groesze der Spielwelt
    worldSize = getWorldSize();
    
    //Initialisiere Vectoren
    for (int z = 0; z < worldSize.second; z++) //Zeilen
    {
        for (int s = 0; s < worldSize.second; s++) //Spalten
        {
            positions.push_back(std::pair<int, int>(z, s));
        }//end for
        
    }//end for Zeilen
    
    //Bringe den Inhalt des Vectors positions durcheinander
    std::random_shuffle(positions.begin(), positions.end());
    
    //Wiederhole bis alle Positionen vergeben
    for (std::vector<std::pair<int, int> >::iterator it = positions.begin();
         it != positions.end();
         it++)
    {
        newIndividual= _createRandomIndividual();
        _setPlayingFieldValue(it->first, it->second, *newIndividual);
    }//end for
Der ganze Algorythmus ist sehr schnell. Eine Erstellung einer Größe von 600*600 ist unter einer Sekunde fertig, was vorher 7 Minuten gedauert hat. 1000 * 1000 ist ebenfalls unter einer Sekunde fertig!

Grüße
MaX
Antworten