@Sirius3: Mit welchen Grössen sind denn diese Zeiten entstanden?
Wenn ich das richtig sehe stellst Du nicht sicher das alle Walker alleine auf einer Koordinate stehen‽ Je dichter man das Koordinatensystem besetzt um so weiter dürfte die Startsituation der beiden Implementierungen abweichen. Und ist ein Schritt eines Waklers bei Dir auch nur in einer Dimension?
Identische Spalten in numpy array suchen
@Blackjack: Du hast Recht. Die Startbedingungen waren nicht optimal. Ich hab's korrigiert.
Die möglichen Schritt-Richtungen sind in der Instanzvariable _steps gespeichert, ±1 in jede Richtung,
und werden in random_move zufällig ausgewählt. Damit braucht man pro Walker und Step nur jeweils
eine statt zwei Zufallszahlen, was die Geschwindigkeit um ~15% steigert.
Rein aus Interesse, wie sähenoch ein Geschwindigkeitsvergleich mit einer einfachen c-Version aus?
Die möglichen Schritt-Richtungen sind in der Instanzvariable _steps gespeichert, ±1 in jede Richtung,
und werden in random_move zufällig ausgewählt. Damit braucht man pro Walker und Step nur jeweils
eine statt zwei Zufallszahlen, was die Geschwindigkeit um ~15% steigert.
Rein aus Interesse, wie sähenoch ein Geschwindigkeitsvergleich mit einer einfachen c-Version aus?
-
BlackJack
@Sirius3: Ich bekomme folgende Laufzeiten heraus:
Ist mein Rechner so schnell oder Deiner so langsam? Kann ich fast nicht glauben. Ich habe hier ja fast den Eindruck dass die beiden bei mir deutlich näher beieinander sind, liegt einfach am konstanten Aufwand der hier dominiert und dadurch der Vorteil von `numpy` nicht so sichtbar wird.
Bei einer einfachen C-Version bekommt man das Problem, dass man eine Hashtable selber implementieren oder aus einer Bibliothek verwenden muss, wenn man eine äquivalente Implementierung liefern möchte.
Ausserdem müsste man sich `random.sample()` mal anschauen um das auch effizient zu implementieren.
@Tyrax: Kannst Du mal ungefähre Grössenordnungen verraten mit denen man das testen kann um Deinem Szenario nahe zu kommen.
Code: Alles auswählen
Python: 0.141s
+Numpy: 0.100sBei einer einfachen C-Version bekommt man das Problem, dass man eine Hashtable selber implementieren oder aus einer Bibliothek verwenden muss, wenn man eine äquivalente Implementierung liefern möchte.
Ausserdem müsste man sich `random.sample()` mal anschauen um das auch effizient zu implementieren.
@Tyrax: Kannst Du mal ungefähre Grössenordnungen verraten mit denen man das testen kann um Deinem Szenario nahe zu kommen.
In C++ sollte das schnell gemacht sein. Dictionaries benötigen als hash-Funktion für Indizes nur den <-Operator, welcher bei Koordinaten ja trivial zu implementieren ist. `random.sample()` kenne ich unter C++ nicht, auch nicht bei boost, wenn ich mich richtig erinnere, steht aber irgendwo bei Knuth etwas dazu.BlackJack hat geschrieben:Bei einer einfachen C-Version bekommt man das Problem, dass man eine Hashtable selber implementieren oder aus einer Bibliothek verwenden muss, wenn man eine äquivalente Implementierung liefern möchte.
Ausserdem müsste man sich `random.sample()` mal anschauen um das auch effizient zu implementieren.
Edit: je nach Datenlage könnte man random_shuffle verwenden. Und hier noch ein Stackoverflow-Thread, sogar mit dem Hinweis auf Knuth.
Das Leben ist wie ein Tennisball.
-
BlackJack
@EyDu: Das was den ``<``-Operator braucht ist keine Hashtable und damit hat das auch nichts mit einer Hashfunktion zu tun. Der Datentyp aus der STL ist als Baum implementiert.
-
BlackJack
@Sirius3: Hier ist eine Umsetzung in Vala: http://pastebin.com/1a3YfcRQ
Ist sehr nah am Python-Code. Statt des Python-`tuple` gibt es eine `Coordinate`-Klasse.
Die Laufzeit liegt interessanter Weise bei mir zwischen Python und Python+Numpy bei 0,122 Sekunden.
Edit: Nachdem ich mir die Laufzeitverteilung mal angeschaut hatte eine geänderte Implementierung in Vala: http://pastebin.com/1Cxx2vZV
Über 60% der Laufzeit war die erste Version damit beschäftigt in der `step()`-Methode `ArrayList`-Exemplare zu erstellen. Keine Ahnung warum das so langsam/aufwändig ist. Das habe ich jetzt durch eine ganz simple Klasse zum Zählen ersetzt und nun ist es deutlich schneller. Laufzeiten bei mir auf einen Blick:
Ist sehr nah am Python-Code. Statt des Python-`tuple` gibt es eine `Coordinate`-Klasse.
Die Laufzeit liegt interessanter Weise bei mir zwischen Python und Python+Numpy bei 0,122 Sekunden.
Edit: Nachdem ich mir die Laufzeitverteilung mal angeschaut hatte eine geänderte Implementierung in Vala: http://pastebin.com/1Cxx2vZV
Über 60% der Laufzeit war die erste Version damit beschäftigt in der `step()`-Methode `ArrayList`-Exemplare zu erstellen. Keine Ahnung warum das so langsam/aufwändig ist. Das habe ich jetzt durch eine ganz simple Klasse zum Zählen ersetzt und nun ist es deutlich schneller. Laufzeiten bei mir auf einen Blick:
Code: Alles auswählen
Python: 0.141s
PyPy: 0.125s
Vala #1: 0.114s
+Numpy: 0.100s
Vala #2: 0.043s@BlackJack:
Für meine Zwecke ist ein Gitter von 10^3 x 10^4 durchaus drin, sowie 100 random walker. Ich werde noch ein paar kleine Erweiterungen einbauen, z.B. dass sich die RW nur mit W-keit p auslöschen.
@alle:
Ich werde wohl etwas brauchen, um Eure Vorschläge im Detail zu verstehen und ein entsprechendes Skript nach meinen Bedürfnissen zu entwickeln. OOP ist mir leider noch nicht ins Blut übergegangen. Ist aber ziemlich cool.
Naja, ich melde mich, wenn ich zu einem vorzeigbaren Ergebnis gekommen bin.
Danke und beste Grüße, Tyrax
Für meine Zwecke ist ein Gitter von 10^3 x 10^4 durchaus drin, sowie 100 random walker. Ich werde noch ein paar kleine Erweiterungen einbauen, z.B. dass sich die RW nur mit W-keit p auslöschen.
@alle:
Ich werde wohl etwas brauchen, um Eure Vorschläge im Detail zu verstehen und ein entsprechendes Skript nach meinen Bedürfnissen zu entwickeln. OOP ist mir leider noch nicht ins Blut übergegangen. Ist aber ziemlich cool.
Naja, ich melde mich, wenn ich zu einem vorzeigbaren Ergebnis gekommen bin.
Danke und beste Grüße, Tyrax
Ja, das ist natürlich richtig. Ich weiß auch nicht mehr, was sich da genau in meinem Kopf abgespielt hat. Wenn ich das nächste Mal wieder mit Fieber mit Bett liege, dann lasse ich das Schreiben besser.BlackJack hat geschrieben:@EyDu: Das was den ``<``-Operator braucht ist keine Hashtable und damit hat das auch nichts mit einer Hashfunktion zu tun. Der Datentyp aus der STL ist als Baum implementiert.
Über den Geschwindigkeitsunterschiede würde ich keine Schätzung abgeben wollen, da könnte man sicher einiges ausprobieren. Mittels map wäre sicher die offensichtliche Lösung, das Sortieren der Walker wäre auch noch ein möglicher Ansatz. Ansonsten gibt es noch unordered_map und boost bietet auch ein Hashtable. Dann kann man sich natürlich noch prima über die Hash-Funktion streiten.
Vielleicht finde ich demnächst dazu mal ein wenig Zeit um die Implementierungen zu testen. Leider ist Zeit ja immer so ein knappes Gut...
Das Leben ist wie ein Tennisball.
-
BlackJack
@Tyrax: Könntest Du noch verraten wieviele Schritte eine Simulation bei 1.000×10.000 mit 100 Walkern läuft? Wenn ich die reine Python-Version 10.000 Schritte laufen lasse kollidieren die recht selten und ein Lauf dauert hier cirka 5 Sekunden.
Wie sieht `p` üblicherweise aus und wird für jeden Beteiligten einer Kollision gewürfelt oder nur einmal für den gesamten „crash”?
Edit: Hier mal die Zeiten für 100 Walker auf 1.000×10.000 Lattice und 10.000 Schritte:
Wie sieht `p` üblicherweise aus und wird für jeden Beteiligten einer Kollision gewürfelt oder nur einmal für den gesamten „crash”?
Edit: Hier mal die Zeiten für 100 Walker auf 1.000×10.000 Lattice und 10.000 Schritte:
Code: Alles auswählen
CPython: 4.936s
CPython+Numpy: 1.594s
Vala #2: 1.566s
PyPy: 1.244s@BlackJack:
Jede Kollision soll mit Wkeit p zur Auslöschung beider Walker führen. p = 10^(-n) mit n>2.
Die mittlere Zahl der Kollisionsversuche bis zum Ende der Simulation ist linear in 1/p. Ich denke, man kann in den meisten Fällen annehmen, dass auch die mittlere Anzahl der Simulationsschritte in etwa linear in 1/p zunimmt. Dabei vernachlässige ich, dass zwei Walker nach einer missglückten Kollision, nah beieinander sind und sich tendenziell schneller wieder treffen.
Jede Kollision soll mit Wkeit p zur Auslöschung beider Walker führen. p = 10^(-n) mit n>2.
Die mittlere Zahl der Kollisionsversuche bis zum Ende der Simulation ist linear in 1/p. Ich denke, man kann in den meisten Fällen annehmen, dass auch die mittlere Anzahl der Simulationsschritte in etwa linear in 1/p zunimmt. Dabei vernachlässige ich, dass zwei Walker nach einer missglückten Kollision, nah beieinander sind und sich tendenziell schneller wieder treffen.
Hallo,
ich muss zugeben, dass der objektorientierte Weg mir durchaus gefällt. Ein paar Fragen drängen sich mir dabei gerade auf:
- In der Version von BlackJack ist ein Koordinatensystem ein endliches Gitter, dass selbst nichts davon weiß, wie seine Ränder aussehen. In der Walker-Klasse wird dann definiert, dass die Ränder periodisch sind. Es erscheint mir naheliegend, das so zu machen, doch eigentlich sind die Randbedingungen eher eine Eigenschaft des Gitters (hier haben wir ja einen Torus). Wenn ich nun komplexere Gitter (eine Kugel mit reflektierenden Rändern, Löchern in der Gitterstruktur o.ä.) modellieren will, sollte ich dann die Eigenschaften doch lieber in die Klasse der Koordinatensystem schreiben?
- Wenn ich zum Beispiel die kompletten Pfade aller Walker mitschreiben will (z.B. um sie zu plotten), wo sollte ich das einbauen? An welcher Stelle, würde man eine Ausgabedatei erzeugen und füllen?
- die Geschichte mit den decorators (?) @properties und @classmethod ist mir noch nicht ganz klar. Weiß da jemand ein gutes OOP-Anfänger-Tutorial?
Beste Grüße, Tyrax
ich muss zugeben, dass der objektorientierte Weg mir durchaus gefällt. Ein paar Fragen drängen sich mir dabei gerade auf:
- In der Version von BlackJack ist ein Koordinatensystem ein endliches Gitter, dass selbst nichts davon weiß, wie seine Ränder aussehen. In der Walker-Klasse wird dann definiert, dass die Ränder periodisch sind. Es erscheint mir naheliegend, das so zu machen, doch eigentlich sind die Randbedingungen eher eine Eigenschaft des Gitters (hier haben wir ja einen Torus). Wenn ich nun komplexere Gitter (eine Kugel mit reflektierenden Rändern, Löchern in der Gitterstruktur o.ä.) modellieren will, sollte ich dann die Eigenschaften doch lieber in die Klasse der Koordinatensystem schreiben?
- Wenn ich zum Beispiel die kompletten Pfade aller Walker mitschreiben will (z.B. um sie zu plotten), wo sollte ich das einbauen? An welcher Stelle, würde man eine Ausgabedatei erzeugen und füllen?
- die Geschichte mit den decorators (?) @properties und @classmethod ist mir noch nicht ganz klar. Weiß da jemand ein gutes OOP-Anfänger-Tutorial?
Beste Grüße, Tyrax
-
BlackJack
@Tyrax: Wenn man unterschiedliche Gitterformen haben möchte mit den genannten verschiedenen Eigenschaften, dann sollte die Bewegung in das Koordinatensystem wandern. Als API könnte man eine Methode schreiben, welche die aktuelle Koordindate und das Delta bekommt und daraus dann die neue Koordinate berechnet.
Protokollieren der Schritte könnte man in der Hauptschleife nach jedem Schritt einbauen.
`property()` und `classmethod()` sind als Funktionen dokumentiert. Und die @-Syntax ist nur syntaktischer Zucker für:
Wobei ``callable`` ein Ausdruck sein muss, der ein aufrufbares Objekt ergibt. Im einfachsten Fall direkt eine Funktion oder Methode.
Protokollieren der Schritte könnte man in der Hauptschleife nach jedem Schritt einbauen.
`property()` und `classmethod()` sind als Funktionen dokumentiert. Und die @-Syntax ist nur syntaktischer Zucker für:
Code: Alles auswählen
@callable
def spam():
# ...
# <->
def spam():
# ...
spam = callable(spam)@BlackJack:
Hmm, ich kann noch nicht ganz folgen. Wenn die Bewegung der Walker ins Koordinatensystem wandert, dann fällt die Walker-Klasse weg, oder? Modelliere ich dann die Walker als Attribute des Koordinatensystems?
Mein intuitiver Ansatz wäre jetzt gewesen, die Walker beim Koordinatensystem anfragen zu lassen, welche der benachbarten Gitterplätze frei sind und dann eine Bewegung zu machen. Demnach müsste die Koordinatensystem-Klasse eine Methode haben, die Infos zu einzelnen Koordinaten rausrückt.
Den syntaktischen Zucker hebe ich mir jedenfalls für den Nachtisch auf, also bis das Hauptgericht fertig ist.
Hmm, ich kann noch nicht ganz folgen. Wenn die Bewegung der Walker ins Koordinatensystem wandert, dann fällt die Walker-Klasse weg, oder? Modelliere ich dann die Walker als Attribute des Koordinatensystems?
Mein intuitiver Ansatz wäre jetzt gewesen, die Walker beim Koordinatensystem anfragen zu lassen, welche der benachbarten Gitterplätze frei sind und dann eine Bewegung zu machen. Demnach müsste die Koordinatensystem-Klasse eine Methode haben, die Infos zu einzelnen Koordinaten rausrückt.
Den syntaktischen Zucker hebe ich mir jedenfalls für den Nachtisch auf, also bis das Hauptgericht fertig ist.
-
BlackJack
@Tyrax: Es ist halt die Frage wo man die Bewegung/Einschränkung ansiedeln möchte. Die Walker-Klasse fällt nicht weg, denn die ID ist ja ein Attribut vom Walker. Und eine zufällige Bewegung macht ja auch der Walker. Ich würde vielleicht sogar eine `Coordinate`-Klasse einführen wie ich das bei der Vala-Implementierung machen musste, weil es dort kein `tuple` gibt, und das Koordinatensystem vom Walker dorthin als Attribut verschieben.
Bei der zufälligen Bewegung für den Walker gibt es zwei Möglichkeiten: Er sucht sich zufällig eine aus und versucht es einfach. Welche Zielkoordinate dabei heraus kommt, muss im Koordinatensystem entschieden werden. Oder der Walker fragt seine Koordinate nach legalen Nachbarkoordinaten und sucht sich dann zufällig eine davon aus. Auch hier muss im Endeffekt das Koordinatensystem die Nachbarn liefern.
Bei der zufälligen Bewegung für den Walker gibt es zwei Möglichkeiten: Er sucht sich zufällig eine aus und versucht es einfach. Welche Zielkoordinate dabei heraus kommt, muss im Koordinatensystem entschieden werden. Oder der Walker fragt seine Koordinate nach legalen Nachbarkoordinaten und sucht sich dann zufällig eine davon aus. Auch hier muss im Endeffekt das Koordinatensystem die Nachbarn liefern.