Würfelsimulation
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Tatsache. :ooops: Lesen sollte man können. Hat mich nur gewundert, warum BlackJack die Zahlen nicht in das Ranking mit aufgenommen hat.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Weil ich bis eben kein Ruby auf diesem Rechner installiert hatte.
36.863 Haskell (von audax)
34.366 Python (2.5 -- `defaultdict`)
14.633 Ruby (von zero-one)
12.241 Python (2.5 -- eigene `dice_roll()` statt `randint()` von rayo)
00.820 Python (2.5 -- mit `numpy` von HerrHagen)
00.541 Scheme (Bigloo-Compiler)
00.435 Pascal (FreePascal)
00.241 C++ (von zero-one)
36.863 Haskell (von audax)
34.366 Python (2.5 -- `defaultdict`)
14.633 Ruby (von zero-one)
12.241 Python (2.5 -- eigene `dice_roll()` statt `randint()` von rayo)
00.820 Python (2.5 -- mit `numpy` von HerrHagen)
00.541 Scheme (Bigloo-Compiler)
00.435 Pascal (FreePascal)
00.241 C++ (von zero-one)
Das lag nur(!) an der lahmen Random-Funktion... >.<BlackJack hat geschrieben:@audax: Haskell ist halt doof. Laufzeitverhalten und auch Speicherverbrauch ist für normalsterbliche Programmierer IMHO nicht vernünftig abschätzbar, wegen der lazy-Auswertung, die ja im Ernstfall nicht nur bedeutet, das etwas später ausgewertet wird, sondern das eine Funktion halb ausgewertet wird und solche Konstrukte den Speicher zumüllen. Deine Variante mit `ghc` ohne Optionen übersetzt, musste ich abbrechen nachdem das Programm angefangen hat zu swappen und immer mehr Speicher wollte. Mit `-O3` ging's dann, aber eben wie bei Dir, schnarchlangsam.
Und -O2 muss eigentlich immer sein, ansonsten optimiert er die Struktur nicht genug.
Das hier geht aber auch ohne -O2:
http://paste.pocoo.org/show/99707
Die tuts nun bei mir in 2,5s.
Das was eben noch etwas lahm is, ist der Generator für die Zahlen...
Üblicherweise nutzt man übringens bei Berechnungen auch strikte Typen, wie ich das nun auch tu. Die erste Version war noch etwas sehr naiv
Code: Alles auswählen
bj@s8n:~$ ghc -O3 test.hs
test.hs:1:0:
Failed to load interface for `System.Random.Mersenne'
Meine Variante in D
http://paste.pocoo.org/show/99725/
Mhm, ich mag D. Aber das ist D mit Tango, nur damit ihr wisst... also nicht Phobos.
//Mhm, ich seh grade... man sollte es mit 1e7 laufen lassen? Naja, egal... Wer's mag, kanns auch mit 1e7 laufen lassen Ist ja nur eine Zeile im Quelltext.
//Und dasselbe nochmal mit Phobos
http://paste.pocoo.org/show/99726/
Phobos is wohl'n bissel flotter weils die C-Funktion für Random verwendet, die könnte man auch in die Tangoversion einbauen... ich fand aber Kiss so schön. Mhm... egal wie mans dreht und wendet, bei mir wirds wohl zwischen 1.1~1.7 sein.
http://paste.pocoo.org/show/99725/
Code: Alles auswählen
C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dice.d
0.16 seconds
{1 => 165916, 2 => 166601, 3 => 166869, 4 => 166973, 5 => 166561, 6 => 167080}
//Mhm, ich seh grade... man sollte es mit 1e7 laufen lassen? Naja, egal... Wer's mag, kanns auch mit 1e7 laufen lassen Ist ja nur eine Zeile im Quelltext.
Code: Alles auswählen
C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dice.d
1.66 seconds
{1 => 1664310, 2 => 1667156, 3 => 1667379, 4 => 1669515, 5 => 1666800, 6 => 1664840}
http://paste.pocoo.org/show/99726/
Code: Alles auswählen
C:\Dokumente und Einstellungen\~\Desktop>dmd -O -run dicephobos.d
1.094
[1:1664470,2:1669052,3:1666193,4:1667854,5:1665509,6:1666922]
BlackJack hat geschrieben:Ich weiss nicht ob ich Lust habe mich jetzt mit dem Cabal-Kram herum zu schlagen.Code: Alles auswählen
bj@s8n:~$ ghc -O3 test.hs test.hs:1:0: Failed to load interface for `System.Random.Mersenne'
Code: Alles auswählen
cabal install mersenne-random
Übrigens int numpy böse. Die Zeit die es braucht macht ja Angst!
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
audax hat geschrieben:Übrigens int numpy böse. Die Zeit die es braucht macht ja Angst!
Davon abgesehen: kann man eigentlich Bigloo ein Shared-Object kompilieren lassen? Ich hatte die Idee, Python-Code durch OCaml-Code zu beschleunigen, aber OCaml kann keine Objekte erstellen die ich irgendwie via ctypes ansprechen könnte.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
@BlackVivi: Hab kein Tango installiert. In der C-Standardbibliothek gibt es kein `randomize()` und die POSIX-Funktion `random()` erwartet a) kein Argument und liefert b) eine ganze Zahl zwischn 0 und RAND_MAX, also wie `rand()`. Deine Phobos-Variante ist also wohl auf Windows beschränkt.
@audax:
und:
Damit ist das komplizierter als ich bereit bin Zeit dafür zu opfern…
@Leonidas: Also bei Bigloo selbst habe ich so auf die Schnelle keine Schalter für dynamische Bibliotheken gefunden.
@audax:
Code: Alles auswählen
bj@s8n:~$ cabal
bash: cabal: command not found
Code: Alles auswählen
bj@s8n:~/src/mersenne-random-0.1.3$ runhaskell Setup.lhs configure
Setup.lhs: mersenne-random.cabal:42: 'Executable' stanza starting with field 'fl
ag small_base
description'
@Leonidas: Also bei Bigloo selbst habe ich so auf die Schnelle keine Schalter für dynamische Bibliotheken gefunden.
- mosenturm
- User
- Beiträge: 23
- Registriert: Dienstag 15. Juli 2008, 17:54
- Wohnort: Plauen
- Kontaktdaten:
Nochmal zu den Zeiten und dem (von mir) verursachten Durcheinander mit der Anzahl von Durchläufen:
Man sieht schön, dass bei der zehnfachen Anzahl der Durchläufe (1e7 anstatt 1e6) auch die Laufzeit ziemlich genau zehnmal so groß ist. Sehe ich das richtig, dass man da auch O(n) sagen könnte? O(n) ist doch auch das erstrebenswerte, wenn ich mich recht entsinne.
Liegt der Unterschied im Laufzeitverhalten zwischen random.rand(int/range) und der numpy Lösung in den C-Bibl. von numpy? Sind die Algorithmen zur Zufallszahlerzeugung so aufwändig, dass hier der Hase im Pfeffer liegt? Weshalb ist PHP an der Stelle so viel schneller? Der PHP Code hat ja tatsächlich 1e7 als Anzahl Durchläufe zu stehen.
Man sieht schön, dass bei der zehnfachen Anzahl der Durchläufe (1e7 anstatt 1e6) auch die Laufzeit ziemlich genau zehnmal so groß ist. Sehe ich das richtig, dass man da auch O(n) sagen könnte? O(n) ist doch auch das erstrebenswerte, wenn ich mich recht entsinne.
Liegt der Unterschied im Laufzeitverhalten zwischen random.rand(int/range) und der numpy Lösung in den C-Bibl. von numpy? Sind die Algorithmen zur Zufallszahlerzeugung so aufwändig, dass hier der Hase im Pfeffer liegt? Weshalb ist PHP an der Stelle so viel schneller? Der PHP Code hat ja tatsächlich 1e7 als Anzahl Durchläufe zu stehen.
Viele Grüße
Andreas
Andreas
@BlackJack:
Memo an mich selbst - C-Funktionen nur im Ausnahmefall benutzen (in der Dokumentation stand definitiv nicht Win32 only).
Variante in Phobos und definitiv ohne Win32-Zeug:
http://paste.pocoo.org/show/99766/
Besonders flott is's nich =/
Memo an mich selbst - C-Funktionen nur im Ausnahmefall benutzen (in der Dokumentation stand definitiv nicht Win32 only).
Variante in Phobos und definitiv ohne Win32-Zeug:
http://paste.pocoo.org/show/99766/
Besonders flott is's nich =/
Code: Alles auswählen
C:\Dokumente und Einstellungen\~\Desktop>dmd -O -run dicephobos.d
1.813
[1:1665915,2:1667017,3:1666102,4:1667758,5:1666285,6:1666923]
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Ja, das ist O(n), zwar nicht fatal aber nicht erstrebenswert. Man würde sich eher O(n log n) oder optimalerweise O(1) (also das berühmte "constant time") wünschen.mosenturm hat geschrieben:Sehe ich das richtig, dass man da auch O(n) sagen könnte? O(n) ist doch auch das erstrebenswerte, wenn ich mich recht entsinne.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
bekommt man das problem den ueberhaupt mit weniger als O(n) hin? also ich bin in dem thema noch ned allzubewandert... aber um ne schleife fuer die Anzahl der durchlaeufe kommt man ja nicht drumrum... also gehts in dem fall ja nicht besser als O(n)? oder versteh ich da irgendwas noch nicht so ganz?
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Nein, ich denke nicht. Ggf kann man ja das Problem anpassen, so dass so etwas nicht nötig wäre, aber die Operation ist wohl nicht besser als O(n) zu machen.zero-one hat geschrieben:bekommt man das problem den ueberhaupt mit weniger als O(n) hin?
Übrigens ist es manchmal gar nicht so trivial zu sagen, was für ein Problem die Effektivste Lösung ist. Siehe einige Informatikprobleme, die Beweise haben dass sie nicht in weniger als O(irgendwas) lösbar sind.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
http://de.wikipedia.org/wiki/NP_(Komplexitätsklasse)Leonidas hat geschrieben:Übrigens ist es manchmal gar nicht so trivial zu sagen, was für ein Problem die Effektivste Lösung ist. Siehe einige Informatikprobleme, die Beweise haben dass sie nicht in weniger als O(irgendwas) lösbar sind.
Falls jemand noch ein paar Informationen dazu haben möchte =) Algorithmik ist eines der interessantesten Gebiete in der Informatik.
Und ich kann mir nicht vorstellen, dass mit der vorgesehenen Datenstruktur (Zufallszahlen von 1~6) irgendeine Verbesserung der Komplexität möglich ist. Verbesserung auf n log n oder log n setzt ja immer vorraus, dass uns die Datenstrutkur auf irgendeine Weise bekannt ist... Wie der Unterschied zwischen linearer Suche, die bei ungeordneten Listen angewendet wird, oder der binären Suche, die bei geordneten Listen angewendet wird (dort ist uns also bekannt, was wir zu erwarten haben).
- mosenturm
- User
- Beiträge: 23
- Registriert: Dienstag 15. Juli 2008, 17:54
- Wohnort: Plauen
- Kontaktdaten:
Hier bei mir ergibt das Folgendes:BlackVivi hat geschrieben:...
Variante in Phobos und definitiv ohne Win32-Zeug:
http://paste.pocoo.org/show/99766/
Besonders flott is's nich =/
Code: Alles auswählen
C:\Dokumente und Einstellungen\~\Desktop>dmd -O -run dicephobos.d 1.813 [1:1665915,2:1667017,3:1666102,4:1667758,5:1666285,6:1666923]
Code: Alles auswählen
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
\dev\D>dmd -O -run rolling.d
1.485
[1:1666894,2:1667344,3:1665670,4:1666395,5:1666479,6:1667218]
Viele Grüße
Andreas
Andreas
Wisst ihr, was mich fasziniert? Wenn ich statt dem asoziativen Array einfach nur ein normales Array bei D benutz, ist das Programm deutlich flotter oO!
Erstmal mit Tango
Phobos ist auch ein wenig flotter
Erstmal mit Tango
Code: Alles auswählen
C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dice.d
0.59 seconds
[1667884, 1665633, 1665648, 1668525, 1665905, 1666405]
Code: Alles auswählen
C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dicephobos.d
1.344
[1667652,1666288,1666436,1666696,1666727,1666201]
Meine Common Lisp Kenntnisse sind zwar extrem bescheiden,
aber versuchen kann man's ja mal:
(SBCL)
Ergibt
auf meinem uralten Athlon 2400.
Und weils so schön war hier mit SWI-Prolog:
Eine Rekursionstiefe von 1e7 schafft Prolog natürlich nicht
(out of local Stack), daher nur 90000 Durchläufe.
Auch erfolgt das Updaten des Histogramms mit O(n)
(n = Anzahl der Würfelseiten) statt O(1), aber ich dachte mir,
ich poste das einfach mal.
Ausreichend didaktisches Material muesste ja jetzt vorliegen.
yipyip
aber versuchen kann man's ja mal:
(SBCL)
Code: Alles auswählen
(defparameter *max-throws* 10000000)
(defun dices (n)
(let ((histo (make-array '(6))))
(dotimes (i n)
(let* ((r (random 6))
(x (aref histo r)))
(setf (aref histo r) (1+ x))))
histo))
(defun main ()
(let ((histo (dices *max-throws*)))
(dotimes (i 6)
(format t "~D: ~D~%" (1+ i) (aref histo i)))))
Code: Alles auswählen
CL-USER> (time (main))
1: 1667830
2: 1666404
3: 1664453
4: 1667586
5: 1665540
6: 1668187
Evaluation took:
0.407 seconds of real time
0.400025 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
32,768 bytes consed.
Und weils so schön war hier mit SWI-Prolog:
Code: Alles auswählen
update([X|R], POS, POS, [Y|R]) :-
Y is X + 1.
update([X|R1], COUNT, POS, [X|R2]) :-
COUNT1 is COUNT + 1,
update(R1, COUNT1, POS, R2).
update([], _, _, []).
dices(N, L, HISTO) :-
N > 0,
X is random(6),
update(L, 0, X, L1),
N1 is N - 1,
dices(N1, L1, HISTO).
dices(_, L, L).
main(HISTO) :-
dices(90000, [0, 0, 0, 0, 0, 0], HISTO).
Code: Alles auswählen
?- time(main(X)).
% 990,635 inferences, 1.70 CPU in 1.83 seconds (93% CPU, 582726 Lips)
X = [15016, 14899, 15066, 14925, 14960, 15134]
(out of local Stack), daher nur 90000 Durchläufe.
Auch erfolgt das Updaten des Histogramms mit O(n)
(n = Anzahl der Würfelseiten) statt O(1), aber ich dachte mir,
ich poste das einfach mal.
Ausreichend didaktisches Material muesste ja jetzt vorliegen.
yipyip