Würfelsimulation

Code-Stücke können hier veröffentlicht werden.
zero-one
User
Beiträge: 58
Registriert: Dienstag 20. Mai 2008, 20:52

Beitragvon zero-one » Mittwoch 14. Januar 2009, 00:17

audax du laesst es ja au mit 1e6 laufen ... Aufgabenstellung ist ja 1e7 ist im obersten Script vom Threadersteller falsch.

weil mir grad langweilig ist:

Code: Alles auswählen

srand()
start_ = Time.new
numbers = Hash.new(0)
for i in 0...10000000 do
   num = rand(6)
   numbers[num] += 1
end
end_ = Time.new

puts "Dauer: "+(end_ - start_).to_s + " Sekundenn\n"
numbers.each do |k, v|
   puts "Zahl: #{k+1}\tAnzahl: #{v}"
end


Dauer: 8.301156 Sekundenn

hmm .. also langsam kommen mir die Zahlen von meinem Python versuch spanisch vor... oO
BlackJack

Beitragvon BlackJack » Mittwoch 14. Januar 2009, 08:55

Die Pascal-Implementierung: http://paste.pocoo.org/show/99564/

Meine Python-Implementierung mit `defaultdict`:

Code: Alles auswählen

from collections import defaultdict
from random import randint

N = int(1e7)
DICE_SIDES = 6

def main():
    histogram = defaultdict(int)
    for dummy in xrange(N):
        histogram[randint(1, DICE_SIDES)] += 1
    for value, count in sorted(histogram.iteritems()):
        print '%d:  %d' % (value, count)


Zeiten auf meinem Rechner (in Sekunden):

34.366 Python (2.5)
00.435 Pascal
00.241 zero-one's C++-Implementierung

Also wenn Python 140× langsamer als C++ ist, sollte ich vielleicht doch die Sprache wechseln. Produktivität und Spass beim Programmieren wird überschätzt. ;-)
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Mittwoch 14. Januar 2009, 09:26

na dann:

Code: Alles auswählen

{1 1666835, 2 1666165, 3 1667203, 4 1667724, 5 1665771, 6 1666302}"Elapsed time: 66100.259321 msecs"


Und Haskell:
http://paste.pocoo.org/show/99567/

Code: Alles auswählen

[(1,1666821),(2,1664322),(3,1667503),(4,1667076),(5,1667697),(6,1666581)]
23

Also 23 Sekunden

Warum ist Haskell so lahm? :(

€dit:
Blackies hat 29s
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Beitragvon veers » Mittwoch 14. Januar 2009, 10:40

zero-one hat geschrieben:int digit = rand() % 6;
Falsch.

Durch das Modulo gibst du dem Ergebnis einen Bias ;)

Meine cython variante, auf meinem System ~20mal schneller als die pure python variante.

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

- Jonas
Zuletzt geändert von veers am Mittwoch 14. Januar 2009, 14:48, insgesamt 1-mal geändert.
My Website - 29a.ch
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Beitragvon HerrHagen » Mittwoch 14. Januar 2009, 10:53

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.

Code: Alles auswählen

import numpy
dice = numpy.random.randint(1,7,1e7)
hist = numpy.histogram(dice, bins=[1,2,3,4,5,6,7], new=True)
print hist[0]

Das bläuft bei mir in 0.4s (Py2.5, numpy1.2.1, WinXP, AMD Turion64x2 1.9GHz).

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

MFG HerrHagen
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Beitragvon HerrHagen » Mittwoch 14. Januar 2009, 10:58

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

Beitragvon mosenturm » Mittwoch 14. Januar 2009, 11:19

HerrHagen hat geschrieben: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)

HerrHagen hat geschrieben:<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 ;-)
Viele Grüße
Andreas
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Mittwoch 14. Januar 2009, 11:48

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

Beitragvon mosenturm » Mittwoch 14. Januar 2009, 11:55

rayo hat geschrieben: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.
Viele Grüße

Andreas
BlackJack

Beitragvon BlackJack » Mittwoch 14. Januar 2009, 13:37

@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
User
Beiträge: 58
Registriert: Dienstag 20. Mai 2008, 20:52

Beitragvon zero-one » Mittwoch 14. Januar 2009, 13:43

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
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Mittwoch 14. Januar 2009, 13:52

@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

Beitragvon BlackJack » Mittwoch 14. Januar 2009, 14:18

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)
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 14. Januar 2009, 14:29

zero-one hat geschrieben: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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 14. Januar 2009, 15:02

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

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder