Primzahlen / Threads

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
KayaStudent
User
Beiträge: 1
Registriert: Montag 24. August 2020, 16:25

Dienstag 25. August 2020, 20:45

Hallo bin neu in Python und habe die Aufgabe erhalten ein Programm zu schreiben, dass überprüfen soll ob eine Zahl eine Primzahl ist oder nicht. Ich bin so weit, dass ich den Satz von Wilson berechnen kann und diesen dann durch Mod kleiner machen kann (wegen großen Zahlen wie BSP: 9000004879). Nun ist meine Aufgabe:
Beispiel: Es soll geprüft werden, ob 17 eine Primzahl ist, d.h. es wird 16! mod
17 berechnet. Es sollen 4 Threads benutzt werden, also wird das Intervall 1..16
in 4 Teilintervalle aufgeteilt: 1..4, 5..8, 9..12, 13..16. Diese werden den 4
Worker-Threads per Parameter übergeben.
Wie die Intervalle gebildet werden hab ich auch schon und wie Threads funktionieren habe ich auch schon verstanden. Das einzige was ich nicht verstehe ist, wie man nun die Rechnung bzw das Intervall in die 4 Worker-Threads übergibt. Ich würde mich freuen wenn mir das einer erklären könnte.

Mit freundlichen Grüßen

Code: Alles auswählen

import threading
class PrimzahlThread(threading.Thread):
    def __init__(self, zahl):
        super().__init__()
        self.Zahl = zahl
    def run(self):
        summe = 1
        i = 1
        for i in range(1,self.Zahl):
            #summe = summe * i
            summe=((summe%self.Zahl)*(i%self.Zahl))%self.Zahl

        if summe%self.Zahl==self.Zahl-1:
            print(self.Zahl, "is PZ!")
        else:
            print(self.Zahl, "ist KEINE PZ!")

        t_threads=4
        intervall=[]

        for i in range(t_threads):
            intervall.append([int(i*(self.Zahl-1)/t_threads+1), int((i+1)*(self.Zahl-1)/t_threads)])
        print(intervall)


meine_threads = []
eingabe = input("> ")
while eingabe != "e":
    try:
        thread = PrimzahlThread(int(eingabe))
        meine_threads.append(thread)
        thread.start()
    except ValueError:
        print("Falsche Eingabe!")
    eingabe = input("> ")
for t in meine_threads:
    t.join()
Benutzeravatar
__blackjack__
User
Beiträge: 6810
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Dienstag 25. August 2020, 21:35

@KayaStudent: Mit CPython, also der Python-Implementierung die man von python.org bekommt, macht das gar keinen Sinn das auf Threads aufzuteilen, weil da kein Python-Code parallel läuft. Wenn man tatsächlich parallele Ausführung braucht, muss man Prozesse verwenden. Beispielsweise über das `concurrent.futures`-Modul. Das hat einen Pool mit dem man dann Aufgaben auch auf verschiedene Arbeitsprozesse verteilen kann.

Auch wenn Threads hier ein Irrweg sind: Eine von Thread abgeleitete Klasse die nur eine `__init__()` und die `run()` implementiert ist im Grunde nur eine übermässig kompliziert geschriebene Funktion. Man kann `Thread`-Objekten auch eine Funktion übergeben die dann nebenläufig ausgeführt wird.

Extrem verwirrend finde ich das da etwas `summe` heisst, was aber das Ergebnis von Multiplikation ist‽
long long ago; /* in a galaxy far far away */
Sirius3
User
Beiträge: 12747
Registriert: Sonntag 21. Oktober 2012, 17:20

Mittwoch 26. August 2020, 08:47

`meine_threads` macht als Name nur Sinn, wenn es auch `deine_threads` gibt. Das sind Threads zum berechnen von Primzahlen, also primenumber_threads.
Attribute schreibt man wie Variablennamen komplett klein: zahl.
Was soll das `i = 1`, wenn Du es gleich durch die for-Schleife überschreibst?
`i % zahl` ist immer i solange i < zahl ist. Das vereinfacht die Rechnung deutlich.
Das input ist doppelt im Code, das kann man durch eine while-True-Schleife verhindern:

Code: Alles auswählen

import threading

def is_prime(zahl):
    produkt = 1
    for i in range(1, zahl):
        produkt = (produkt  * i) % zahl

    if produkt == zahl - 1:
        print(zahl, "is PZ!")
    else:
        print(zahl, "ist KEINE PZ!")

prime_threads = []
while True:
    eingabe = input("> ")
    if eingabe == "e":
        break
    try:
        thread = threading.Thread(target=is_prime, args=(int(eingabe),))
        prime_threads.append(thread)
        thread.start()
    except ValueError:
        print("Falsche Eingabe!")
for thread in prime_threads:
    thread.join()
Was die Intervallberechnung betrifft:
Was soll das t_ bei t_threads? Sollte das nicht number_of_threads heißen?
Für Ganzzahldivision gibt es //.

Code: Alles auswählen

number_of_threads = 4
intervalls = []

for i in range(number_of_threads):
    intervalls.append([i * (zahl-1) // number_of_threads+1, (i+1) * (zahl-1) // number_of_threads])
print(intervalls)
Jetzt mußt Du noch für jedes Intervall einen Thread starten und auf das Ergebnis warten. Das Rückgeben von Ergebnissen ist dabei das komplizierteste.
Deshalb benutz man dafür einen Threadpool, wie z.B. concurrent.futures.ThreadPoolExecutor der eine map-Methode hat, wo das Starten von Threads und das Übergeben von Parametern automatisch passiert. Und das kann man auch einfach durch concurrent.futures.ProcessPoolExecutor ersetzen, falls man tatsächlich Parallelität möchte.
Antworten