Würfelsimulation

Code-Stücke können hier veröffentlicht werden.
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Donnerstag 15. Januar 2009, 13:02

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.
http://de.wikipedia.org/wiki/NP_(Komplexitätsklasse)

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).
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Donnerstag 15. Januar 2009, 13:41

BlackVivi hat geschrieben:...
Variante in Phobos und definitiv ohne Win32-Zeug:

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

Besonders flott is's nich =/

[code=]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]


Hier bei mir ergibt das Folgendes:
[code=]
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]
[/code]

BTW: So bin ich endlich dazu gekommen, mir auch mal D (dmd) zu installieren.
Viele Grüße
Andreas
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Donnerstag 15. Januar 2009, 18:17

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

[code=]C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dice.d
0.59 seconds
[1667884, 1665633, 1665648, 1668525, 1665905, 1666405][/code]

Phobos ist auch ein wenig flotter

[code=]C:\Dokumente und Einstellungen\BlackVivi\Desktop>dmd -O -run dicephobos.d
1.344
[1667652,1666288,1666436,1666696,1666727,1666201][/code]
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Donnerstag 15. Januar 2009, 22:12

Meine Common Lisp Kenntnisse sind zwar extrem bescheiden,
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)))))


Ergibt

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.

auf meinem uralten Athlon 2400.


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]


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. :)

:wink:
yipyip

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder