Multiprocessing

[Xethy]

Hi, ich verstehe nicht so ganz was ich bei multiprocessing falsch mache mein code angehängt wird irgendwie gar nicht ausgeführt.

Mir ist klar das in dem folgenden code einige dinge nicht schön umgesetzt sind.
Es handelt sich um die idee möglichst zeiteffizient primzahlen zu berechnen. Dafür soll später noch verbesserungen mit dem dictonary vorgenommen werden wofür es übergeben werden muss.

Ich bräuchte tipps für folgende dinge

1) Warum lauft das multiprocessing gegen eine wand. Bei mir endet das programm einfach nicht.

2) ich habe für multiprovessing ein 8 kern rechner angenommen, ziel war nur eine cpu nicht zu belasten um zumindest noch einen taskmanager aufzubekommen um die instanzen abschießen zu können wenn der prozess einfriert.
Deswegen rechne ich erst die primzahlen aus die kleiner sind als die wurzel der gegebenen größten zahl. Diese gebe ich in ein dictonary (für geschwindigkeit beim aufruf) und übergebe das dict und dann am subprozesse. Dannach rechne lasse ich die zahlen in einer liste weil ich Ich teile ich die verbleibenden recheneinheiten in 7 teile auf ... Sehr umständlich. Hier wären einige tipps hilfreich.
Optional- ich würde gerne die cpu anzahl variabel machen. Ich sehe aber keine möglichkeit dazu? Gibts hier keine schöne Lösung? Ich wollte eine For schleife nutzen habe aber gelesen dass wenn die einzelnen prozesse die mit for gestartet werden auch einzeln durchlaufen befor ein neuer prozess gestartet wird (doof für mp wo man je parallelität möchte) und dann auf die beendigung des vorherigen prozesses gewartet wird. Ebenso wurde empfohlen nicht join zu verwenden.

3) ich würde gerne ordnung in die rückgabe von den zurückgegebenen listen einführen und sie der reihe nach ausgeben lassen. Es muss nicht das hauptprogramm machen. Wenn es in reihnfolge also niedrigere primzahlen zuerst dann höhere primzahlen ausgegeben wird ist mir alles recht

Code:


import math
import threading
import time
import multiprocessing as mp
def is_int(string):
try:
if(int(string)==float(string)):
return True
else:
return False
except ValueError :
return False

def primtest(Pnum, nfrom, nto, lenght1,dict_num):
prim = True
k = 3
num_list = []
inputsqrt = math.sqrt(int(nto))
for n in range(nfrom , nto, 2) :
y = math.sqrt(n)
while k <= y :
if(n%k == 0):
prim = False
k = k + 2
k = 3
if prim == True :
num_list.append(n)
else:
prim = True
return(num_list, Pnum)

repeat = True
while (repeat):
input1 = input("Please give whole number for finding primes to")
input2 = input("f = program end")
if input2 == "f" :
input2 = False
if(is_int(input1)):
prim = True
k = 3
lenght1 = 0
dict_num = {"0" : 2}
inputsqrt = math.sqrt(int(input1))
for n in range(3 , int(inputsqrt), 2) :
y = math.sqrt(n)
while k <= y :
if(n%k == 0):
prim = False
k = k + 2
k = 3
if prim == True :
lenght1 = lenght1 +1
dict_num[n] = lenght1
else:
prim = True
print(*dict_num)
s = int(inputsqrt)
e = int(input1)
if(s%2 == 0):
s = s + 1
if(e%2 == 0):
e = e - 1
calc = e - s
work = int((calc / 7)+1)
if(e%2 != 0):
work = work - 1
p1nfrom = s
p1nto = s + work
p2nfrom = p1nto + 2
p2nto = s + work*2
p3nfrom = p2nto + 2
p3nto = s + work*3
p4nfrom = p3nto + 2
p4nto = s + work*4
p5nfrom = p4nto + 2
p5nto = s + work*5
p6nfrom = p5nto + 2
p6nto = s + work*6
pnfrom = p6nto + 2
pnto = e
p0 = threading. Thread(target=primtest,args=(0, pnfrom, pnto, lenght1, dict_num))
p0.start
if __name__ == '__main__':
p1 = mp.Process(target=primtest, args=(1, p1nfrom, p1nto, lenght1, dict_num))
p2 = mp.Process(target=primtest, args=(2, p2nfrom, p2nto, lenght1, dict_num))
p3 = mp.Process(target=primtest, args=(3, p3nfrom, p3nto, lenght1, dict_num))
p4 = mp.Process(target=primtest, args=(4, p4nfrom, p4nto, lenght1, dict_num))
p5 = mp.Process(target=primtest, args=(5, p5nfrom, p5nto, lenght1, dict_num))
p6 = mp.Process(target=primtest, args=(6, p6nfrom, p6nto, lenght1, dict_num))
p1.start()
p2.start()
p3.start()
p4.start()
p5.start()
p6.start()
print(*p1.num_list)
else:
print("Not a whole number")

[Sirius3]

Mal klammerst Du den Ausdruck bei if und mal nicht? Da die Klammern überflüssig sind, lass sie immer weg. Wenn die if-Abfrage als Ergebnis doch nur True oder False liefert, kann man den Vergleichsausdruck gleich als Rückgabewert benutzen.

Code: Alles auswählen

def is_int(string):
    try:
        return int(string) == float(string)
    except ValueError:
        return False

Wenn Du nur prüfen willst, ob ein String in ein Int umwandelbar ist, dann ist der float-Aufruf überflüssig.

Code: Alles auswählen

def is_int(string):
    try:
        int(string)
        return True
    except ValueError:
        return False

Variablennamen schreibt man wie Funktionen komplett klein und bentzt keine kryptischen Abkürzungen. Was soll Pnum sein? Das braucht die Funktion doch gar nicht. `length1` hat eine unsinnig 1 am Namen; die Variable wird ebenso nicht benutzt. `dict_num` hat einen Typ im Namen, was an sich auch schlecht ist, weil sich der Typ öfter mal ändert und dann müßte man überall die Variable umbenennen. Variablen setzt man direkt bevor man sie benutzt, und setzt sie nicht zurück, nachdem man sie benutzt hat. `inputsqrt` wird gar nicht benutzt. Die while-Schleife sollte eine for-Schleife sein. Wenn prime einmal auf False gesetzt ist, dann kannst Du die Schleife abbrechen.
Auf True vergleicht man nicht explizit, weil was soll aus so einem Vergleich schon rauskommen, außer wieder True oder False?
Das ganze könnte also so aussehen:

Code: Alles auswählen

def find_primes_in_range(number_from, number_to):
    primes = []
    for n in range(number_from, number_to, 2):
        is_prime = True
        for k in range(3, int(n ** 0.5), 2):
            if n % k == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(n)
    return primes

Der Code hat natürlich noch das Problem, dass falls number_from gerade ist, gar keine Primzahlen gefunden werden.

Code: Alles auswählen

def find_primes_in_range(number_from, number_to):
    if number_from % 2 == 0:
        number_from += 1
    primes = []
    for n in range(number_from, number_to, 2):
        is_prime = True
        for k in range(3, int(n ** 0.5), 2):
            if n % k == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(n)
    return primes

Das Hauptprogramm sollte in einer Funktion `main` stehen, wenn man multiprocessing benutzt, dann muß das sogar so sein, weil Du sonst in eine Endlosschleife läufst, und das Programm nicht reagiert.
`repeat` ist immer True, also hast Du eigentlich eine while-True Schleife.
Für input1 und input2 solltest Du bessere Namen finden. input2 wird nie benutzt.
Die Schleife ist dann auch etwas lang, und sollte dringend in mehrere Funktionen aufgeteilt werden.

Code: Alles auswählen

def main():
    while True:
        user_input = input("Please give whole number for finding primes to (f= program end)")
        if user_input == "f":
            break
        if is_int(user_input):
            calculate_primes(int(user_input))

if __name__ == "__main__":
    main()

Dann hast Du nochmal den selben Code um Primzahlen auszurechnen. Das was Du da mit dict_num machst, ist für mich völlig unverständlich. Sollen da nun Primzahlen drin stehen, aber was soll dann "0"? Und was bedeutet der Wert zu den Schlüsseln?
Das was dann kommt, ist auch unverständlich. Wenn man anfängt, Variablen durchzunummerieren, dann möchte man eigentlich Listen benutzen. Du solltest Dich entscheiden, ob Du Threads oder Multiprocessing benutzt. Den Thread startest Du auch gar nicht.
Am besten benutzt man einen multiprocessing-Pool oder gleich concurrent-futures.

Code: Alles auswählen

def generate_parameter_ranges(start, stop, number_of_processes):
    step = (stop - start) / number_of_processes
    return [
        (round(start + i * step), round(start + (i + 1) * step))
        for i in range(number_of_processes)
    ]

def calculate_primes(max_number, number_of_processes=7):
    sqrt_number = int(max_number ** 0.5) + 1
    primes = find_primes_in_range(3, sqrt_number)
    parameters = generate_parameter_ranges(sqrt_number, max_number, number_of_processes)
    with mp.Pool(number_of_processes) as pool:
        print(pool.starmap(find_primes_in_range, parameters))

Wenn man aber schnell Primzahlen berechnen will, dann benutzt man andere Algorithmen, wie z.B. ein Sieb.

Ach ja, noch ein Wort zu Deinen Befürchtungen: Ein Rechner besteht verschiedenen Resourcen, CPU, Speicher und Netzwerk/Festplatten-Input-Output und interne Verwaltungsstrukturen. Speicher kann nur einmal benutzt werden, also wenn viele Prozesse viel Speicher verbrauchen, dann ist irgendwann einmal Schluß und Processe brechen ab. Wenn zu viel IO benutzt wird, dann kann der Rechner sehr langsam und unbenutzbar werden. Man kann aber auch das Betriebssystem überfordern, in dem man z.B. ständig neue Prozesse erzeugt. Dann kann alles hängen.
Wenn aber nur viele Prozesse sehr viel CPU-Zeit verbrauchen, dann wird alles zwar etwas langsamer, aber meist kann man noch gut arbeiten. Also ob Du jetzt mit 7, 8 und 34 Prozessen Primzahlen berechnest, Dein Rechner wird weiter so reagieren, so dass Du interaktiv ohne Probleme die Prozesse auch wieder abschießen kannst.

[noisefloor]

Hallo,

halb unabhängig von der Fragestellung: wenn es um Geschwindigkeit geht gibt es (für Python) schnellere Weg als Multiprocessing. Ich habe dazu vor ein paar Jahren mal einen Blogartikel geschreiben: https://noisefloor-net.blogspot.com/201 ... -oder.html. Das gilt IMHO heute weitestgehend immer noch so, der Numba JIT Compiler ist inzwischen auch separat (ohne Anaconda) installierbar.

Bei wirklich großen Primzahlen braucht man aber in erster Instanz bessere Algorithmen als die hier genutzten oder genannten, sonst dauert das alles lange. Primzahlenforschung gibt's schon lange, entsprechend findet man dazu auch Literatur zu.

Gruß, noisefloor

[Xethy]

Hi, Noisefloor und Sirius3

Ersteinmal Danke, dass ihr tatkäftig geholfen habt, obwohl der Code oben nicht wirklich eine Meisterleistung ist;

zu meiner Verteidigung, ich hab ihn auch nur auf meinem Handy geschrieben und er war nur einem Code/Problem nachempfunden, welches ich lösen wollte. Dennoch nicht das schönste Stückchen code das ich produziert habe, also sorry dafür.

Hier Schreibe ich erstmal kurz etwas zu den code und gedanken von Sirius; weiter unten werde ich dann auf Noisefloor bezug nehmen.

Lieber Sirius, danke für ein paar worte wegen meiner Ängste/Ideen.
Das war sehr hilfreich;

Ich hab deine grundsätzlichen Hilfen beachtet, aber auch versucht nichts direkt von dir zu übernehmen, da ich auch etwas beim Programmieren lernen möchte.

Auch; Grundsätzlich es macht einfach spaß, den code effizienter zu machen und noch etwas mehr zeit rauszukitzeln und das dann auch später zu sehen.

Für mich war erstmal wichtig einen code geschrieben zu haben, welcher Primzahlen bis zu einer zahl berechnet, nicht ein code, welcher eine bestimmte Zahl darauf testet, ob sie eine primzahl ist.
Natürlich, würde eine zahl die gerade ist dem code probleme bereiten, deswegen ist alles so gestellt, dass keine gerade zahl generiert wird.

Zu Sieben kenne ich mich nicht aus, Aber ich hab 1, 2 ideen wie ich ein einfaches sieb (selbst ausgedachtes sieb) in meinen aktuellen code implementieren kann, ob das sinnvoll ist, ist eine andere Frage.

Wie auch immer, danke für deine Hilfe, wenn dich der Code interessiert, den ich geschrieben habe, er findet sich weiter unten.

Hallo Lieber Noisefloor, sehr interesanter Blog, und coole Möglichkeiten. Ich muss mich noch etwas weiter einlesen wie ich einen besseren compiler verwenden kann.

Hier mal ein Einblick in meinen aktuellen (endlich funktionierenden) code. Ich hoffe ich habe BBcode richtig verstanden und das sieht nicht so doof aus wie mein erster Versuch.

Dieser Code findet und berechnet alle primzahlen bis 4.000.000 auf meinem computer in ca 3 sekunden, bis 100.000.000 in ca 170 sekunden. Dennoch sehe ich noch zwei punkte wo optimierungspotential ist. Vieleicht, mache ich mcih dann auch an siebe. Wie auch immer mit den genierten primzahlen kann man dann bis zum quadrat der größten gefunden primzahl mit jeder gefundenen Primzahl testen; wie schnell oder langsam das wäre weiß ich aber nicht. Die zahlen die in deinem code betrachtet werden sind teilweise größer als das quadrat von 100.000.000. Mit einigen wenigen zahlen kann mein code da nicht mithalten, gänge es jedoch ein paar hundert, naja vermultich eher sogar tausend zahlen in dem zahlenbereich, sähe die Situation vieleicht wieder anders aus. (Nicht das jemand so lange rechnen möchte) Mein Code arbeit damit, dass er wirklich nur durch primzahlen und nicht durch alle ungeraden zahlen teilt; dafür wird das dict erstellt und übergeben. Dies erlaubt sobald das dictonary erstellt ist, das deutlich schnellere testen von Zahlen.

Code: Alles auswählen

