Optimieren von Code

• Zu Aufgabe 1 - Effiziente Summenberechnung: Optimierung der Berechnung großer Summen von natürlichen Zahlen
• Zu Aufgabe 2 - Durchschnittsberechnung: Ermittlung des arithmetischen Mittels einer Liste von Zahlen in Python
• Zu Aufgabe 3 - Primfaktorzerlegung
• Zu Aufgabe 4 - Summe der Zahlen von 0 bis x
• Fazit

1. Aufgabe: Effiziente Summenberechnung: Optimierung der Berechnung großer Summen von natürlichen Zahlen

Dieser Code berechnet die Summe aller natürlichen Zahlen von 0 bis n-1. Wenn wir eine große Zahl als Eingabe (n) verwenden, kann es eine Weile dauern, um die Summe zu berechnen.

def find_sum(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum

print(find_sum(1000000))

Die Ausführung des Code-Blocks hat 0.02502 Sekunden gedauert.

Promt: Wie kann man diesen Code optimieren, um die Berechnungszeit zu verkürzen?

Ergebnis: Hier ist eine optimierte Version des Codes:

def find_sum(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum

print(find_sum(1000000))

Diese Version verwendet eine mathematische Formel, um die Summe aller natürlichen Zahlen von 0 bis n-1 zu berechnen, anstatt eine Schleife zu durchlaufen. Die Formel ist bekannt als die "Gaußsche Summenformel" oder auch "arithmetische Summenformel". Indem wir diese Formel verwenden, können wir die Berechnungszeit erheblich reduzieren. Die Division durch 2 wird verwendet, um eine Ganzzahl-Division sicherzustellen und das richtige Ergebnis zu erhalten, auch wenn n ungerade ist.

Wenn wir diese optimierte Version des Codes verwenden, wird die Summe der natürlichen Zahlen von 0 bis 999999 in weniger als einer Sekunde berechnet, im Gegensatz zur vorherigen Version, die mehrere Sekunden benötigt hätte.

Test in der Entwicklungsumgebung:

def find_sum(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum

Output:

499999500000

Die Ausführung des Code-Blocks hat 0.00000 Sekunden gedauert.

2. Aufgabe: Durchschnittsberechnung: Ermittlung des arithmetischen Mittels einer Liste von Zahlen in Python

Gegeben ist eine Liste von Zahlen. Schreibe eine Funktion in Python, die das arithmetische Mittel dieser Zahlen berechnet.

def average(numbers):
    sum = 0
    count = 0
    for number in numbers:
        sum += number
        count += 1
    if count > 0:
        return sum / count
    else:
        return 0

Die Ausführung des Code-Blocks hat 0.00000 Sekunden gedauert.

Prompt: Wie kann ich die Länge dieses Codes verkürzen?

Ergebnis: Dieser Code funktioniert, aber er kann noch verbessert werden. Eine mögliche Verbesserung besteht darin, die Funktion sum() zu verwenden, um die Summe der Zahlen in der Liste zu berechnen, anstatt eine Schleife zu verwenden. Außerdem können wir die Bedingung if count > 0 entfernen, da die Division durch 0 nicht möglich ist und wir daher sicher sein können, dass count immer größer als 0 ist.

Hier ist der optimierte Code:

def average(numbers):
    sum = 0
    count = 0
    for number in numbers:
        sum += number
        count += 1
    if count > 0:
        return sum / count
    else:
        return 0

In diesem optimierten Code haben wir die Funktion sum() verwendet, um die Summe der Zahlen in der Liste zu berechnen, anstatt eine Schleife zu verwenden. Außerdem haben wir die Bedingung if count > 0 entfernt und sie durch if len(numbers) > 0 ersetzt, um sicherzustellen, dass wir immer eine Liste von Zahlen haben und nicht versehentlich eine leere Liste übergeben.

Test in der Entwicklungsumgebung:

def average(numbers):
    if len(numbers) > 0:
        return sum(numbers) / len(numbers)
    else:
        return 0

numbers = [1, 2, 3, 4, 5]
result = average(numbers)
print("Das arithmetische Mittel von", numbers, "ist", result)

Output:

Das arithmetische Mittel von [1, 2, 3, 4, 5] ist 3.0

3. Aufgabe: Primfaktorzerlegung

Dieser Code führt die Primfaktorzerlegung für die Zahl number durch:

def prime_factorization(n):
    factors = []
    divisor = 2

    while divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n /= divisor
        else:
            divisor += 1

    return factors
number = 999999998
factors = prime_factorization(number)
print("Primfaktoren von", number, ":", factors)

Die Ausführung des Code-Blocks führte zu folgendem Ergebnis:

Primfaktoren von 999999998 : [2, 691, 723589]
Ausführungsdauer: 0.083147 Sekunden

Prompt:

Lässt sich dieser Code für die Primfaktorzerlegung optimieren?

Ergebnis ChatGPT:

Ja, der Code für die Primfaktorzerlegung lässt sich optimieren, um die Ausführungszeit zu reduzieren. Hier ist eine optimierte Version des Codes:

def prime_factorization(n):
    factors = []
    divisor = 2

    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1

    if n > 1:
        factors.append(n)

    return factors

# Eine große Zahl für die Primfaktorzerlegung
number = 999999998

# Berechnung der Primfaktorzerlegung
factors = prime_factorization(number)

print("Primfaktoren von", number, ":", factors)

Die Optimierungen im Code sind:

Wir verwenden die Bedingung divisor * divisor <= n anstelle von divisor <= n in der While-Schleife. Dadurch reduzieren wir die Anzahl der Schleifendurchläufe, da wir wissen, dass der größte Teiler einer Zahl nicht größer als die Quadratwurzel dieser Zahl sein kann.

Anstelle von n /= divisor verwenden wir n //= divisor, um eine Ganzzahldivision durchzuführen. Dadurch wird eine Fließkommaoperation vermieden und die Leistung verbessert.

Am Ende überprüfen wir, ob n größer als 1 ist. Wenn ja, fügen wir n als weiteren Primfaktor hinzu. Dies ist wichtig, um sicherzustellen, dass alle Primfaktoren erfasst werden, insbesondere wenn die eingegebene Zahl selbst eine Primzahl ist.

Durch diese Optimierungen wird die Ausführungszeit der Primfaktorzerlegung erheblich reduziert.

Test in der Entwicklungsumgebung:

import time
start = time.time()
def prime_factorization(n):
    factors = []
    divisor = 2

    while divisor * divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        else:
            divisor += 1

    if n > 1:
        factors.append(n)

    return factors

# Eine große Zahl für die Primfaktorzerlegung
number = 999999998

# Berechnung der Primfaktorzerlegung
factors = prime_factorization(number)

print("Primfaktoren von", number, ":", factors)


end = time.time()
execution_time = end - start
print("Ausführungsdauer: {:.6f} Sekunden".format(execution_time))

Output:

Primfaktoren von 999999998 : [2, 691, 723589]
Ausführungsdauer: 0.001001 Sekunden

4. Aufgabe: Summe der Zahlen von 0 bis x

Dieser Code summiert die Zahlen von 0 bis 100 Millionen:

def perform_computation():
    result = 0
    for i in range(10**8):
        result += i
    return result
computation_result = perform_computation()
print("Berechnungsergebnis:", computation_result)

Berechnungsergebnis: 4999999950000000
Ausführungsdauer: 3.566159 Sekunden

Prompt: Lässt sich dieser Code im Hinblick auf die Ausführungsdauer optimieren?

Ergebnis ChatGPT:

Um die Ausführungsdauer des Codes zu optimieren, könnten wir die Berechnung durch eine mathematische Formel ersetzen, die die Summe der Zahlen von 0 bis n berechnet. Hier ist eine optimierte Version des Codes:

Berechnungsergebnis: 4999999950000000
Ausführungsdauer: 3.566159 Sekunden

In dieser optimierten Version verwenden wir die mathematische Formel für die Summe der Zahlen von 0 bis n, die als die Summe der aufeinanderfolgenden natürlichen Zahlen bekannt ist. Durch die direkte Berechnung der Formel anstelle einer Schleife wird die Ausführungsdauer erheblich verkürzt.

Test in der Entwicklungsumgebung:

import time
start = time.time()

def perform_computation():
    n = 10**8
    result = (n * (n + 1)) // 2
    return result

computation_result = perform_computation()
print("Berechnungsergebnis:", computation_result)

end = time.time()
execution_time = end - start
print("Ausführungsdauer: {:.6f} Sekunden".format(execution_time))

Output:

Berechnungsergebnis: 5000000050000000
Ausführungsdauer: 0.000000 Sekunden

Das Ergebnis liegt 1 daneben, aber ist von der zeitlichen Durchführung her deutlich reduziert.

Fazit