Das deutsche Python-Forum

Hallo,

ich habe die Absicht in einem Würfel eine variable Anzahl an langen zufällig, orientierten Zylindern, durchdringungsfrei zu positionieren. Die Vorgehensweise, die ich bis jetzt verwende sieht wie folgt aus:
1. Startpunkt des Zylinders mithilfe eines Zufallsgenerators erzeugen, dabei muss der Abstand zu alle anderen Punkten gegen ein Kriterium geprüft werden.
2. Danach wird ein (bezüglich der x-Achse eines kartesichen Koordinatensystems paralleler) Vektor erzeugt, dessen Richtung durch zwei Rotationen (zufällig generierte Winkel in bestimmten Bereichen) verändert wird.
3. Durch Multiplikation dieses Einheitsvektors mit der Länge des Zylinders wird ein Geradenabschnitt erzeugt.
4. Jetzt wird dieser geradenabschnitt gegen alle vorliegenden Geraden auf Durchdringung gecheckt. Gegebenenfalls wird eine neue Gerade auf diese Weise per Zufall erzeugt.

Das funktioniert auch recht gut und ausreichend schnell bis ca 10vol% . Das Problem ist nur, dass ich den Volumenanteil der Zylinder bis knapp unter 20% haben möchte. Dann dauert die Rechnung natürlich sehr lang (14-vol% dauern auf meinem AMD xp 1800 ca. 5 Stunden), was durch die Herangehensweise bestimmt ist.

Was ich mir jetzt davon erhoffe, dass ich den Code hier online stelle:
Vielleicht kann jemand drüber schauen und mir Verbesserungsvorschläge liefern, die in erster Linie die Geschwindigkeit verbessern sollen.

Vielleicht sieht jemand noch eine weitere Lösungsmöglichkeit, um mein Vorhaben zu lösen.


Vielen Dank an alle, die sich die Mühe machen.

http://paste.pocoo.org/show/104661/

Edit: Habe den Code ausgelagert

Carsten1983 hat geschrieben: Vielleicht kann jemand drüber schauen und mir Verbesserungsvorschläge liefern, die in erster Linie die Geschwindigkeit verbessern sollen.

Mal eben "drüber schauen" ist natürlich bei solchem Code und der entsprechenden Länge nicht mal so eben getan ...

Zu deinem Problem: Eine alternative Lösungsidee ist mir zwar (noch) nicht eingefallen, aber dein Grundansatz, zufällig ohne irgendwelche Anfangseinschränkungen einen Zylinder zu erzeugen, diesen "aufzubauen" und erst zum Schluss zu prüfen, ob es überhaupt ein unter den festgesetzten Bedingungen möglicher Zylinder ist, um ihn dann ggf. zu verwerfen und wieder von vorne anzufangen, ist definitiv äußerst ineffektiv. Du könntest ja mal einen Zähler mitlaufen lassen, der dir ausgibt, wie viele Versuche vergeblich waren in Abhängigkeit von der laufenden Nummer des Zylinders - da werden mit der Zeit sehr hohe Zahlen an Fehlversuchen entstehen.

Es müsste also ein grundlegend anderer Ansatz gefunden werden.

Wie "zufällig" müssen denn die Zylinder sein?
Was ist der Hintergrund der Problemstellung?

Eine leichte Beschleunigung könnte der Einsatz von psyco bringen, aber ob es für 14 Zylinder nun 5 Stunden oder 1 Stunde sind, ist letztlich auch egal. Bis auf 20 Zylinder wirst du dann vermutlich auch in den nächsten Jahren nicht mehr kommen ...

Die Zylinder sind nicht rein zufällig. Vielmehr haben sie immer die selbe Form, ihre Positionierung im Raum erfolgt in gewissen Grenzen zufällig.
Der Startpunkt wird immer sehr weit links im Kubus positioniert (0*Kubuslänge..Faktor*Kubuslänge). Die Ausrichtung im Raum wird über zwei Winkel realisiert. Diese werden zufällig innerhalb eines Wertebereiches, der vorgegeben werden muss bestimmt.

Die Problemstellung die sich dahinter verbirgt ist in Realität die Abbildung eines Einheitsvolumens (der Kubus) in dem sich Fasern (Zylinder) mit einem bestimmten mittleren Orientierungszustand befinden. Dieses Einheitsvolumen soll später für mikromechanische Untersuchungen verwendet werden.

Die Zufälligkeit der Zylinder wird durch die verwendete Zufallsverteilungsfunktion und die Grenzen der zulässigen Rotationswinkel, die in selbige eingesetzt werden, bestimmt.

Es ist in der Tat ein Problem, dass ich immer jeden Punkt und jeden Vektor bezüglich alle anderen Punkte und Vektoren checken. Dabei kommt eine extrem ungünstige Laufzeit raus ((limit_p)²*anzahlFaser*mögl_startPunktumlagerungen*möglich_endPunktumlagerungen = ca 125²*200*75*50). Aber da sind dann ca. 120..130 Fasern drin, was vielleicht 13vol% entspricht.

Ich sehe im Moment zwei Möglichkeiten die Geschwindigkeit zu erhöhen:
1. Wie wäre es einen Wrapper für das selbe Programm in z.B. Fortran zu schreiben (oder eben gleich in Fortran zur Not).
2. Den positionierten Zylindern und Punkten einen Unterraum zuweisen. So müsste ich jeden neuen Vektor/Punkt nur gegen Punkte eines Unterraumes prüfen.

Zu.1: Ich weiß aber nicht ob mir das tatsächlich was bringt, da numpy doch eh zum großen Teil die Fortran Bibliotheken nutzt, oder?


Eine Alternative die mir noch zu dem kompletten Vorgehen einfällt wäre, die Zylinder alle in einer Richtung in dem Würfel zu positionieren. Was dann ja der höchstmöglichen Packungsdicht entspricht. Dann soviele rauslöschen bis der gewünschte Volumenanteil erreicht ist. Und dann jede Faser solang zufällig bewegen bis sich der gewünschte mittlere Orientierungszustand eingestellt hat. Das Problem an der Sache ist, das ich nicht weiß, ob es das wirklich besser macht oder ob ich überhaupt auf die gewünschten Zustände komme

Hier eine überarbeitete Fassung des Scripts:
http://paste.pocoo.org/show/105325/

Ich habe den Kubus in 4 Unterräume eingeteilt, so dass jetzt nur noch die Punkte und Zylinder eines Unteraumes gegeneinander gecheckt werden. Damit konnte ein ziemlicher Geschwindigkeitszuwachs erzielt werden. Waren (bei selben Parametern) vorher in 6 Stunden 150 Zylinder (entsprachen in dem Fall 14 vol%) möglich, sind es mit der Unterraumgeschichte 270 in einer halben Stunde (allerdings andere Parameter[dünnere zylinder, deshaln sind mehr von Nöten]).

Jetzt würde ich gern die absolute Anzahl auf ca 450..500 Stück erhöhen. Das Problem an der Geschichte ist damit natürlich wieder das Alte:
Es müssen zuviele Zylinder gegeneinander auf Durchdringung überprüft werden, bei immer geringerer Wahrscheinlichkeit einen passenden Zwischenraum zur Positionierung zu finden.

Hat jemand Vorschläge zur weiteren Geschwindigkeitssteigerung? Hat vielleicht jemand irgendwelche Hinweise bezüglich der Datentypen, dass es vielleicht an mancher Stelle sinnvoller wäre etwas anders zu machen oder dergleichen?

Edit: Könnte man so ein Problem vom Aufbau her anders gestalten, so dass auf einem Quadcore mehrere CPUs genutzt würden. Ich weiß, dass das theoretisch geht, aber wäre das auch bei diesem Prooblem möglich/sinnvoll?