#imports for Timing, Squareroots and  Multiprocessing
import time
import math
import multiprocessing as mp
dict_num = {0: 2}
#The dictonary was chosen for fast access of the primes that are smaller than the squarroot of the biggest checked number.
lenght1 = 0
#Needed to produce the keys for the dictonary. keeps track of the current lenght of the dictonary
prim = True
#Flag to check if prime or not to add to dict, or list
remember = 2
#remember is the prime that is smaller than the squareroot of the number which needs to be checked
#remember needs to be 2 for startup, if 3, 3 will not be checked.
index = 0
#pointer in the dictonary to find the prime that is smaller than the squareroot of the number to be checked
l = 1
#used to prevent a printing of numlist if not multiprocessing.
def main(nfrom, nto, dict_num, index, lenght1, inputsqrt):
    num_list = []
    k = 2
    #k is needed as condition for while loop. define small k needs to be 1 smaller than the number that shall be checked first - 3.
    z = 0
    #z is needed to find the next prime in the dictionary to be used as divisor. Also used as pointer in the dictonary to find the prime that is smaller than the squareroot of the number to be checked
    prim = True
    #Flag to check if prime or not to add to dict, or list 
    y = 2
    #y is usually the squareroot of the next tested number. In this case a start number was chosen that doesnt generate hickups.
    for n in range(nfrom, nto, 2): #Even numbers are not checked. There are no even primes besides 2. 2 was added to dict by hand.
        try: # This try and except block is needed in the main programm for the following reason: in multiprocessing the a def: try except function did not behave as intended for some reason.
            remember = dict_num[(index)]
            y = math.sqrt(n + 2)
            q = dict_num[(index + 1)]
            #is the number next to the index bigger than the prime in the next loop?
            while(q <= y):
                if q == dict_num[(index + 1)]:
                    remember = dict_num[(index + 1)]
                    index = index + 1
                    try:
                        q = dict_num[(index + 1)]
                    except KeyError:
                        pass
                else:
                    q = y + 1
            q = remember
        except KeyError:
            pass
        while k < remember and prim:
            z = z + 1
            k = dict_num[z]
            if n % k == 0:
                prim = False 
        #reseting k for next loop. otherwise k > remember, previous while condition wont work.
        k = 2
        #find the squareroot of n for next loop.
        y = math.sqrt(n + 2)
        #reseting z for next loop. Z cannot be used as subsitute for index.
        z = 0
        #is there a dictonary entry bigger than the indexed one? Is there even the number index?
        if prim == True:
            if inputsqrt < n:
                num_list.append(n)
            else:
                lenght1 = lenght1 + 1
                dict_num[lenght1] = n
        prim = True
    if l == 1:
        print(num_list) 
def is_int(string):
    try:
        int(string)
        if(int(string) == float(string)):
            return True
        else:
            return False
    except ValueError:
        return False
if __name__ == '__main__':
    #Input = problem?
    input1 = input("Make a list of of all primes to (please give a whole number): ")
    inputsqrt = int(math.sqrt(int(input1)))
    #inputsqrt is needed to differ primes that are not divisors and primes that are divisors of any needed number. 
    if is_int(input1) == True :
        start = time.time()
        #starting timer
        s = int(round(inputsqrt+0.5))
        pform = 3
        pto = s
        l = 0
        main(pform, pto, dict_num, index, lenght1, inputsqrt)
        l = 1
        print(f'{dict_num}')
        u = 8 #change to the number of processes that are needed.
        e = int(input1)
        if s%2 == 0 :
            s = s + 1
        if e%2 == 0 :
            e = e - 1
        calc = e - s
        work = int(round((calc /(u)) + 0,5))
        if work%2 != 0 :
            work = work - 1
        u = u + 1
        pro_list = []
        pro = {}
        for i in range(1, u):
            pfrom = s + (work*(i-1))
            pto = s + work*i
            if i == (u - 1) :
                pto = e  
            pro[i] = mp.Process(target=main, args=(pfrom, pto, dict_num, index, lenght1, inputsqrt))
            pro_list.append(pro[i])
            pro[i].start()
        for i in range(1, u): #A second loop is needed otherwise the main process will wait for one multiprocessing task to end just to start the next one.
            pro[i].join()
    else:
        print("Invalid input")
    end = time.time()
    print(end-start)

[Sirius3]

Hallo Xethy,

in paar Leerzeilen würden die Lesbarkeit des Codes stark erhöhen. Um ein Programm gut verstehen zu können, braucht es aussagekräftige Variablennamen und Funktionen. Eine Funktion `main`, die gar nicht die Startfunktion ist, ist da sogar kontraproduktiv.
Warum `dict_num` oder `length1` schlecht sind, hatte ich ja schon eingesprochen. Hinzu kommt jetzt auch noch `l` was in dreifacher Hinsicht schlecht ist, weil nichts-sagend, einbuchstabig, und noch leicht mit 1 oder I zu verwechseln.
Globale Variablen darf es nicht geben. Du hast gleich eine ganze Reihe davon.
Variablen definiert man erst, wenn man sie braucht. Dann würde auch auffallen, dass manche, wie `prim` oder `remember` gar nicht benutzt werden. `dict_num` wird ganze 84 Zeilen vor der Verwendung definiert.
Statt Variablen mit langen Kommentaren zu erklären, ist es besser, vernünftige Namen zu benutzen.
Wie man is_int besser schreibt und wie man multiprocessing einsetzen sollte, das hatte ich alles ja schon geschrieben, muß ich also hier nicht wiederholen.

Man mißbraucht keine Wörterbücher als Listen. Die Schlüssel all Deiner Wörterbücher sind aufsteigende Zahlen, effektiv eine Liste, was auch den ganzen Code deutlich einfacher machen würde!
Du treibst das ja noch auf die Spitze, in dem Du `pro` und `pro_list` gleichzeitig füllst, die Liste aber dann gar nicht verwendest.

Um all das zu illustrieren, nehmen wird den Codeteil:

Code: Alles auswählen

        u = 8 #change to the number of processes that are needed.
        e = int(input1)
        if s%2 == 0 :
            s = s + 1
        if e%2 == 0 :
            e = e - 1
        calc = e - s
        work = int(round((calc /(u)) + 0,5))
        if work%2 != 0 :
            work = work - 1
        u = u + 1
        pro_list = []
        pro = {}
        for i in range(1, u):
            pfrom = s + (work*(i-1))
            pto = s + work*i
            if i == (u - 1) :
                pto = e  
            pro[i] = mp.Process(target=main, args=(pfrom, pto, dict_num, index, lenght1, inputsqrt))
            pro_list.append(pro[i])
            pro[i].start()
        for i in range(1, u): #A second loop is needed otherwise the main process will wait for one multiprocessing task to end just to start the next one.
            pro[i].join()

Der Code ist sehr schwer zu verstehen, weil alle Variablen nur einen Buchstaben haben, oder sonst irgendwie generisch benannt sind.
Manche Variablen ändern auch noch ihre Bedeutung, so dass die Anfänglich herausgefundene Benutzung am Ende gar nicht mehr stimmt.
Im ersten Schritt habe ich alle Variablen so umbenannt, dass sie aussagekräftig sind. Auch wenn sie etwas länger sind, so muß man präzise die Verwendung unterscheiden können, also ist das jetzt die generelle Startnummer, oder die für einen Prozess?

Code: Alles auswählen

        number_of_processes = 8  # change to the number of processes that are needed.
        end_number = int(end_number_input)
        if start_number % 2 == 0:
            start_number += 1
        if end_number % 2 == 0:
            end_number -= 1
        amount_of_numbers_to_be_calculated_less_one = end_number - start_number
        amount_of_numbers_per_task = int(round((amount_of_numbers_to_be_calculated_less_one / number_of_processes) + 0, 5)) # round on 5 digits? why?
        if amount_of_numbers_per_task % 2 != 0 :
            amount_of_numbers_per_task -= 1
        one_more_than_number_of_processes = number_of_processes + 1
        processes = {}
        for i in range(1, one_more_than_number_of_processes):
            start_number_for_task = start_number + work * (i - 1)
            end_number_for_task = start_number + work * i
            if i == (one_more_than_number_of_processes - 1):
                end_number_for_task = end_number  
            processes[i] = mp.Process(target=print_primes, args=(start_number_for_task, end_number_for_task, dict_num, index, lenght1, inputsqrt))
            processes[i].start()
        for i in range(1, one_more_than_number_of_processes):
            processes[i].join()

