Würfelsimulation

[HerrHagen]

Achso,... Da fällt mir noch was ein. Unter WinXP solltest du statt time.time (unzuverlässig) besser time.clock verwenden.

time.clock -> Windows
time.time -> Unix

[mosenturm]

Du kannst das ganze auch in Python verdammt fix machen, du mußt nur das richtige Werkzeug nehmen. Zur Lösung numerischer Probleme gibt es numpy.
Das bläuft bei mir in 0.4s (Py2.5, numpy1.2.1, WinXP, AMD Turion64x2 1.9GHz).

Habe jetzt auch mal mit numpy dein Beispiel laufen lassen:
Dauer: 0.920265415402 (Mobile Pentium Dual Core T2410 2 GHz
Win XP Prof. SP 3, Python 2.5.4)

<Oberlehrer>
Ich würd nicht zuviel Zeit auf die Laufzeit-Optimierung von reinen Python-Code verschwenden, schon gar nicht im Rahmen eines Anfängerkurses. Du willst die Leute ja zu guten Python und nicht zu C-Programmiern erziehen.
"premature optimization is the root of all evil"
</Oberlehrer>

Ich habe das ja nur für mich getestet, um zu wissen, ob man das Beispiel vielleicht verwenden kann. Es soll nicht die Optimierung des Codes im Vordergrund stehen, sondern die Auswahl des besten Algorithmus.

Auf jeden Fall weiß ich jetzt, dass das random Modul der StdLib zur Bremse werden kann. Das ist doch auch was Wert

[rayo]

Auf jeden Fall weiß ich jetzt, dass das random Modul der StdLib zur Bremse werden kann. Das ist doch auch was Wert

Wie kommst du darauf?

Code: Alles auswählen

import time
from collections import defaultdict
from random import randint, random

N = int(1e7)

def test_random():
    histogram = defaultdict(int)
    start = time.time()
    for dummy in xrange(N):
        histogram[(int(random()*6))+1] += 1
    end = time.time()    
    print 'Laufzeit mit random: %f' % (end-start)
    for value, count in sorted(histogram.iteritems()):
        print '%d:  %d' % (value, count)

def random_replacement():
    return 0.5

def test_without_random():
    histogram = defaultdict(int)
    start = time.time()
    for dummy in xrange(N):
        histogram[(int(random_replacement()*6))+1] += 1
    end = time.time()    
    print 'Laufzeit ohne random: %f' % (end-start)
    for value, count in sorted(histogram.iteritems()):
        print '%d:  %d' % (value, count)
        
test_random()
test_without_random()

Code: Alles auswählen

Laufzeit mit random: 12.790084
1:  1666632
2:  1666861
3:  1666019
4:  1668770
5:  1665630
6:  1666088
Laufzeit ohne random: 13.357360
4:  10000000

Bei mir ist random sogar schneller. Also das Modul ist sicher nicht langsam.

Hier ist die Funktion randint und Python allgemein schuld an der langen Laufzeit. Schau mal randint/randrange an (in der Datei random.py von Python).

Gruss

Gruss

[mosenturm]

Hier ist die Funktion randint und Python allgemein schuld an der langen Laufzeit. Schau mal randint/randrange an (in der Datei random.py von Python).

Diese Funktionen meinte ich auch. Mit den beiden hatte ich getestet.

[BlackJack]

@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.

@veers: Modulo mag zwar falsch sein, aber IMHO ist das Ergebnis gut genug.

@all: Und noch eine Lösung in Scheme, mit Bigloo compiliert: http://paste.pocoo.org/show/99602/

36.863 Haskell (von audax)
34.366 Python (2.5 -- `defaultdict`)
00.820 Python (2.5 -- mit `numpy` von HerrHagen)
00.541 Scheme (Bigloo-Compiler)
00.435 Pascal (FreePascal)
00.241 C++ (von zero-one)

[zero-one]

hmm.. passt zwar nicht ganz rein ... aber wieso is der modulo falsch? Ich dachte das ist die gaenige Art die Zufallszahlen zu begrenzen.

Mich wundert es trotzdem das python mit der stdlib also ohne zusaetze wie numpy so weit hinter php und sogar ruby zurueckliegt...

Ich dachte des wird auf knapp schlechter als php und deutlich besser als ruby hinauslaufen.

komisch komisch...

[rayo]

@BlackJack

Und wie siehts damit aus? Kannst du deine kleine Tabelle damit erweitern?

Code: Alles auswählen

import time
from collections import defaultdict
from random import random
def test():
    histogram = defaultdict(int)
    start = time.time()
    for dummy in xrange(N):
        histogram[(int(random()*6))+1] += 1
    end = time.time()   
    print '%6.3f Python (2.5 -- random anstatt randint)' % (end-start)
    for value, count in sorted(histogram.iteritems()):
        print '%d:  %d' % (value, count)
test() 

Damit liegts bei mir nicht so extrem weit hinten.

Gruss

[BlackJack]

Ich habe das Würfel in eine eigene Funktion rausgezogen:

36.863 Haskell (von audax)
34.366 Python (2.5 -- `defaultdict`)
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)

[Leonidas]

Mich wundert es trotzdem das python mit der stdlib also ohne zusaetze wie numpy so weit hinter php und sogar ruby zurueckliegt...

Wo ist der PHP und Ruby-Code? Du hast jetzt keine Benchmarksergebnisse geschrieben, somit ist das erstmal nur eine Behauptung.

[numerix]

Ja, ich habe den Ausgangsbeitrag gelesen.

Hat mich trotzdem interessiert, wie viel psyco hierbei rausholen kann. Auf meinem System erreiche ich damit gegenüber der schnellsten Python-Variante (mit Liste und random() statt randrange/randint) eine Laufzeiteinsparung von gut 60%. Immerhin.

An die Zeit von Pascal (ich habe auch seit langer Zeit dann mal wieder meinen Pascal-Compiler angeworfen ...) ist aber auch damit nicht zu denken. (Trotzdem ist mir Python lieber).

[zero-one]

@Leonidas doch habe ich .. schau mal genauer hin

[Leonidas]

Tatsache. :ooops: Lesen sollte man können. Hat mich nur gewundert, warum BlackJack die Zahlen nicht in das Ranking mit aufgenommen hat.

[BlackJack]

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)

[audax]

Ich mach mich nochmal an die Haskell-Lösung

Btw, Leonidas: Bitte mit -O2 kompilieren

[audax]

@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.

Das lag nur(!) an der lahmen Random-Funktion... >.<
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

[BlackJack]

Code: Alles auswählen

bj@s8n:~$ ghc -O3 test.hs

test.hs:1:0:
    Failed to load interface for `System.Random.Mersenne'

Ich weiss nicht ob ich Lust habe mich jetzt mit dem Cabal-Kram herum zu schlagen.

[BlackVivi]

Meine Variante in D

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

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}

//Und dasselbe nochmal mit Phobos

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]

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.

[audax]

Code: Alles auswählen

bj@s8n:~$ ghc -O3 test.hs

test.hs:1:0:
    Failed to load interface for `System.Random.Mersenne'

Ich weiss nicht ob ich Lust habe mich jetzt mit dem Cabal-Kram herum zu schlagen.

Code: Alles auswählen

cabal install mersenne-random

Ist nur das eine Modul

Übrigens int numpy böse. Die Zeit die es braucht macht ja Angst!

[Leonidas]

Ü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.

[BlackJack]

@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:

Code: Alles auswählen

bj@s8n:~$ cabal
bash: cabal: command not found

und:

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'

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.