Seite 1 von 3

Verfasst: Mittwoch 14. Januar 2009, 00:17
von zero-one
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

Verfasst: Mittwoch 14. Januar 2009, 08:55
von BlackJack
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. ;-)

Verfasst: Mittwoch 14. Januar 2009, 09:26
von audax
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

Verfasst: Mittwoch 14. Januar 2009, 10:40
von veers
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

Verfasst: Mittwoch 14. Januar 2009, 10:53
von HerrHagen
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

Verfasst: Mittwoch 14. Januar 2009, 10:58
von 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

Verfasst: Mittwoch 14. Januar 2009, 11:19
von mosenturm
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 ;-)

Verfasst: Mittwoch 14. Januar 2009, 11:48
von rayo
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

Verfasst: Mittwoch 14. Januar 2009, 11:55
von mosenturm
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.

Verfasst: Mittwoch 14. Januar 2009, 13:37
von 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)

Verfasst: Mittwoch 14. Januar 2009, 13:43
von 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...

Verfasst: Mittwoch 14. Januar 2009, 13:52
von 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

Verfasst: Mittwoch 14. Januar 2009, 14:18
von 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)

Verfasst: Mittwoch 14. Januar 2009, 14:29
von Leonidas
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.

Verfasst: Mittwoch 14. Januar 2009, 15:02
von 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).

Verfasst: Mittwoch 14. Januar 2009, 15:43
von zero-one
@Leonidas doch habe ich .. schau mal genauer hin

Verfasst: Mittwoch 14. Januar 2009, 15:53
von Leonidas
Tatsache. :ooops: Lesen sollte man können. Hat mich nur gewundert, warum BlackJack die Zahlen nicht in das Ranking mit aufgenommen hat.

Verfasst: Mittwoch 14. Januar 2009, 17:47
von 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)

Verfasst: Mittwoch 14. Januar 2009, 19:11
von audax
Ich mach mich nochmal an die Haskell-Lösung :D

Btw, Leonidas: Bitte mit -O2 kompilieren ;)

Verfasst: Mittwoch 14. Januar 2009, 23:00
von audax
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.
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 :D