Es fällt auf, dass die Variable one_more_than_number_of_processes ziemlich komisch benannt ist, was daran liegt, dass die Verwendung komisch ist. Ausdrücke wie one_more_than_number_of_processes - 1 zeigen dann auch, dass hier was komplizierter geschrieben ist, als es sein müßte.
Sehr viele Zeilen Code beschäftigen sich damit, dass die Funktion `print_primes` (ehemals `main`) nur unter sehr bestimmten Bedingungen richtig funktioniert. Könnte bei der Funktion die Start- und Endzahl auch gerade sein, würde der Code deutlich schlanker:

Code: Alles auswählen

        number_of_processes = 8  # change to the number of processes that are needed.
        end_number = int(end_number_input)
        amount_of_numbers_to_be_calculated = end_number - start_number + 1
        amount_of_numbers_per_task = round(amount_of_numbers_to_be_calculated / number_of_processes)
        processes = {}
        for i in range(1, number_of_processes + 1):
            start_number_for_task = start_number + work * (i - 1)
            end_number_for_task = start_number_for_task + work
            if i == number_of_processes:
                end_number_for_task = end_number  
            processes[i] = mp.Process(target=print_primes, args=(start_number_for_task, end_number_for_task, dict_num, index, lenght1, inputsqrt))
            processes[i].start()
        for i in range(1, number_of_processes + 1):
            processes[i].join()

Jetzt zu der Geschichte mit den Listen. Eine Liste hat den Vorteil, dass man den Index nicht selbst verwalten muß. Man kann einfach über Listen iterieren und weiß auch, dass es sich nur um eine Ansammlung von Objekten handelt, und ein Schlüssel keine Bedeutung hat.

Code: Alles auswählen

        number_of_processes = 8  # change to the number of processes that are needed.
        end_number = int(end_number_input)
        amount_of_numbers_to_be_calculated = end_number - start_number + 1
        amount_of_numbers_per_task = round(amount_of_numbers_to_be_calculated / number_of_processes)
        processes = []
        for i in range(number_of_processes):
            start_number_for_task = start_number + work * i
            end_number_for_task = start_number_for_task + work
            if i == number_of_processes - 1:
                end_number_for_task = end_number  
            processe = mp.Process(target=main, args=(start_number_for_task, end_number_for_task, dict_num, index, lenght1, inputsqrt))
            processe.start()
            processes.append(process)
        for process in processes:
            process.join()

[__blackjack__]

@Xethy: Anmerkungen zum Quelltext (ungeachtet der bisherigen Beiträge, da sind also sicher schon Sachen dabei die bereits gesagt wurden):

Kommentare sollen dem Leser einen Mehrwert über den Code geben. Faustregel: Kommentare beschreiben nicht *was* der Code macht, denn das steht da bereits als Code, sondern warum er das macht. Sofern das nicht offensichtlich ist. Offensichtlich ist in aller Regel auch was in der Dokumentation von Python und den verwendeten Bibliotheken steht. Also beispielsweise vor den Importen noch mal zu kommentieren das und was da importiert wird macht keinen Sinn.

Kommentare stehen vor dem Code den sie kommentieren. Das anders herum zu machen ist schwer zu lesen für Leute die Python-Quelltexte gewohnt sind. Und dann wechselt das auch noch an einigen Stellen.

Auf Modulebene sollte nur Code stehen der Konstanten, Funktionen, und Klassen definiert. Das Hauptprogramm steht üblicherweise in einer Funktion die `main()` heisst. Die jetzige `main()`-Funktion ist nicht die Hauptfunktion.

Die ursprünglichen `prim` und `remember` von der Modulebene werden nirgends verwendet.

`l` ist ein verdammt schlechter Name für eine globale Variable die entscheidet ob eine Funktion eine Ausgabe macht oder nicht. Zudem sollte das keine globale Variable sein. Funktionen und Methoden bekommen alles was sie ausser Konstanten benötigen, als Argument(e) übergeben.

Die Werte 1 und 0 sollten nicht als Wahrheitswerte missbraucht werden. Wenn man eine Zuweisung von `True` sieht, weiss man da sind `True` und `False` möglich. Bei einer Zuwesiung von 1 könnte auch 23, 42, oder sonstwas ein sinnvoller Wert sein und man muss erst schauen wo das überall verwendet wird, um zu erkennen, dass es wahrscheinlich ein Flag ist das nur 0 und 1 als sinnvolle Zahlen nimmt.

Man macht keine Vergleiche mit literalen Wahrheitswerten. Bei dem Vergleich kommt doch nur wieder ein Wahrheitswert bei heraus. Entweder der, den man sowieso schon hatte; dann kann man den auch gleich nehmen. Oder das Gegenteil davon; dafür gibt es ``not``.

Das `length1` im Hauptprogramm ist und bleibt immer 0, das macht also nichts sinnvolles. Also wird an der Stelle eine feste 0 an die ehemalige `main()`-Funktion übergeben. So eine Übergabe kann man sich sparen. Das gleiche gilt für `index`

`inputsqrt` wird zu früh berechnet. Vor dem Test ob die Eingabe in eine ganze Zahl umgewandelt werden kann, wird hier die Eingabe in eine ganze Zahl umgewandelt, wodurch das Programm an der Stelle mit einer Ausnahme abbrechen würde und so nie das ``else`` mit der Ausgabe „Invalid input“ erreicht werden kann.

Bei `is_int()` ist das innere ``if``/``else`` sinnfrei, denn das wird niemals erreicht wenn `string` nicht in eine ganze Zahl umwandelbar ist, weil dann vorher eine Ausnahme ausgelöst wird.

`pform` sollte wohl eher `pfrom` heissen. Der Wert wird aber nur ein einziges mal verwendet, also könnte man den dort auch gleich einsetzen.

Bei der Berechnung von `s` ist das `round()` überflüssig bis falsch, denn das rundet wahrscheinlich nicht wie Du das erwartest.

Die erste Zuweisung an `pto` kann man sich sparen, denn das wird nur an einer Stelle verwendet und da kann man auch einfach `s` hinschreiben.

`time.time()` ist für Zeitmessungen nur bedingt geeignet. Dafür nimmt man `time.monotonic()`. Die `start`-Zeit wird an der falschen Stelle ermittelt. Oder die `end`-Zeit. Denn so wie es jetzt dort steht läuft der Code in eine Ausnahme wenn die Eingabe keine ganze Zahl war, weil dann zwar `start` nicht definiert wird, aber am Schluss versucht wird das undefinierte Start von `end` abzuziehen.

`dict_num` ist ein schlechter Name. Grunddatentypen haben in Namen nichts zu suchen. Den Typ ändert man gerne mal im Laufe der Programmentwicklung und dann hat man entweder falsche, irreführende Namen oder unnötig Arbeit die betroffenen Namen zu ändern. Der Name sagt auch nicht was der Wert bedeutet. Das sind die gefundenen Primzahlen.

Das sollte auch kein Wörterbuch sein. Wörterbücher mit aufsteigenden ganzen Zahlen als Schlüssel sind kompliziert geschriebene Listen.

`u` ist wieder ein schlechter Name. Wenn das `process_count` heissen würde, wüsste man überall wo der Wert verwendet wird was der bedeutet und es würde vielleicht auch eher auffallen wie Scheisse ungünstig das ist diesen Wert um 1 zu erhöhen, womit er ja falsch ist, und dann an verschiedenen Stellen immer den Wert selbst oder einen Wert der davon abhängt, wieder um 1 nach oben oder unten zu korrigieren.

In ``work = int(round((calc /(u)) + 0,5))`` ist ein netter Fehler versteckt. Man könnte ja sagen das addieren von 0 kann man sich auch sparen. Wenn man das überflüssige bis fehlerhafte `round()` da raus nimmt, fällt der Fehler auf, denn dann bekommt man einen ``TypeError: int() can't convert non-string with explicit base``. Das muss 0.5 heissen, nicht 0,5.

`pro_list` wird befüllt aber nirgends verwendet. Sollte es aber. Denn `pro` ist unsinnig. Beide Namen sind indiskutabel.

Das `work` um eins verringert werden kann ist ziemlich sicher falsch. Das wird davon aufgefangen, dass für den letzten Prozess `pto` gesondert behandelt wird, also macht es mindestens mal keinen Sinn.

`pto` wird etwas zu aufwändig berechnet. Den Wert kann man durch eine simple Addition aus `pfrom` berechnen. Letztlich kann man auch einfach `range()` schon dazu verwenden `pfrom`-Werte auszuspucken.

Der Kommentar bei der Schleife wo `join()` auf den Prozessen aufgerufen wird ist inhaltlich falsch.

For einer Schleife Variablen zu initialisieren die man am Ende jeden Schleifendurchlaufs wieder auf diese Werte ”resettet” ist unnötige Arbeit und fehleranfällig. Das macht man *einmal* am Anfang jeden Schleifendurchlaufs.

Der Wert von der Zuweisung ``y = 2`` wird nirgends verwendet. Ebensowenig der Wert der `y` vor ``if prim:`` zugeordnet wird. ``q = remember`` macht aus dem gleichen Grund keinen Sinn.

Das ``else: q = y + 1`` ist ein kryptisch ausgedrücktes ``break``. Der ``else``-Zweig kann nur eintreten wenn im vorherigen Schleifendurchlauf im ``if``-Zweig die Ausnahme aufgetreten ist. Wo man *dort* dann schon die Schleife hätte abbrechen können. Womit das ``else`` überflüssig wird. Dann ist aber die Bedingung im ``if`` *immer* wahr und das ``if`` somit überflüssig. Letztlich ist das gesamte Konstrukt ziemlich überflüssig, weil man den Test ob die Primzahl gegen die man testet grösser als die Wurzel der zu testenden Zahl ist, auch in die Schleife einbauen kann in der man auf Teilbarkeit testet. Allerdings muss man da wieder testen welche ”Art” von Aufruf das ist. Ich habe es einfach mal komplett rausgeworfen — das Programm weiter unten ist auch so schneller als die ursprüngliche Version.

Die ``while``-Schleife mit dem ``and prim`` in der Bedingung würde man besser einfach mit ``break`` abbrechen wenn die Bedingung eintritt. Dann kann man auch ``else`` zu der Schleife verwenden und sich `prim` komplett sparen. Das mit dem manuell raufgezählten `z` das als Index in die Primzahlen genutzt wird ist auch umständlich. Das sollte wohl eher eine Schleife über die Primzahlen sein. Dann kann man sich auch den `k`-Wert sparen der garantiert so klein ist, dass die ``while``-Schleife betreten wird.

Die Entscheidung zu welcher Liste die Primzahlen hinzugefügt wird ist komisch, weil die letztlich davon abhängt ob das der erste Aufruf im gleichen Prozess oder der Aufruf aus einem der anderen Prozesse ist. Das ist eine sehr eigenartige Asymmetrie. Funktionen sollten halt keine übergebenen Datenstrukturen befüllen, sondern Rückgabewerte liefern.

Zwischenstand:

Code: Alles auswählen

#!/usr/bin/env python3
import math
import multiprocessing as mp
import time


def is_int(string):
    try:
        int(string)
    except ValueError:
        return False
    else:
        return True


def calculate_primes(
    start, end, known_prime_numbers=None, print_numbers=False
):
    if start % 2 == 0:
        start += 1

    if known_prime_numbers is None:
        known_prime_numbers = new_prime_numbers = [2]
    else:
        new_prime_numbers = []

    for candidate in range(start, end, 2):
        for prime_number in known_prime_numbers:
            if candidate % prime_number == 0:
                break
        else:
            new_prime_numbers.append(candidate)
    #
    # TODO This flag should not exist.  A function to calculate prime numbers
    #      has no business in printing them.  That's the job of the caller.
    # 
    if print_numbers:
        print(new_prime_numbers)

    return new_prime_numbers


def main():
    answer = input(
        "Make a list of of all primes to (please give a whole number): "
    )
    if is_int(answer):
        start_time = time.monotonic()
        end = int(answer)
        start = int(int(math.sqrt(end)) + 0.5)
        prime_numbers = calculate_primes(3, start)
        print(prime_numbers)

        process_count = 8  # Change to the number of processes that are needed.
        if end % 2 == 0:
            end -= 1
        if start % 2 == 0:
            start += 1
        chunk_length = int((end - start) / process_count + 0.5)
        processes = []
        for chunk_start in range(start, end, chunk_length):
            process = mp.Process(
                target=calculate_primes,
                args=(
                    chunk_start,
                    min(chunk_start + chunk_length, end),
                    prime_numbers,
                    True,
                ),
            )
            process.start()
            processes.append(process)

        for process in processes:
            process.join()

        print(time.monotonic() - start_time)
    else:
        print("Invalid input")


if __name__ == "__main__":
    main()

Bevor man hier jetzt die Optimierung mit `remember` wieder versucht einzubauen, sollte man das ganz dringend erst einmal testbar machen und dann auch *testen*. Automatisiert und mit den passenden Randfällen um sicher zu sein, dass bei jeder Eingabe auch wirklich alle Primzahlen ermittelt werden und nicht durch die Start-/Endanpassung Kombinationen entstehen können bei denen nicht alle Kandidaten geprüft werden. Wenn ich bei Deinem Programm beispielsweise 18 eingebe, ist die 17 nicht im Ergebnis, da stimmt also was nicht. In meiner überarbeiteten Version ist das Ergebnis das gleiche, aber ich habe ja auch versucht inhaltlich nichts zu ändern, sondern Dein Programm einfach nur verständlicher und simpler auszudrücken.

Für die Tests empfehle ich einen Blick auf `pytest`.

[__blackjack__]

Mal ein Zeitvergleich: Das einfachste an Code was man machen kann: `sympy.primerange()` benutzen:

Code: Alles auswählen

#!/usr/bin/env python3
import time
from sympy import primerange


def main():
    answer = input(
        "Make a list of of all primes to (please give a whole number): "
    )
    start_time = time.monotonic()
    print(list(primerange(int(answer))))
    print(time.monotonic() - start_time)


if __name__ == "__main__":
    main()

Das ist 1 Prozess und reiner Python-Code soweit ich weiss. Das jetzt mal gegen Deinen und den von mir überarbeiteten Code mit 8 Prozessen und der Eingabe von 5 Millionen als Obergrenze:

Code: Alles auswählen

8.1 s  `sympy.primerange()` (1 Prozess)
7.6 s  Xethy (8 Prozesse)
4.9 s  Überarbeitete Version (8 Prozesse)

[Xethy]

Hallo, erstmal danke an euch beide, dass ihr euch die Zeit für mich genommen habt.
Entschuldigung auch, dass ich mit einer antwort so lange gebraucht habe; da ich gerade viel um die ohren habe hatte ich bisher keine Zeit zu antworten. Folgendes; ich sehe ihr beide habt ein problem damit gehabt dass ich ein dictonary als Liste missbraucht habe.

Lasst mich einmal kurz den Grund / das Problem erklären das ich damit zu lösen versuchte.

Ich hab noch alte versionen des codes da bei dem ich das problem erkannt/ erkannt zu glauben habe.

Hier haben wir einen simplen code, ganz am anfang meiner Tests, er ist quasi fast 1:1 aus einer Vorlesungsdatei importiert.
Ebenfalls, die nutzung der zeitmessung ist hier noch falsch... usw; grundsätzlich sollte die zeiten aber jedoch als gute abschätzung dienen.
Bitte geht damit nicht zu hart ins gericht; ich frage mal explizit nach keiner verbesserung dieses codes, es geht nur um das problem das ich damit hatte.


Folgender code testet alle ungeraden zahlen wenn ich mich korrekt erinnere:

Laufzeit bis 1.000.000 ca 35 sekunden auf meinem rechner.

Code: Alles auswählen

import time
import math
#Time at start
start = time.time()
input1 = input("Liste alle Primzahlen bis (ganze positive zahl eingeben): ")
def is_int(string):
    try:
        int(string)
        return True
    except ValueError:
        return False

if(is_int(input1) == True):
    k = 3
    last = 2
    z = 1
    prim = True
    num_list = [2]
    for n in  range(3, (int(input1)+1), 2):
        y = math.sqrt(n)
        while k <= y and prim:
            if(n % k == 0):
                prim = False
            k = k + 2
        k = 3
        z = 1
        if(prim == True):
            last = n
            z = 1
            num_list.append(n)
        prim = True
    end = time.time()
    print(f'{num_list}')
else:
    print("Invalid Input")
print(end-start)

Dieser code testet nur primzahlen als teiler. Dennoch; Laufzeit bis 1.000.000 ca 35 sekunden. - Das ergebnis sogar um eine nuance schlechter als beim original oben das nur mit ungeraden zahlen arbeitet.
Damit habe ich listen für das lesen mit primzahlen für meine nur die primzahlen zum teilen zu nehmen als ausgeschlossen betrachtet.
Nach ein wenig googlen habe ich dann festgestellt dass es an dem pop befehl und dem insert befehl für listen liegt. Im groben nimmt der code ja die primzahlen aus der liste und attacht sie dann wieder. dabei verschiebt er die gesamte liste einmal um das ergebnis zu lesen (umständlich, leichter zu lösen?) und dann wir das selbe wieder gemacht um das ergebnis wieder einzufügen. Leider habe ich nichts dahingehendes gefunden das ein ergebnis nur liest und nicht einmal die ganze liste verschieben muss nur um die primzahl zu lesen und dann die ganze liste wieder verschieben muss um sie dann einzufügen... vieleicht habt ihr da ja ne empfehlung.

Code: Alles auswählen

import time
import math
#Time at start
start = time.time()
input1 = input("Liste alle Primzahlen bis (ganze positive zahl eingeben): ")
def is_int(string):
    try: # Das ist alter code, Ziel war übrigens auch keinen Float input zu akzeptieren.
        int(string)
        if(int(string) == float(string)): 
            return True
        else:
            return False
    except ValueError:
        return False

if(is_int(input1) == True):
    k = 3
    last = 0
    z = 0
    lenght1 = -1
    prim = True
    imputsqrt = math.sqrt(int(input1))
    num_list = []
    num_list1 = []
    for n in  range(3, (int(input1)+1), 2):
        y = math.sqrt(n)
        while k <= y and prim:
            if(n % k == 0):
                prim = False
            if((k < last)):
                #print(lenght1)
                #print(z)
                k = num_list1.pop((lenght1 - z)) # Hier wurde der versuch gemacht die liste umzudrehen, dass kleine primzahlen weiter vorne im stackspeicher sind, wodurch das testen schneller geht. Meiner erinnerung nach war das schneller als die umgekehrte variante, wo die kleinen primzahlen am anfang der liste sind, obwohl die ganze liste einmal bewegt werden muss um eine neue zahl hinzuzufügen. Zumindest ist das so für kleine listen.
                #print("N:" + str(n))
                #print("Tested k:" + str(k))
                num_list1.insert((lenght1 - z), k)
                z = z + 1
            else:  
                k = k + 2
        k = 3
        z = 0
        if(prim == True):
            #print(last)
            if(imputsqrt < n):
                num_list.append(n)
            else:
                last = n
                num_list1.insert(0, n)
                lenght1 = lenght1 + 1
        prim = True
    num_list1.append(2) #nur ungerade zahlen werden betrachtet
    end = time.time()
    print(f'{num_list}')
    print(f'{num_list1}')
    print(len(num_list1))
else:
    print("Invalid Input")

print(end-start)

Meine lösung war jedenfalls ein dictonary als liste zu verwenden. Umständlich, ja aber es hat sich als zeiteffizienter bewiesen. Das ergebnis seht ihr ja an meinem späteren code. https://stackoverflow.com/questions/697 ... -in-python
Wenn ihr eine idee habt wie ich dennnoch listen verwenden kann, ohne pop und insert würde ich die gerne hören. Sonst habe ich mich auch entschieden nur die benötigten zahlen in ein dictonary zu machen, ein wenig in der sorge, dass ich sonst vieleicht den speicher sehr ineffizient nutze.

Sonst bin ich noch am knabbern von den codeschnipseln die ihr mir dagelassen habt. Lieben dank dafür.

[Sirius3]

Es macht wenig Sinn, diesen Code anzuschauen, weil wegschmeißen und Neuschreiben das einzige ist, was man damit machen kann. Das ist jetzt kein Angriff gegen Dich, sondern ein übliches Vorgehen, sobald man merkt, dass man sich verrannt hat. Gerade beim Lernen hilft jeder Code, und man versteht dann mehr und kann beim Neuschreiben neue Fehler machen. Es ist wie beim Malen lernen, dort verbesserst Du ja auch nicht 17mal die Augen, weil sie bei Deinem Porträt nicht stimmen, sondern grundierst Deine Leinwand und fängst von vorne an.

Was Du zuerst lernen solltest, ist, wie man mit Python mit Listen umgeht. Wie man über Listen iteriert, dass man keine Indizes benutzt.
Nimm Dir __blackjack__s Code als Vorlage, da steht in 6 Zeilen mit 3 Variablen das, was Du in 20 Zeilen mit 9 Variablen versuchst:

Code: Alles auswählen

    for candidate in range(3, end, 2):
        for prime_number in prime_numbers:
            if candidate % prime_number == 0:
                break
        else:
            prime_numbers.append(candidate)

[__blackjack__]

@Xethy: Noch mal zum `is_int()` weil da im Kommentar steht, dass das Ziel war auch keine Gleitkommazahlen als Eingabe zu akzeptieren: Da wird versucht ein Problem zu lösen, dass es so gar nicht gibt:

Code: Alles auswählen

In [269]: def is_int(string):
     ...:     try:
     ...:         int(string)
     ...:         return True
     ...:     except ValueError:
     ...:         return False
     ...: 

In [270]: is_int("42.0")
Out[270]: False

Und falls das meinte, das man der Funktion für das `string`-Argument auch Werte mit anderen Datentypen zu übergeben: *Das* wäre ja ein ganz anderes Problem, nicht mit dem Wert, sondern mit dem Datentyp. Es gibt ”unendlich” viele Datentypen, deren Werte sich mit `int()` in eine ganze Zahl umwandeln lassen. Jeder kann so einen Datentyp selbst schreiben/erfinden. Und das wäre kein Problem das ich in so einer Funktion lösen würde, denn das würde letztlich auf Typprüfungen hinaus laufen und damit für meinen Geschmack Python unterlaufen, denn dann schränkt man Duck-Typing ein. Wie würde man unterscheiden wollen welcher Typ okay ist und welcher nicht‽ Das kommt ja letztlich auf das Verhalten an.

[__blackjack__]

@Xethy: Was man bei der Zeitmessung auch vermeiden sollte ist das warten auf die Benutzereingabe mit einzubeziehen.

Für Code aus einer Vorlesung ist das erste Beispiel wirklich schlecht. Das war entweder nicht ordentlich vorbereitet, oder dem Dozenten war das nicht wichtig sauberen Code zu schreiben. Und dabei meine ich jetzt nicht, dass da unsaubere Abkürzungen verwendet werden um den Code kürzer und leichter Verständlich zu machen. Zum Beispiel das man Fehlerbehandlung weg lässt und zum Beispiel davon ausgeht, dass Eingaben sowohl den richtigen Typ als auch den richtigen Wertebereich haben, um sich auf den Algorithmus zu konzentrieren. Diese `is_int()` lenkt ja vom eigentlichen Berechnen der Primzahlen hier ja nur ab. Und die Umwandlung von Zeichenkette in Zahl ist im Algorithmus, statt dass das was ist was *davor* passiert.

Was dazu führt das zwar ``try``/``except`` drin steht, was für die Berechnung der Primzahlen nicht wichtig ist, auf der anderen Seite fehlt aber ``break`` in dem Code, was den Code vereinfachen würde.

`last` wird definiert aber nirgends verwendet. Und `k`, `z`, und `prim` werden viel zu oft mit Werten belegt, teilweise auch wieder offensichtlich unnötig, und wie schon in vorherigen Beiträgen erwähnt, an den falschen Stellen im Programmablauf. Das macht den eigentlich ja sehr einfachen Algorithmus schon unnötig kompliziert.

Hier mal beide Ansätze ohne so viele Variablen als Generatorfunktionen formuliert, so man auch schön sieht wie ähnlich die letztendlich sind:

Code: Alles auswählen

#!/usr/bin/env python3
import itertools
import math


def iter_primes_a():
    yield 2
    for candidate in itertools.count(3, step=2):
        for divisor in range(3, int(math.sqrt(candidate)) + 1, 2):
            if candidate % divisor == 0:
                break
        else:
            yield candidate


def iter_primes_b():
    yield 2
    primes = [2]
    for candidate in itertools.count(3, step=2):
        for divisor in primes:
            if candidate % divisor == 0:
                break
        else:
            yield candidate
            primes.append(candidate)


def main():
    limit = 100
    for iter_primes in [iter_primes_a, iter_primes_b]:
        print(iter_primes)
        for prime in iter_primes():
            print(prime)
            if prime >= limit:
                break


if __name__ == "__main__":
    main()

[Xethy]

Es macht wenig Sinn, diesen Code anzuschauen, weil wegschmeißen und Neuschreiben das einzige ist, was man damit machen kann. Das ist jetzt kein Angriff gegen Dich, sondern ein übliches Vorgehen, sobald man merkt, dass man sich verrannt hat. Gerade beim Lernen hilft jeder Code, und man versteht dann mehr und kann beim Neuschreiben neue Fehler machen. Es ist wie beim Malen lernen, dort verbesserst Du ja auch nicht 17mal die Augen, weil sie bei Deinem Porträt nicht stimmen, sondern grundierst Deine Leinwand und fängst von vorne an.

Was Du zuerst lernen solltest, ist, wie man mit Python mit Listen umgeht. Wie man über Listen iteriert, dass man keine Indizes benutzt.
Nimm Dir __blackjack__s Code als Vorlage, da steht in 6 Zeilen mit 3 Variablen das, was Du in 20 Zeilen mit 9 Variablen versuchst:

Code: Alles auswählen

    for candidate in range(3, end, 2):
        for prime_number in prime_numbers:
            if candidate % prime_number == 0:
                break
        else:
            prime_numbers.append(candidate)

Also, dass ich mich verannt habe, hab ich schon gemerkt; Ich wollte einfach nur explizit die frage stellen, weil ich listen ja bewusst nicht benutzt habe, ihr aber beide auf listen verweist, mir war nur nicht 100% klar wieso wo doch pop, insert ein problem sind. (ich hatte keine andere möglichkeit einen wert aus der liste explizit aufzurufen gewusst) Wenn ich nun an nehmen darf, sobald man es über eine For schleife löst ist es kein problem mehr oder weil auf den speicher nicht wie ein Stack zugegriffen wird. Was ich will ist nur, dass das programm nicht wie war die notation eine Laufzeit O(n) hat nur um einmal ein element aus der liste zu holen und wieder eine von (O)n um es wieder abzuspeichern.

- Was ich wissen will ist; ist es der zeitliche Aufwand wert mit einem Dictonary zu arbeiten um befehle wie insert oder pop zu benutzen oder nicht(und einfach mit for schleife zu arbeiten). Ich denke ich höre ein relativ klares oder nicht heraus. Weil in dem code oben ja explizit eine Liste mit einer For schleife bearbeitet wird (von der ich hoffe dass sie besser läuft als insert oder pop und nicht auf diese befehle zugreift). Ich denke ich habe langsam verstanden was oder wie ihr es macht.

[Xethy]

Hier mal beide Ansätze ohne so viele Variablen als Generatorfunktionen formuliert, so man auch schön sieht wie ähnlich die letztendlich sind:

Moment mal, der eine code bezieht gar nichts mit ein, nichtmal eine liste. Während der zweite einfach noch eine liste hinzufügt, welche überflüssig aussieht wo der erste code doch schon funktioniert.
Was ist nur vereinfacht welcher code? beide originale nutzen doch listen?
Ist dann nicht code b generell schlechter? Macht Itertools hier igentwas spezielles? Ich denke ich kucke mir das pack mal genauer an.

[__blackjack__]

@Xethy: Der erste Code entspricht dem Ansatz einfach alle geraden Zahlen bis zur Wurzel des Kandidaten als Divisor durchzuprobieren. Also das was Dein „Vorlesungs-Code“ macht. Und der zweite probiert die bisher gefundenen Primzahlen als Divisor. Ohne allerdings das Limit mit der Wurzel zu berücksichtigen — das könnte man da noch einbauen. Ich habe `divisor` mal in `prime` umbenannt wo sicher ist, dass das inhaltlich stimmt, und die Variante mit Begrenzung auf Primzahlen ≤Wurzel des Kandidaten hinzugefügt:

Code: Alles auswählen

#!/usr/bin/env python3
import math
from itertools import count, takewhile


def iter_primes_a():
    """
    Generate prime numbers by testing each candidate if divisible by odd numbers
    up to sqrt(candidate).
    """
    yield 2
    for candidate in count(3, step=2):
        for divisor in range(3, int(math.sqrt(candidate)) + 1, 2):
            if candidate % divisor == 0:
                break
        else:
            yield candidate


def iter_primes_b():
    """
    Generate prime numbers by testing each candidate if divisible by prime
    numbers found so far.
    """
    yield 2
    primes = [2]
    for candidate in count(3, step=2):
        for prime in primes:
            if candidate % prime == 0:
                break
        else:
            yield candidate
            primes.append(candidate)


def iter_primes_c():
    """
    Generate prime numbers by testing each candidate if divisible by prime
    numbers found so far up to sqrt(candidate).
    """
    yield 2
    primes = [2]
    for candidate in count(3, step=2):
        limit = math.sqrt(candidate)
        for prime in takewhile(lambda prime: prime <= limit, primes):
            if candidate % prime == 0:
                break
        else:
            yield candidate
            primes.append(candidate)


def main():
    limit = 1000
    for iter_primes in [iter_primes_a, iter_primes_b, iter_primes_c]:
        print(iter_primes)
        for number, prime in enumerate(iter_primes(), 1):
            if prime > limit:
                break
            print(number, prime)


if __name__ == "__main__":
    main()

[DeaD_EyE]

Kleine Anmerkung:

Code: Alles auswählen

return int(string) == float(string)

float hat seit einigen Updates die Methode is_integer.

So geht der Test auf Ganzzahlen einfacher:

Code: Alles auswählen

return float(string).is_integer()

Ein weiterer Vorteil ist, dass man sofort sieht, was man testen möchte.

[Xethy]

Hallo, ich habe erstmal ein kleines update zu dem code den ich von @__blackjack__ bekommen habe

Diesmal habe ich mir das to do das sich im code versteckt zur aufgabe gesetzt.

Ich hab den code durchgearbeitet und versucht eine sinnvolle ausgabe herauszubekommen. Wenn man nicht weiß was man tut ist dass ein klein wenig hölle. Es erst mit der multiprocessing queue versucht, die bei großen zahlen irgentwie abgestürtzt ist.
Bin dann auf den Manager gewechselt. Hier gab es keine probleme.

Dann habe ich verzweifelt nach einem weg gesucht die eingabe geordnet zu bekommen. *head smokes* und geordnet an meine primzahlenliste anzuhängen.

hab keinen weg gefunden um ein element in einer liste, welche in einer liste ist direkt anzusprechen und dann in der reihenfolge anzufügen. Deswegem wurde es das umständliche stück code dass es jetzt ist. Funktional aber, dauert eine Sekunde länger als der original code. Liegt wohl an dem befehl ".extend." das dieser code nicht besonders schnell ist, weiß ich ja inzwischen.

Ausserdem ein zwei kleine bugfixes. das Multiprocessing hat gerne mal 9 anstatt 8 prozessen gestartet und ich denke den fehler warum die 17 nicht ausgegeben wurde bei einer eingabe von 18 habe ich auch (ich denke) gefixt.

pytest kann ich nicht verwenden, da ich momentan auf windows arbeite. habe dazu nur Linux distributionen gefunden.
ich habe mich aber dazu hinreißen lassen linux auf eine alte festplatte zu schmeißen und werde da vieleicht mal mehr rumprobieren.

Nächstes ziel "Remember" wieder implementieren.

Code: Alles auswählen

#!/usr/bin/env python3
import math
import multiprocessing as mp
import time


def is_int(string):
    try:
        int(string)
    except ValueError:
        return False
    else:
        return True

def calculate_primes(
    start, end, known_prime_numbers=None, queue = None, Process_number = None
):
    if start % 2 == 0:
        start += 1

    if known_prime_numbers is None:
        known_prime_numbers = new_prime_numbers = [2]
    else:
        new_prime_numbers = []

    for candidate in range(start, end, 2):
        for prime_number in known_prime_numbers:
            if candidate % prime_number == 0:
                break
        else:
            new_prime_numbers.append(candidate)
    if queue == None:
        return new_prime_numbers
    else:
        returntuple = (Process_number, new_prime_numbers)
        queue.put(returntuple)
    
    
def main():
    answer = input(
        "Make a list of of all primes to (please give a whole number): "
    )
    if is_int(answer):
        start_time = time.monotonic()
        end = int(answer)
        start = int(math.sqrt(end))
        prime_numbers = calculate_primes(3, start)
        #print(prime_numbers)
        process_count = 8  # Change to the number of processes that are needed.
        if end % 2 == 0:
            end += 1
        if start % 2 == 0:
            start += 1
        if end < 1000000 :
            chunk_length = int(125000) 
        else:
            chunk_length = int((end - start) / process_count + 1) # changed from 0.5 to 1 old code gives out 9 processes often otherwise.
        processes = []
        queue = mp.Manager().Queue()
        for chunk_start in range(start, end, chunk_length): 
            process_number = int((chunk_start/chunk_length)+1)
            process = mp.Process(
                target=calculate_primes,
                args=(
                    chunk_start,
                    min(chunk_start + chunk_length, end),
                    prime_numbers, queue, process_number
                ),
            )
            process.start()
            processes.append(process)  
        results = []
        for process in processes:
            process.join()
            results.append(queue.get())#taking the results and process_numbers form the manager
            #print(process_number)
        process_return_order = list(list(zip(*results))[0])
        results = list(list(zip(*results))[1]) #process_number extracted, so the old results with the printorder is not needed can be replaced.
        number_of_element_to_attach = 0
        for element in process_return_order: #for every element in process_return_order find the one that is the next to attach to the prime_numbers.
            number_of_element_to_attach  += 1
            prime_numbers.extend(results[process_return_order.index(number_of_element_to_attach)])
        print(prime_numbers)  
        print(time.monotonic() - start_time)
    else:
        print("Invalid input")


if __name__ == "__main__":
    main()

[__blackjack__]

@Xethy: Warum denkst Du pytest nicht unter Windows verwenden zu können‽ Und Testen sollte wirklich der nächste Schritt sein, denn wichtiger als Geschwindigkeit ist ja wohl das es korrekte Ergebnisse liefert.

Das zusammensetzen des Ergebnisses ist unnötig kompliziert. Man würde die Tupel einfach sortieren und dann eine Schleife über die sortierten Ergebnisse schreiben.

Edit: Die Queue und die Prozessnummer haben in der Funktion die die Primzahlen berechnet eigentlich nichts zu suchen.

[Sirius3]

@Xethy: wie ich schon in meiner allerersten Antwort hier geschrieben habe, benutzt man keine multiprocessing direkt, sondern statt dessen multiprocessing-Pool oder concurrent.futures. Da muß man sich nicht um Queues, oder Reihenfolge, oder überhaupt um die Prozesse kümmern. Damit schrumpfen Deine drei komplizierten Schleifen zu einer einfachen zusammen.

[__blackjack__]

@Xethy: Du solltest das ganze wirklich dringend testbar(er) schreiben und dann auch testen. Denn es macht wenig Sinn Code der falsche Ergebnisse liefert schneller zu machen. Code muss erst korrekt sein, bevor man darüber nachdenkt den schneller zu machen.

Fehler im Moment: wenn man 2 oder 3 eingibt, dann ist 1 angeblich eine Primzahl. Bei 10 ist zum Beispiel die 9 mit im Ergebnis. Bei 30 ist da eine 25 unter den Primzahlen.

[Xethy]

Hey, ich habe nun Pytest installiert bekommen. (ich hatte nur pytest installation gesucht, und kam immer by Tar.gz packs raus was ja für linux ist, dass das einfach über das IDE geht ist mir nicht in den sinn gekommen, sorry - ich bin noch frisch im thema, und hatte zum beispiel bis heute keine ahnung von sort/ sorted)

Erstmal Danke dass ihr mir so tatkräftig helft, trotzdem ich hier nicht den besten code produziere.

Ich verspreche euch aber, dass ich motiviert bin, das ding gut zum Laufen zu bringen.

Ich hatte heute versucht (Den kommentar von @__blackjack__ umzusetzen und die Listen mit "Sorted" zu sortieren. Dies funktioniert aber nur mit kleineren listen. Als denen, welche generiert werden.

@Sirius, sorry dass ich bisher Pool ignoriert habe. Ich habe nur mit Pool bisher kein vernüftiges programm zum laufen gebracht. Und bei Queues hat es halt funktioniert.

Also lasst mich mal eine Prioritäten To do list aufstellen

1) Versuch das Programm über pool, gelöst zu bekommen, damit die Sortierung der listen wegfällt.
2) Bugs die falsche Primzahlen erzeugen beheben. (mit dem nun installierten Pytest)
3) Remember optimierung einführen
4) Euklidisches Netz einführen.
5) Andere Netze?

- Wenn ihr eine andere reihnfolge in Prioritätenliste für sinnvoll haltet oder ich einen punkt vergessen haben sollte, schreibt mir einfach.