Primzahlenrechner

[nooby]

Hallo liebe Python-Profis

Ich habe mich wieder ein Mal hingesetzt und ein Wenig programmiert.
Und zwar ein Primzahlenrechner,welcher alle Primzahlen von z.B. 1 bis 100 in eine Datei schreibt.
Beim nächsten Start liest er aus der Datei ein, wo er stehen geblieben ist und man kann eingeben bis zu welcher Zahl er wieder rechnen soll.
Das ganze funktioniert auch relativ gut. Aber wenn ich alle Primzahlen "printe", dann ist das Programm sehr langsam.
Ich habe auch bereits gelesen, dass dies am Windows Terminal liegt, welches einfach Zeit fürs Ausgeben benötigt.
Jetzt habe ich gedacht, dass ich das ganze über einen _thread realisieren könnte, aber ich kann mir einfach nicht vorstellen wie das gehen sollte. Zudem lastet mein Programm nur einen CPU-Kern aus, was nicht optimal ist.
Kann ich dies ebenfalls über _thread ändern?
Gerne nehme ich auch Verbesserungsvorschläge entgegen. Auch wenn ihr Tipps habt, wie ich die Performance verbessern kann, bin ich dankbar.

Danke für eure Hilfe

Code: Alles auswählen

import time
isPrime = True
try:
    db = open("primes.txt", "r")
    last = int(db.read().splitlines()[-1])
    print("Es beginnt bei:", last)
    db.close()
except:
    print("Noch keine Datei vorhanden. Sie wird neu angelegt.")
    last = 2
db = open("primes.txt", "a")
start = last
ende = int(input("Endzahl: "))
if ende < start:
    print("Das Ende muss grösser sein, als der bereits berechnete Teil.")
    print("Es beginnt bei:", last)
    ende = int(input("Endzahl: "))
startTime = time.clock()
def isPrime(zahl):
    for x in range(2, int(zahl**0.5)+1):
        if zahl % x == 0:
            return False
    return True

for i in range(start, ende+1):
    if isPrime(i) == True:
        db.write(str(i)+"\n")
        db.flush()
db.close()
endTime = time.clock()
time = (endTime-startTime)/60
print("Alle Primzahlen von {0} bis {1} wurden berechnet. Das hat {2} Minuten gedauert.".format(last, ende, round(time, 3)))
    

[Hyperion]

Die erste wesentliche Verbesserung wäre es, das ganze mittels Funktionen in voneinander unabhängige Komponenten zu zerlegen! Also z.B. eine Funktion zum Prüfen, ob eine Zahl eine Primzahl ist, eine für das Speichern, eine für das Einlesen der bisher berechneten, usw.

[Sirius3]

Hallo nooby,

»_thread« ist ein internes Modul, benutze statt dessen »threading«. Das beschleunigt aber nichts, weil Python nur einen Kern auslasten kann.
Deine isPrime-Funktion versteckt sich relativ gut zwischen dem ganzen anderen Code. Setz sie doch an den Anfang, und da Du schonmal dabei bist, kannst Du alles in eine main-Funktion und vielleicht noch ein paar neue Funktionen einbauen.
»except« sollte nur einen IOError abfangen und nicht alles.
statt db.read().splitlines() gibt es auch db.readlines() bzw. list(db).
Nutze »with open()«.
Auf True wird automatisch bei if geprüft, ein ==True ist überflüssig.

Primzahlen bis 1Mio brauchen bei mir 23 Sekunden.

[Hyperion]

Für wirkliche Parallelisierung böte sich das multiprocessing-Modul an.

[nooby]

Gute, ich probiere das Programm umzuschreiben und in Funktionen zu zerlegen.
Noch eine Frage, was ist genau besser daran, "with open" zu benutzen?
Sorry finde nichts im Internet, was ich begreife

Noch mals Danke für eure Mühe

[Hyperion]

Noch eine Frage, was ist genau besser daran, "with open" zu benutzen?
Sorry finde nichts im Internet, was ich begreife

Mit ``with`` wird sicher gestellt, dass nach Beendigung der Operation - egal ob regulär oder durch eine Exception - auf jeden Fall die ``close()``-Methode aufgerufen wird. Ein Stichwort fürs Netz wäre wohl u.a. "Context Manager" - denn genau dieses Interface spricht ``with`` an.

[nooby]

Gut, ich habe das Programm umgeschrieben. Code weiter unten.
Noch 2 Fragen zur Sicherheit:

1. Wenn ich Dateien mit 'with open' öffne, muss ich sie nicht mehr explizit mit 'close()' schlissen.
2. Multiprocessing bringt in meinem Fall keine Geschwindigkeitssteigerung, da Python nur einen Kern nutzt.

Was kann ich sonst noch tun, um mein Programm schöner und schneller zu gestalten.

Ich freue mich auf eure konstruktive Kritik.

Code: Alles auswählen

import time
import os

def bereitsBerechnet(fileName):
    with open(fileName) as file:
        last = file.readlines()[-1]
    last = last.strip()
    return int(last)

def isPrime(zahl):
    for x in range(2, int(zahl**0.5)+1):
        if zahl % x == 0:
            return False
    return True

def savePrime(prime, fileName):
    with open(fileName, "a") as file:
        file.write(str(prime)+"\n")
        file.flush()
    return True

def generateCheckSaveNumber(start, ende, fileName):
    for i in range(start, ende+1):
        if isPrime(i):
            savePrime(i, fileName)
    return True
            
def fileExist(fileName):
    if os.path.isfile(fileName):
        return True
    else:
        return False
    
def main():
    startTime = time.clock()
    if fileExist("primes.txt"):
        start = bereitsBerechnet("primes.txt")
        print("Es wurde bereits bis {0} berechnet".format(start))
        ende = int(input("Bitte gib ein, wie weit du berechnen möchtest: "))
    else:
        start = 2
        ende = int(input("Bitte gib ein, wie weit du berechnen möchtest: "))
        with open("primes.txt", "w") as file:
            pass
    if generateCheckSaveNumber(start, ende, "primes.txt"):
        endTime = time.clock()
        usedTime = round((endTime-startTime)/60, 4)
        print("Super. Es wurden alles Zahlen bis {0} berechnet. Dafür hat dein Computer {1} Minuten gebraucht".format(ende, usedTime))
if __name__ == "__main__":
    main()

[Hyperion]

2. Multiprocessing bringt in meinem Fall keine Geschwindigkeitssteigerung, da Python nur einen Kern nutzt.

Öh... hast Du Dir die Doku überhaupt einmal durchgelesen - also die ersten *drei* Zeilen?

[nooby]

Habe ich nicht...
Ich habe mich nur auf die Aussage meines Vorposters bezogen.

»_thread« ist ein internes Modul, benutze statt dessen »threading«. Das beschleunigt aber nichts, weil Python nur einen Kern auslasten kann.

Das heißt, dass ich mit multiprocessing die Geschwindigkeit erhöhen könnte?
Was kann ich sonst noch tun, um meinen Code schneller zu machen?

[nooby]

Ich habe gerade bemerkt, dass mein neuer Code extrem viel länger braucht.
Für alle Primzahlen von 1 bis 1Mio benötigt es 8 Minuten, mein anderes gerade 25 Sekunden.
Woran könnte das liegen?? Vielleicht daran, dass ich die Datei in jeder Funktion neu öffne?

[BlackJack]

@nooby: Die Namensgebung hält sich nicht an die Namenskonvention für Funktionen und Variablen (kleinbuchstaben_mit_unterstrichen).

`file` ist der Name eines eingebauten Typs, den sollte man nicht an etwas anderes binden.

Statt die gesamte Datei in eine Liste zu lesen nur um dann die letzte Zeile zu verwenden, hätte man die Zeilen auch alle in einer Schleife lesen können ohne sie im Speicher zu halten. Der Fall dass die Datei leer ist, wird nicht berücksichtigt.

`fileExists()` ist überflüssig, denn ganz offensichtlich macht die Funktion das selbe wie `os.path.isfile()`. Letztlich ist das Vorgehen aber sowieso nicht „pythonisch”. Man würde einfach die Datei öffnen und auslesen. Wenn dabei eine Ausnahme auftritt, dann muss man offensichtlich von zwei anfangen. Das würde ich alles in die Funktion stecken, die ausliest mit welcher Zahl weiter gemacht werden soll. Die gibt dann entweder die letzte Zahl aus der Datei oder eben 2 zurück. Das macht den Quelltext wesentlich einfacher an der Stelle.

Es ist nicht nötig `flush()` auf einer Datei aufzurufen, die danach sofort geschlossen wird. Andererseits ist das ständige öffnen und schliessen der Datei für jede einzelne Zahl ineffizient. Warum `savePrime()` den Rückgabewert `True` hat, ist mir nicht so ganz klar? Das gleiche gilt für `generateCheckSaveNumber(). Warum wird der Rückgabewert, der *immer* `True` ist, mit einem ``if`` geprüft? Das macht doch gar keinen Sinn. Und der Name ist nicht wirklich gut gewählt.

Die Auflösung von `time.clock()` hängt vom Betriebssystem ab. Ebenso wie `time.time()` deshalb sollte man die nicht unbedacht zum Messen von Zeiten verwenden. Für Sachen wie hier, wo man längere Laufzeiten erwarten kann, würde ich das `datetime`-Modul verwenden.

Konstanten wie den Dateinamen sollte man idealerweise nur einmal im Quelltext haben. Wenn man den Wert einmal ändern möchte, muss man sonst aufpassen ihn an jeder Stelle zu ändern. Das ist eine beliebte Fehlerquelle.

Ich lande dann bei etwas in dieser Richtung (ungetestet):

Code: Alles auswählen

import time


def bereits_berechnet(filename):
    result = 2
    try:
        with open(filename) as lines:
            for result in lines:
                pass
        return int(result)
    except EnvironmentError:
        return result


def is_prime(zahl):
    for i in range(2, int(zahl**0.5) + 1):
        if zahl % i == 0:
            return False
    return True


def generate_check_save_number(start, ende, filename):
    with open(filename, 'w') as primes_file:    
        for i in range(start, ende + 1):
            if is_prime(i):
                primes_file.write(str(i) + '\n')
                primes_file.flush()


def main():
    primes_filename = 'primes.txt'
    start_time = time.clock()
    start = bereits_berechnet(primes_filename)
    if start > 2:
        print('Es wurde bereits bis {0} berechnet.'.format(start))
    ende = int(input('Bitte gib ein, wie weit du berechnen möchtest: '))
    generate_check_save_number(start, ende, primes_filename)
    end_time = time.clock()
    used_time = round((end_time - start_time) / 60, 4)
    print(
        'Super. Es wurden alles Zahlen bis {0} berechnet.'
        ' Dafür hat dein Computer {1} Minuten gebraucht.'.format(
            ende, used_time
        )
    )


if __name__ == '__main__':
    main()

Was mir daran allerdings noch nicht gefällt ist die fehlende Trennung vom erzeugen der Primzahlen und dem Speichern.

[nooby]

Vielen Dank für deine Verbesserung! Ich habe es mir leider angewöhnt immer kleinGross zuschreiben aber ich gebe mir mühe von jetzt an auf klein_gross um steigen.
Jetzt ist das Programm gleich schnell wie die alte Version.
Das ständige flush() mache ich, damit, falls jemand den PC abstellt, oder der PC abstürzt, die bereits berechneten sicher gespeichert sind. Wären sie dies auch ohne das?
1 bis 1mio mit flush(): 25 Sek
1 bis 1mio ohne flush(): 20 Sek
Man sieht also, das das flush() wirklich einen Einfluss auf die Performance hat.
Aber wie schon geschrieben, was passiert, wenn das Programm unterbrochen wird und nicht ständig ge-flush()-t wird?
Sind die Daten verloren?

//edit: Wegen der Trennung vom generieren und speichern der Zahlen, ich wusste nicht, wie ich das realisieren soll.
Ich kann ja schlecht zu erst alle Nummern generieren und in eine Liste packen. Bei grossen Zahlen gäbe das sicher Memory Probleme. Und mit

Code: Alles auswählen

primes = range(1, 100)

kann ich is_prime nicht aufrufen.
Die einzige Lösung, die ich sehe, ist, dass ich für das Generieren der Zahlen keine eigene Funktion mache, sondern das Generieren in die Main Funktion packe.

[BlackJack]

@nooby: Das `flush()`\en ist überflüssig wenn Du die Datei jedesmal neu öffnest und schliesst. Ich habe es bei meinen Änderungen ja drin gelassen, weil die Datei dort nur einmal zum Schreiben geöffnet wird. Dann braucht man es, wenn man sicher sein will, dass jede Zahl sofort rausgeschrieben wird.

Mit der bisherigen ineffizienten Vorgehensweise bekommt man wohl eher Laufzeitprobleme bevor man Speicherprobleme bekommt. Jedenfalls bei üblichen RAM-Grössen.

Die Trennung kann man machen in dem man eine Generatorfunktion schreibt, statt erst alles in einer Liste zu speichern. Das lässt sich mit dem was schon vorhanden ist und der `filter()`-Funktion in einer Zeile schreiben. Wieder ungetestet:

Code: Alles auswählen

from datetime import datetime as DateTime


def bereits_berechnet(filename):
    result = 2
    try:
        with open(filename) as lines:
            for result in lines:
                pass
        return int(result)
    except EnvironmentError:
        return result


def is_prime(zahl):
    for i in range(2, int(zahl**0.5) + 1):
        if zahl % i == 0:
            return False
    return True


def generate_primes(start, ende):
    return filter(is_prime, range(start, ende + 1))


def main():
    primes_filename = 'primes.txt'
    start = bereits_berechnet(primes_filename)
    if start > 2:
        print('Es wurde bereits bis {0} berechnet.'.format(start))
    ende = int(input('Bitte gib ein, wie weit du berechnen möchtest: '))
    start_time = DateTime.now()
    with open(primes_filename, 'a') as primes_file:
        for prime in generate_primes(start, ende):
            primes_file.write('{0}\n'.format(prime))
            primes_file.flush()
    used_time = DateTime.now() - start_time
    print(
        'Super. Es wurden alle Zahlen bis {0} geprüft.'
        ' Dafür hat dein Computer {1} gebraucht.'.format(ende, used_time)
    )


if __name__ == '__main__':
    main()

[nooby]

Da ich nicht wusste, ob ich nach einer Woche noch Mals in dieses Thema schreiben darf, mache ich es einfach. Wenn ich ein neues Thema eröffnen hätte müssen, Mods einfach melden.
Zu meinem Problem.
Ich habe mir da Multiprocessing Modul angeschaut und ausprobiert. Aber ich krieg es einfach nicht hin. Mein Programm läuft zwar, aber benötigt genau so viel Zeit wie vorher, ob wohl es doch mit multiprocessing.Pool alle 4 Kerne meines PCs nutzen sollte.
Habt ihr eine Ahnung, was ich falsch mache?
Vielen Dank für eure Hilfsbereitschaft.

Code: Alles auswählen

from datetime import datetime as DateTime
from multiprocessing import Pool

def bereits_berechnet(filename):
    result = 2
    try:
        with open(filename) as lines:
            for result in lines:
                pass
        return int(result)
    except EnvironmentError:
        return result


def is_prime(zahl):
    for i in range(2, int(zahl**0.5) + 1):
        if zahl % i == 0:
            return False
    return True


def generate_primes(start, ende):
    return filter(is_prime, range(start, ende + 1))

def generate_save_primes(start, ende, filename):
    primes = filter(is_prime, range(start, ende + 1))
    with open (filename, "a") as primes_file:
        for i in primes:
            primes_file.write(str(i) + "\n")
            primes_file.flush()

def main():
    primes_filename = "test.txt"
    start = bereits_berechnet(primes_filename)
    if start > 2:
        print('Es wurde bereits bis {0} berechnet.'.format(start))
    ende = int(input('Bitte gib ein, wie weit du berechnen möchtest: '))
    start_time = DateTime.now()
    pool = Pool()
    pool.apply_async(generate_save_primes(start, ende, primes_filename))
    pool.close()
    pool.join()
    used_time = DateTime.now() - start_time
    print(
        'Super. Es wurden alle Zahlen bis {0} geprüft.'
        ' Dafür hat dein Computer {1} gebraucht.'.format(ende, used_time)
    )
    
if __name__ == '__main__':
    main()

[BlackJack]

@nooby: Du verwendest die `apply_async()`-Methode falsch. Da muss die Funktion und die Argumente übergeben werden. Du übergibst da das *Ergebnis* des Funktions*aufrufs*. Das ist `None`, da die Funktion gar nichts zurück gibt. Und die Funktion wird natürlich in dem Prozess ausgeführt in dem Du sie aufrufst.

Aber selbst wenn Du den Aufruf von `apply_async()` richtig gemacht hättest, würde das nichts bringen, denn damit würde dann *eine* Funktion vom Pool auf *einem* Prozessor ausgeführt. Du müsstest aber die Bereiche von `start` bis `end` in kleinere Abschnitte und mehrere asynchrone Anwendungen der Funkion unterteilen, die dann auf verschiedenen Prozessoren berechnet werden können.

Desweiteren kannst Du das schreiben in die Datei nicht den verschiedenen Prozessen überlassen, denn die können ja unterschiedlich schnell mit ihrem Teilstück fertig sein, und dann stimmt die Reihenfolge nicht. Beziehungsweise gibt es auch Datenchaos in der Datei wenn mehrere Prozesse gleichzeitig in die Datei schreiben.

[Sirius3]

@nooby: der Fehler liegt in dieser Zeile:

Code: Alles auswählen

pool.apply_async(generate_save_primes(start, ende, primes_filename))

die Du auch so schreiben könntest:

Code: Alles auswählen

result=generate_save_primes(start, ende, primes_filename)
pool.apply_async(result)

Der Rückgabewert von generate_save_primes ist übrigens »None«.
Du mußt »apply_async« eine Funktion und nicht das Ergebnis eines Funktionsaufrufs übergeben:

Code: Alles auswählen

pool.apply_async(generate_save_primes, args=(start, ende, primes_filename))

Damit werden Deine Primzahlen aber immer noch nur in einem Process berechnet.

[nooby]

@Sirius3:
Ok, danke für deine Antwort. Jetzt ist es mit klar.

Wenn ich die Prozesse unterteilen muss, ist es dann besser auszulesen, wie viele Kerne die betreffende CPU hat, oder kann ich einfach in z.B. 8 Teile spliten und Pool verteilt es dann auf CPU Kerne?

Das Schreiben in eine Datei kann ich ja, wie du geschrieben hast nicht mehr direkt machen, da sonst die Reihenfolge nicht stimmt. Kann ich also alles in eine Liste packen und am Ende die Liste sortieren, oder packen das 4GB Arbeitsspeicher nicht?

[jerch]

@nooby:
Die Prozesserzeugung kannst Du wohl in den Skat drücken, d.h. wenn Dein Problem gut parallelisierbar ist, macht es zunächst keinen großen Unterschied, ob ein Kern genau eine große Aufgabe erhält oder viele kleine nacheinander abarbeitet. Wenn Du Dir allerdings hierüber Gedanken machst, solltest Du vllt. vorher die Sache algorithmisch optimieren. Dabei wirst Du feststellen, dass Primzahlberechnung nicht gut parallelsierbar ist, da folgende Berechnungen auf vorherige angewiesen sind.

[nooby]

Tut mir leid, ich kann dir nicht ganz folgen. Inwiefern ist jede Berechnung von der vorhergehenden Abhängig?
Ich versuche ja nicht, eine einzelne Zahl auf mehreren kernen zu prüfen, sondern parallel auf verschiedenen Kernen verschiedene Zahlen zu prüfen.

[BlackJack]

@jerch: Ich glaube im ersten Satz fehlt irgendwo ein ”nicht”.

@nooby: Dein Algorithmus ist auch, äh sagen wir mal, suboptimal. Normalerweise bauen die Tests nämlich auf den bereits gefundenen Primzahlen auf. Die Zeit in eine Sieb-Lösung wäre sicher besser investiert als Deinen ineffizienten Algorithmus zu parallelisieren.