Zufalls-Punkte Effizienz-Problem

Dobi

Falls x, y und z ziemlich begrenzt sind und die Chancen in eine nicht so riesige Anzahl von ganzen Zahlen aufgeteilt werden kann, könntest du jede Position zwischen 0 und "MAX_CHANCE_INT" mal in einen Vektor speichern, dann eine Zufallszahl zwischen 0 und .size() generieren und dir damit deinen Punkt aus dem Vektor holen.

Oh, noch ne Idee.
Wenn du MAX_CHANCE fließkommamäßig lassen willst, könntest du jeder erlaubten x-y-z-Kombination einen Bereich, der entsprechen der Wahrscheinlichkeit für den Punkt groß ist, in den Fließkommazahlen von 0 bis irgendwas zuweisen, die dann eine von 0 bis irgendwas erzeugen lassen und gucken, welchen deiner Kandidaten sie trifft.

Geht natürlich beides nur für recht kleine Mengen. SeppJs Ansatz ist natürlich skalierbarer, allgemeingültiger und eleganter.

volkard

Welche Wertemengen haben für die Koordinaten?

otze

rob_s schrieb:

Moin!

Ich hatte ursprünglich versucht alle Positionen incl. Chance in eine Liste zu speichern

Ich hoffe, es war keine Liste. Das wäre ziemlich doof.

Mein Ansatz wäre: wie du es gemacht hast, einen Vektor erzeugen. Allerdings mit der akkumulierten Wahrscheinlichkeit. Der erste Wert im Vector hat also irgendeine echt kleine zahl, der letzte ist 1. Und dann eine Binäre suche machen:

std::vector<double> accList; //accList[i]= p[0]+p[1]+...+p[i]
std::vector<Vector> coords; //coords[i] liefert die Position für das element i
//initialisiere lustig deine Liste...)

//algorithmus:
Vector draw(){
    double p = uniform();
    std::size_t minElem = 0;
    std::size_t maxElem = coords.size();
    while(minElem != maxElem){
        std::size_t pos = (maxElem-minElem)/2;
        if(p > accList[i]){
            minElem = pos;
        }
        else
        {
            maxElem = pos;
        }
    }
    //hier gilt miNElem=maxElem = das gesuchte Element
    return coords[minElem];
}

ich bin mir gerade nicht 100% mit den indizes sicher, vielleicht muss man noch etwas daran rumdrehen, dass ja jedes Element ein Wahrscheinlichkeitsintervall darstellt...aber vom Prinzip her sollte da sklappen. Noch fixer wäre es, wenn du nen richtigen baum konstruierst, der die Wahrscheinlichkeiten auch in der Suchstruktur widerspiegelt. Meine Konstruktion sucht nach nem Knoten mit p=0.5 genauso lange wie bei einem p=0.00001 Knoten.

rob_s

Danke schonmal für die vielen Antworten.

Die Monte-Carlo Sache gefällt mir. Gutes Beispiel für Irgendwann mal gelesen ums im richtigen Moment vergessen zu haben.

Leider langsamer. Kann vielleicht an der falschen Umsetzung liegen...

void Galaxy::AddStars3 (UINT nStars, perlin::Noise3D* pNoise)
{
	lblArray3<float> aPositions (m_fWidthX, m_fWidthY, m_fWidthZ);
	for (UINT nCreated = 0; nCreated < nStars; )
	{
		UINT nRandRainX = Rand<UINT> (0, (UINT)m_fWidthX),
		     nRandRainY = Rand<UINT> (0, (UINT)m_fWidthY),
		     nRandRainZ = Rand<UINT> (0, (UINT)m_fWidthZ);

		float* pfData = aPositions(nRandRainX, nRandRainY, nRandRainZ);
		if (*pfData < 0.0f) // Position bereits verwendet.
			continue;

		*pfData += pNoise->Get (nRandRainX, nRandRainY, nRandRainZ);
		if (*pfData >= 1.0f) /* vielleicht auch höher als 1.0. Ausprobieren...*/
		{
			D3DXVECTOR3 vStarPos ((float)nRandRainX,
								  (float)nRandRainY,
								  (float)nRandRainZ);

			m_pStarTree->insert (new star (vStarPos));

			*pfData = -1.0f; // als 'verwendet' markieren
		}
	}

(Die Noise-Funktion liefert Werte zwischen 0 und 1)

Ihr anderen habt auch gute Ideen aber die hab ich jetzt noch nicht ausprobiert weil: Wenn schon Monte-Carlo (der ohne Listen aufbauen) auskommt langsamer ist, hab ich kaum Hoffnung daß das irgendwie weiterhilft...

Dobi

Wenn eine Liste (hier dann wohl implementiert als vector) nur einmal beim Programmstart aufgebaut werden muss, und dann aber nur noch über den Indexoperator drauf zugegriffen werden muss, kann das durchaus schneller sein als die Variante mit den vielen Fehlversuchen bis zum ersten gültigen.

rob_s

Eine Liste würde nur fürs Erzeugen gebraucht. Danach nicht mehr.
Ich glaub ich lass es einfach. Der Zeitaufwand ist besser als erträglich. Erebnis sieht auch gut aus...

Dobi

Verrätst du trotzdem noch, was fürn Wertebereich deine Punkte haben sollen?

rob_s

-50.0f bis +50.0f pro Dimension

im Moment zumindest.

Dobi

Wie hast du es dann eigentlich gemacht, dass jede Position ihre eigene Wahrscheinlichkeit hat wenn nicht mit Listen oder einer mathematischen Funktion?

otze

rob_s schrieb:

Das ist bisher das schnellste was ich hinbekommen hab.
Obwohl es im Raum eine menge Null-Chancen-Positionen gibt. Die Menge der Fehlversuche ist ziemlich enorm.

Wenn sogar MC langsamer ist: was ist für dich "enorm"? Enorm beginnt für mich bei >10^5 Fehlversuchen pro Treffer.