Primzahlen Berechnung in 4Varianten

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Iopodx
User
Beiträge: 68
Registriert: Sonntag 5. September 2004, 08:58

Primzahlen Berechnung in 4Varianten

Beitragvon Iopodx » Donnerstag 10. März 2005, 11:19

Hiho Gemeinde,

hab mal fix was gecodet, vielleicht brauch der eine oder andere das Programm mal.

Hier kann man auch gut sehen, das xrange durchaus schneller als range ist. Desweiteren gibt es noch die funktion pass oder break, wobei break weitaus schneller ist, da es schon abbricht wenn die Zahl durch irgendeine Teilbar ist, bei pass wird das einfach ignoriert!

Viel Spaß!

Code: Alles auswählen

from time import time
from math import sqrt

def check_if_prime_old(a):
    if a%2==0 and a!=2:
        return 0
    else:
        for b in range(3, int(sqrt(a))+1, 2):
            if a%b==0:
                return 0
        return 1

def check_if_prime_new(a):
    if a%23!=0:
        for b in xrange(27, int(sqrt(a))+1, 2):
            if a%b == 0:
                return 0
        return 1
    else: return 0

def start_old(ranges):
    result=[]
    times=[time(), 0, 0]
    for i in range(3, ranges-1):
        if check_if_prime_old(i)==1:
            result.append(i)
    times[1]=time()
    times[2]=times[1]-times[0]
    return [times[2], [2]+result, len([2]+result)]

def start_new(ranges):
    result=[]
    times=[time(), 0, 0]
    for i in xrange(5, ranges-1, 2):
        if i%3!=0 and i%5!=0 and i%7!=0 and i%11!=0 and i%13!=0 and i%17!=0 and i%19!=0:
            if check_if_prime_new(i)==1:
                result.append(i)
    times[1]=time()
    times[2]=times[1]-times[0]
    result=[2, 3, 5, 7, 11, 13, 17, 19, 23]+result
    return [times[2], result, len(result)]


ranges=2
result=[[0, 0, 0], [0, 0, 0]]
for i in range(ranges):
    a=start_new(200000)
    b=start_old(200000)
    result[0][0]=result[0][0]+a[0]
    result[1][0]=result[1][0]+b[0]
    result[0][1]=a[1]
    result[1][1]=b[1]
    result[0][2]=a[2]
    result[1][2]=b[2]

result[0][0]=result[0][0]/ranges
result[1][0]=result[1][0]/ranges
print result[0][0]-result[1][0]
print result[0][0], result[1][0]
print result[0][2], result[1][2]


Edit//Garnicht gesehn das Leonidas vor 8Tagen ein ähnliches Prog gecodet hat xD

Edit2// Neuer Code! Vieeeel schneller!
Zuletzt geändert von Iopodx am Sonntag 13. März 2005, 22:31, insgesamt 3-mal geändert.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Re: Primzahlen Berechnung in 4Varianten

Beitragvon Leonidas » Donnerstag 10. März 2005, 13:39

Iopodx hat geschrieben:Edit//Garnicht gesehn das Leonidas vor 8Tagen ein ähnliches Prog gecodet hat xD

Nicht vor 8 Tagen sondern vor einigen Monaten bzw Jahren :) Aber gut dass du mich daran erinnerst, ich werde auch noch tunen, so ist dort ein Paradefall für Generatoren :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » Donnerstag 10. März 2005, 16:25

Übrigens: anstatt alle Zahlen von 2 bis N als Teiler zu testen, reicht es, 2 bis sqrt(N) zu testen.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 10. März 2005, 16:50

Wo wir grad dabei sind: Ich habe meinen Benchmark auch noch weiter getunt. Hat jemand für checkPrime() noch Verbesserungsvorschläge?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
chaos
User
Beiträge: 52
Registriert: Samstag 21. August 2004, 11:19

Beitragvon chaos » Donnerstag 10. März 2005, 16:56

Joghurt hat geschrieben:Übrigens: anstatt alle Zahlen von 2 bis N als Teiler zu testen, reicht es, 2 bis sqrt(N) zu testen.

Und dann gleich testen, ob sqrt(N) evtl. schon prim ist, und dann erst mit dem Testen von 2 bis floor(sqrt(N))-1 anfangen.
Slackware will never die.
BlackJack

Re: Primzahlen Berechnung in 4Varianten

Beitragvon BlackJack » Freitag 11. März 2005, 00:39

Iopodx hat geschrieben:Hier kann man auch gut sehen, das xrange durchaus schneller als range ist. Desweiteren gibt es noch die funktion pass oder break, wobei break weitaus schneller ist, da es schon abbricht wenn die Zahl durch irgendeine Teilbar ist, bei pass wird das einfach ignoriert!


``break`` und ``pass`` sind keine Funktionen sondern Schlüsselwörter von Python.

Und zu dem Einsatz von ``pass`` zwei Fragen: Warum lässt Du den ``else``-Zweig nicht komplett weg, wenn er nichts tut? Warum lässt Du die beiden ``pass`` Funktionen nicht weg, wenn doch klar ist, das sie völlig unnötig weiterrechnen?

Das hier:

Code: Alles auswählen

def count(tocount):
    result=0
    for current in tocount:
        result=result+1
    return result


lässt sich übrigens kürzer so schreiben:

Code: Alles auswählen

count = len


Ist nicht nur kürzer, sondern auch schneller die eingebaute len()-Funktion zu benutzen ;-)

Die Zeit würde ich übrigens nicht in den Funktionen testen sondern den Code nur an einer Stelle schreiben und die Funktionen in einer Schleife durchtesten. Ungefähr so:

Code: Alles auswählen

for func in (prime_xrange_and_break, prime_xrange_and_pass,
             prime_range_and_break, prime_range_and_pass):
    start = time()
    result = func(2000)
    duration = start - time()
    print duration, result
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Re: Primzahlen Berechnung in 4Varianten

Beitragvon Leonidas » Freitag 11. März 2005, 13:36

BlackJack hat geschrieben:lässt sich übrigens kürzer so schreiben:

Code: Alles auswählen

count = len


Ist nicht nur kürzer, sondern auch schneller die eingebaute len()-Funktion zu benutzen ;-)

Vor allem da das ja in den builtins ist und somit in C geschrieben ist. Außerdem lesbarer, da alle gleich wissen was len() macht.

Dass xrange() schneller ist als range() kann schon sein, aber vor allem nimmt es weitaus weniger Speicher, da es keine Liste mit der gegebenen Länge erstellt, sondern einen Generator erstellt, der die Elemente nur auf Verlangen erstellt.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Iopodx
User
Beiträge: 68
Registriert: Sonntag 5. September 2004, 08:58

Beitragvon Iopodx » Sonntag 13. März 2005, 22:33

Hab mal neuen Code geadded!

Ist komplett überarbeitet und vieel schneller!

Hoffe dass, das nicht als cheaten gilt! ;)

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder