Würfelsimulation

Code-Stücke können hier veröffentlicht werden.
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Würfelsimulation

Beitragvon mosenturm » Dienstag 13. Januar 2009, 15:58

Hallo an Alle,

ich würde gerne von Euch weitere Vorschläge haben, um eine Würfelsimulation zu programmieren.
Folgendes soll umgesetzt werden:

- Zahl zwischen 1 und 6 zufällig erzeugen
- aufrechnen, wie oft welche Zahl "gewürfelt" wurde
- Ausgabe: Zahl, Anzahl der Würfe

Um hier auch zu zeigen, welche Methode am Schnellsten ist, bitte als Grundgesamtheit 1e7 ansetzen und kein psyco benutzen.

Folgende Schnipsel habe ich schon:

Code: Alles auswählen

import random
import time

from collections import defaultdict

count = int(1e6)

dic = {}
start = time.time()
for _ in xrange(count):
    digit = random.randint(1, 6)
    if dic.has_key(digit):
        dic[digit] +=1
    else:
        dic[digit] = 1
##    print '*',
end = time.time()
print 'Dauer: %s sec' % (str(end - start),)
for k,v  in dic.iteritems():
    print 'Zahl: %d\tAnzahl: %d' % (k, v)

print '*' * 80
dic = {}
start = time.time()
for _ in xrange(count):
    digit = random.randint(1, 6)
    try:
        dic[digit] += 1
    except KeyError:
        dic[digit] = 1
end = time.time()
print 'Dauer: %s sec' % (str(end - start),)

print '*' * 80
dic = defaultdict(int)
start = time.time()
for _ in xrange(count):
##    digit = random.randrange(1, 7)
    digit = random.randint(1, 6)
    dic[digit] += 1

end = time.time()
print 'Dauer: %s sec' % (str(end - start),)
for k,v  in dic.iteritems():
    print 'Zahl: %d\tAnzahl: %d' % (k, v)


Danke für Eure Hilfe! Ich möchte das Ganze gerne an Schulen vorstellen, wo ich Computer AGs leite, um zu zeigen, dass viele Wege nach Rom führen.

Andreas
BlackJack

Beitragvon BlackJack » Dienstag 13. Januar 2009, 16:22

@mosenturm: Viel zu viel Code auf Modulebene. Die einzelnen Arten sollten in jeweils einer Funktion verschwinden.

`dic` ist als Abkürzung des Typs ein schlechter Name. Besser wäre ein Name der sagt, was für eine Bedeutung das Objekt hat. `histogramm` zum Beispiel.

`dict.has_key()` ist veraltet und sollte nicht mehr verwendet werden. Dafür gibt's den ``in``-Operator.

Ein Dictionary mit fortlaufenden Nummern als Schlüssel lässt sich auch prima durch eine Liste ersetzen.

Und eine Lösung mit `dict.get()` fehlt noch.
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Dienstag 13. Januar 2009, 16:33

BlackJack hat geschrieben:@mosenturm: Viel zu viel Code auf Modulebene. Die einzelnen Arten sollten in jeweils einer Funktion verschwinden.

Ich habe die einzelnen Methoden einfach untereinander geschrieben, weil ich das Ganze nur als Demo haben möchte. Die Strukturierung soll hier nicht betrachtet werden. Es ist klar, dass das Ganze so nicht in die freie Wildbahn gelassen wird.

BlackJack hat geschrieben:`dic` ist als Abkürzung des Typs ein schlechter Name. Besser wäre ein Name der sagt, was für eine Bedeutung das Objekt hat. `histogramm` zum Beispiel.

Ok, du hast recht. Ist auch nur ein schneller Entwurf von mir.

BlackJack hat geschrieben:`dict.has_key()` ist veraltet und sollte nicht mehr verwendet werden. Dafür gibt's den ``in``-Operator.

Hatte ich ursprünglich auch noch drin. Hat von der Zeit keinen Unterschied gemacht, deshalb ist es wieder verschwunden.

BlackJack hat geschrieben:Ein Dictionary mit fortlaufenden Nummern als Schlüssel lässt sich auch prima durch eine Liste ersetzen.

Und eine Lösung mit `dict.get()` fehlt noch.

Werde ich noch nachholen.

Danke!
Viele Grüße
Andreas
BlackJack

Beitragvon BlackJack » Dienstag 13. Januar 2009, 16:50

Wenn `has_key()` vs. ``in`` keinen Unterschied macht, dann kannst Du die ganzen Messungen in die Tonne kloppen, da die Unterschiede einfach zu klein sind um relevant zu sein. `has_key()` ist nämlich wesentlich aufwändiger in der Abarbeitung auf Bytecode-Ebene. Es wird von einem Objekt ein Attribut abgefragt und eine Methode aufgerufen, während ``in`` über eine schnelle feste Tabelle von Funktionszeigern angesprochen wird.
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Dienstag 13. Januar 2009, 17:08

BlackJack hat geschrieben:Wenn `has_key()` vs. ``in`` keinen Unterschied macht, dann kannst Du die ganzen Messungen in die Tonne kloppen.....

Hier mal die Zeiten für count = 1e7 auf meinem Notebook:
- Dauer has_key: 28.4059998989 sec
- Dauer try/except: 26.0160000324 sec
- Dauer defaultdict: 25.5620000362 sec
- Dauer digit in dic: 26.7350001335 sec

@BlackJack: Hast Recht ;-) digit in dic ist schneller als dic.has_key.
Viele Grüße

Andreas
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Dienstag 13. Januar 2009, 17:35

@mosenturm: Nimm Python 2.5, eine Liste statt eines Dictionaries und randrange statt randint, dann hast du die beste Performance.

Auf meinem System:
- Liste minimal schneller als defaultdict
- randrange ca. 10% schneller als randint
- Py 2.6 ca. 30% langsamer als 2.5
- Py 3.0 ca. 60% langsamer als 2.5

Außer Konkurrenz: Jython braucht ca. 2,5mal so lange wie CPython 2.5. Und die Listen-Variante ist dort sogar etwas langsamer als die Dict-Variante ...
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Dienstag 13. Januar 2009, 18:10

@numerix: Ich nutze Python 2.5

Hier die Zeiten mit randrange anstelle von randint:

- Dauer has_key: 29.6399998665 sec
- Dauer try/except: 27.0 sec
- Dauer defaultdict: 26.2030000687 sec
- Dauer digit in dic: 27.4849998951 sec

Ist bei mir nicht schneller :-( Randrange hatte ich Anfangs auch benutzt und dann gegen randint getauscht. Ein Profiling zeigt auch, dass das Erzeugen der Zufallszahlen die meiste Zeit beansprucht. Dann kommt die Arbeit mit dem Dictionary.

Liste werde ich noch testen.
Viele Grüße

Andreas
BlackJack

Beitragvon BlackJack » Dienstag 13. Januar 2009, 21:36

Wobei das hier alles nichts ist, was man Schülern zeigen sollte. Rechnet mal die Geschwindigkeitsunterschiede einzelnem Schleifendurchlauf aus. Jemandem der hier im Zweifelsfall wirklich 2 Sekunden Laufzeit über Lesbarkeit des Quelltextes stellt, gehört die Python-Lizenz entzogen. ;-)

Es ist wichtig den richtigen Algorithmus zu wählen, nur dass der hier im Grunde überall gleich ist, insbesondere die gleiche Komplexität bei Laufzeit und Speicherverbrauch im Sinne der O-Notation hat. Und solche Mikrooptimierungen sollte man erst machen, wenn man a) tatsächlich ein Problem mit der Laufzeit hat und b) mit dem Profiler geschaut hat, wo die Flaschenhälse liegen.

Nebenbei: Ein Pascal-Programm schafft das bei mir in unter 1½ Sekunden. ;-)
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Dienstag 13. Januar 2009, 21:44

Das alles dient nur zum Testen und wird den Schülern so garantiert nicht gezeigt. Ich wollte nur testen, ob sich bei diesem Beispiel durch die Auswahl unterschiedlicher Methoden, signifikante Laufzeitunterschiede ergeben. Das scheint aber offensichtlich nicht der Fall zu sein.

Somit wird hier nur gezeigt (natürlich als schöner Python Code ;-) ), dass es verschiedene Wege gibt, ein Problem zu lösen.

Edit:
Kann jemand mal ein PHP Programm dafür schreiben und die Laufzeit ermitteln?
Viele Grüße

Andreas
zero-one
User
Beiträge: 58
Registriert: Dienstag 20. Mai 2008, 20:52

Beitragvon zero-one » Dienstag 13. Januar 2009, 22:01

hab deins einfach fast 1 zu 1 in php uebertragen ...

Code: Alles auswählen


<?php
    $start 
microtime&#40;true&#41;;
    
for&#40;$i=0; $i < 10000000; ++$i&#41;&#123;
        
$digit rand&#40;1,6&#41;;
        
$numbers[$digit] +=1;
    &
#125;
    
$end microtime&#40;true&#41;;
    
    
echo "Dauer: " . &#40;$end-$start&#41;. " sec\n\n";
    
foreach&#40;$numbers as $digit => $times&#41;
        
