Python Language
Python-Geschwindigkeit des Programms

Notation

Die Grundidee

Die Notation, die zur Beschreibung der Geschwindigkeit Ihres Python-Programms verwendet wird, wird als Big-O-Notation bezeichnet. Nehmen wir an, Sie haben eine Funktion:

def list_check(to_check, the_list):
    for item in the_list:
        if to_check == item:
          return True
    return False

Dies ist eine einfache Funktion, um zu überprüfen, ob sich ein Element in einer Liste befindet. Um die Komplexität dieser Funktion zu beschreiben, sagen Sie O (n). Dies bedeutet "Order of n", da die O-Funktion als Order-Funktion bezeichnet wird.

O (n) - im Allgemeinen ist n die Anzahl der Artikel im Container

O (k) - im Allgemeinen ist k der Wert des Parameters oder die Anzahl der Elemente im Parameter

Operationen auflisten

Operations: Average Case (setzt voraus, dass die Parameter zufällig generiert werden)

Anhängen: O (1)

Kopie: O (n)

Del Slice: O (n)

Element löschen: O (n)

Einfügen: O (n)

Gegenstand erhalten: O (1)

Setzposten: O (1)

Iteration: O (n)

Slice erhalten: O (k)

Slice einstellen: O (n + k)

Erweitern: O (k)

Sortierung: O (n log n)

Multiplizieren Sie: O (nk)

x in s: O (n)

min (s), max (s): O (n)

Länge erhalten: O (1)

Deque-Operationen

Eine Deque ist eine doppelseitige Warteschlange.

class Deque:
def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def addFront(self, item):
    self.items.append(item)

def addRear(self, item):
    self.items.insert(0,item)

def removeFront(self):
    return self.items.pop()

def removeRear(self):
    return self.items.pop(0)

def size(self):
    return len(self.items)

Operations: Average Case (setzt voraus, dass die Parameter zufällig generiert werden)

Anhängen: O (1)

Anhang: O (1)

Kopie: O (n)

Erweitern: O (k)

Linkshöhe: O (k)

Pop: O (1)

Popleft: O (1)

Entfernen: O (n)

Drehen: O (k)

Operationen einstellen

Operation: Average Case (unterstellt, dass die Parameter zufällig generiert werden): Worst case

x in s: O (1)

Unterschied s - t: O (len (s))

Schnittpunkt s & t: O (min (len (s), len (t))): O (len (s) * len (t)

Mehrere Schnittpunkte s1 & s2 & s3 & ... & sn:: (n-1) * O (l) wobei l max ist (len (s1), ..., len (sn))

abweichungsupdate (t): O (len (t)): O (len (t) * len (s))

s.symetric_difference_update (t): O (len (t))

Symmetrische Differenz s ^ t: O (len (s)): O (len (s) * len (t))

Union s | t: O (len (s) + len (t))

Algorithmische Notationen ...

Es gibt bestimmte Prinzipien, die für die Optimierung in jeder Computersprache gelten, und Python ist keine Ausnahme. Optimieren Sie nicht wie Sie : Schreiben Sie Ihr Programm ohne Berücksichtigung möglicher Optimierungen und konzentrieren Sie sich stattdessen darauf, dass der Code sauber, korrekt und verständlich ist. Wenn es zu groß oder zu langsam ist, können Sie es in Betracht ziehen, es zu optimieren.

Denken Sie an die 80/20-Regel : In vielen Bereichen können Sie mit 20% des Aufwands 80% des Ergebnisses erzielen (auch als 90/10-Regel bezeichnet - abhängig davon, mit wem Sie sprechen). Wann immer Sie Code optimieren möchten, verwenden Sie die Profilerstellung, um herauszufinden, wo 80% der Ausführungszeit liegen. So wissen Sie, wo Sie Ihre Anstrengungen konzentrieren müssen.

Führen Sie immer "vor" und "nach" Benchmarks aus : Wie wissen Sie sonst noch, dass Ihre Optimierungen tatsächlich einen Unterschied gemacht haben? Wenn sich herausstellt, dass Ihr optimierter Code nur geringfügig schneller oder kleiner als die Originalversion ist, machen Sie Ihre Änderungen rückgängig und kehren Sie zum ursprünglichen Code zurück.

Verwenden Sie die richtigen Algorithmen und Datenstrukturen: Verwenden Sie keinen O (n2) - Blasensortieralgorithmus, um tausend Elemente zu sortieren, wenn ein O (n log n) - Quicksort verfügbar ist. Speichern Sie auf keinen Fall eintausend Elemente in einem Array, für das eine O (n) -Suche erforderlich ist, wenn Sie einen binären O (log n) -Baum oder eine O (1) -Python-Hashtabelle verwenden könnten.

Für weitere Informationen besuchen Sie den folgenden Link ... Python Speed ​​Up

Die folgenden 3 asymptotischen Notationen werden meist zur Darstellung der zeitlichen Komplexität von Algorithmen verwendet.

1. Θ Notation : Die Theta-Notation begrenzt Funktionen von oben und unten und definiert somit genau asymptotisches Verhalten. Eine einfache Möglichkeit, die Theta-Notation eines Ausdrucks zu erhalten, besteht darin, niederwertige Terme zu löschen und führende Konstanten zu ignorieren. Betrachten Sie zum Beispiel den folgenden Ausdruck. 3n3 + 6n2 + 6000 = Θ (n3) Das Ablegen von Termen niedrigerer Ordnung ist immer in Ordnung, da es immer ein n0 gibt, nach dem Θ (n3) unabhängig von den beteiligten Konstanten höhere Werte als Θn2 hat. Für eine gegebene Funktion g (n) bezeichnen wir Θ (g (n)) als Funktionssatz. (G (n)) = {f (n): Es gibt positive Konstanten c1, c2 und n0, so dass 0 <= c1 g (n) <= f (n) <= c2 g (n) für alle n> ist = n0} Die obige Definition bedeutet, wenn f (n) theta von g (n) ist, dann liegt der Wert f (n) immer zwischen c1 g (n) und c2 g (n) für große Werte von n (n> = n0). Die Definition von Theta erfordert auch, dass f (n) für Werte von n größer als n0 nicht negativ sein darf.

2. Big-O-Notation : Die Big-O-Notation definiert eine obere Grenze eines Algorithmus, sie begrenzt eine Funktion nur von oben. Betrachten Sie beispielsweise den Fall Einfügungssortierung. Im besten Fall dauert es linear und im schlechtesten Fall quadratisch. Wir können mit Sicherheit sagen, dass die zeitliche Komplexität der Einfügungssortierung O (n ^ 2) ist. Beachten Sie, dass O (n ^ 2) auch die lineare Zeit abdeckt. Wenn wir die complexity-Notation verwenden, um die zeitliche Komplexität der Einfügungssortierung darzustellen, müssen wir zwei Anweisungen für den besten und den schlechtesten Fall verwenden:

1. Die ungünstigste zeitliche Komplexität von Insertion Sort ist Θ (n ^ 2).
2. Die beste zeitliche Komplexität von Insertion Sort ist Θ (n).

Die Big-O-Notation ist nützlich, wenn die Komplexität eines Algorithmus nur mit der Zeit begrenzt ist. Oft finden wir leicht eine obere Grenze, indem wir einfach den Algorithmus betrachten. O (g (n)) = {f (n): Es gibt positive Konstanten c und n0, so dass 0 <= f (n) <= cg (n) für alle n> = n0}

3. Ω-Notation : So wie die Big-O-Notation eine asymptotische Obergrenze für eine Funktion bereitstellt, stellt die Ω-Notation eine asymptotische Untergrenze bereit. Ω Notation <kann nützlich sein, wenn die Komplexität eines Algorithmus niedriger ist. Wie im vorherigen Post diskutiert, ist die beste Leistung eines Algorithmus im Allgemeinen nicht nützlich. Die Omega-Notation ist die am wenigsten verwendete Notation unter allen drei. Für eine gegebene Funktion g (n) bezeichnen wir die Menge der Funktionen mit Ω (g (n)). Ω (g (n)) = {f (n): Es gibt positive Konstanten c und n0, so dass 0 <= cg (n) <= f (n) für alle n> = n0} ist. Betrachten wir hier dasselbe Einfügungssortierbeispiel. Die zeitliche Komplexität der Einfügungssortierung kann als Ω (n) geschrieben werden, ist jedoch keine sehr nützliche Information über die Einfügungssortierung, da wir uns im Allgemeinen für den ungünstigsten Fall und manchmal für den Durchschnittsfall interessieren.