echo "Zahl: &#123;$digit&#125;\tAnzahl: &#123;$times&#125;\n";
?>


bei mir laeuft das in: 'Dauer: 6.5329959392548 sec'
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Beitragvon cofi » Dienstag 13. Januar 2009, 22:24

Der Ursprungscode läuft hier in
Dauer: 7.02060699463 sec
Dauer: 6.48057293892 sec
Dauer: 6.30209612846 sec


Um da mal eine andere Messung einzuwerfen ;)

Python 2.6, Gentoo Linux 2.6.28, Celeron M 1,6 GHz
zero-one
User
Beiträge: 58
Registriert: Dienstag 20. Mai 2008, 20:52

Beitragvon zero-one » Dienstag 13. Januar 2009, 22:36

oh hab beim php code vergessen den Rechner dazuzuschreiben.
php 5.2.6 Mac OS X Core2Duo 2Ghz

// edit die ergbnisse sind falsch da oben 1e6 steht
btw. der python code von ganz oben laeuft bei mir mit python 2.6.1:
[code=]
Dauer: 4.70081806183 sec
Dauer: 4.25815701485 sec
Dauer: 4.26043891907 sec
[/code]

// edit 2 hier die richtigen werte
python 2.6.1
[code=]
Dauer: 47.3008830547 sec
Dauer: 43.6763179302 sec
Dauer: 43.6270251274 sec
[/code]

python 2.5.4
[code=]
Dauer: 45.706359148 sec
Dauer: 42.0972189903 sec
Dauer: 43.6542031765 sec
[/code]
komischerweise bin ich nu nedmal mehr im 20 sec bereich wie die anderen hier... hmm...


Python is schneller als php .. yeahy <-- hat sich nu wohl auch erledigt :-(
wieso ist python hier so viel langsamer?
Zuletzt geändert von zero-one am Dienstag 13. Januar 2009, 23:24, insgesamt 1-mal geändert.
Benutzeravatar
mosenturm
User
Beiträge: 23
Registriert: Dienstag 15. Juli 2008, 17:54
Wohnort: Plauen
Kontaktdaten:

Beitragvon mosenturm » Dienstag 13. Januar 2009, 22:42

Mein Rechner:
Fujitsu Siemens Esprimo Notebook, Mobile Pentium Dual Core T2410 2 GHz
Win XP Prof. SP 3
Python 2.5.2
Viele Grüße

Andreas
zero-one
User
Beiträge: 58
Registriert: Dienstag 20. Mai 2008, 20:52

Beitragvon zero-one » Dienstag 13. Januar 2009, 23:05

auch wenns ned gefragt war ich habs mit dem bissle krueppel c++ was ich kann auch nommal in c++ gemacht wobei es eher c ist *g*


Code: Alles auswählen

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <sys/time.h>
using namespace std;

int main(int argc, char** argv){
   time_t seed;
   timeval start, end;
   
   time(&seed);
   srand((unsigned)seed);
   
   gettimeofday(&start, 0);
   
   int numbers[6] = {0, 0, 0, 0, 0, 0};
   for(int i =0; i< 10000000; ++i){
      int digit = rand() % 6;
      numbers[digit] += 1;
   }
   
   gettimeofday(&end, 0);
   
   cout << start.tv_sec << ':' << start.tv_usec  << endl;
   cout << end.tv_sec << ':' << end.tv_usec << endl << endl;
   for(int i = 0; i < 6; ++i){
      cout << "Zahl: " << i+1 << "\t Anzahl:" << numbers[i] << endl;
   }
}


da es mir jetzt zu kompliziert war da die genauen milisekunden rauszurechnen hab ichs einfach mal so hingeschrieben...

bei mir auf dem System dauert das Ausfuehren 0.229000 sec wenn ich mich ned boes verrechnet habe...
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Mittwoch 14. Januar 2009, 00:01

Code: Alles auswählen

(defn reg-dic
  [hist roll]
  (merge-with + {roll 1} hist))
 
(def rolls (repeatedly #(+ 1 (rand-int 6))))
(time (print (reduce reg-dic {} (take 1e6 rolls))))

Braucht aber auch gut 6 Sekunden :D
Die Zufallszahlen sind sehr teuer...


Code: Alles auswählen

;;;; (time (print (reduce reg-dic {} (take 1e6 rolls)))) ...
{1 166794, 2 166856, 3 166850, 4 165899, 5 166950, 6 166651}"Elapsed time: 6707.7616 msecs"
user>
;;;; (time (print (reduce reg-dic {} (take 1e6 rolls)))) ...
{1 166794, 2 166856, 3 166850, 4 165899, 5 166950, 6 166651}"Elapsed time: 5518.030015 msecs"

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder