Python Language
Python snelheid van programma

schrijfwijze

Basisidee

De notatie die wordt gebruikt bij het beschrijven van de snelheid van uw Python-programma wordt Big-O-notatie genoemd. Laten we zeggen dat je een functie hebt:

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

Dit is een eenvoudige functie om te controleren of een item in een lijst staat. Om de complexiteit van deze functie te beschrijven, zegt u O (n). Dit betekent "Volgorde van n" omdat de O-functie de Bestelfunctie wordt genoemd.

O (n) - in het algemeen is n het aantal items in een container

O (k) - in het algemeen is k de waarde van de parameter of het aantal elementen in de parameter

Lijst bewerkingen

Bewerkingen: Gemiddeld geval (veronderstelt dat parameters willekeurig worden gegenereerd)

Toevoegen: O (1)

Kopiëren: O (n)

Del slice: O (n)

Verwijder item: O (n)

Invoegen: O (n)

Krijg item: O (1)

Set item: O (1)

Iteratie: O (n)

Krijg segment: O (k)

Set slice: O (n + k)

Verlengen: O (k)

Sorteren: O (n log n)

Vermenigvuldigen: O (nk)

x in s: O (n)

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

Krijg lengte: O (1)

Deque operaties

Een deque is een dubbele rij.

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)

Bewerkingen: Gemiddeld geval (veronderstelt dat parameters willekeurig worden gegenereerd)

Toevoegen: O (1)

Appendleft: O (1)

Kopiëren: O (n)

Verlengen: O (k)

Extendleft: O (k)

Pop: O (1)

Popleft: O (1)

Verwijderen: O (n)

Roteren: O (k)

Bewerkingen instellen

Bewerking: Gemiddeld geval (gaat uit van willekeurig gegenereerde parameters): Slechtste geval

x in s: O (1)

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

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

Meerdere snijpunten s1 & s2 & s3 & ... & sn:: (n-1) * O (l) waarbij l max is (len (s1), ..., len (sn))

s.difference_update (t): O (len (t)): O (len (t) * len (s))

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

Symetrisch verschil s ^ t: O (len (s)): O (len (s) * len (t))

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

Algoritmische notaties ...

Er zijn bepaalde principes die van toepassing zijn op optimalisatie in elke computertaal en Python is geen uitzondering. Optimaliseer niet onderweg : schrijf uw programma zonder rekening te houden met mogelijke optimalisaties en concentreer u in plaats daarvan op het controleren of de code schoon, correct en begrijpelijk is. Als het te groot of te langzaam is als je klaar bent, dan kun je overwegen het te optimaliseren.

Onthoud de 80/20-regel : in veel velden krijgt u 80% van het resultaat met 20% van de inspanning (ook wel de 90/10-regel genoemd - het hangt af van met wie u praat). Wanneer je code gaat optimaliseren, gebruik je profilering om uit te vinden waar die 80% van de uitvoeringstijd naartoe gaat, zodat je weet waar je je inspanningen kunt concentreren.

Voer altijd "voor" en "na" benchmarks uit : hoe weet u anders dat uw optimalisaties daadwerkelijk een verschil hebben gemaakt? Als uw geoptimaliseerde code slechts iets sneller of kleiner blijkt te zijn dan de oorspronkelijke versie, maakt u uw wijzigingen ongedaan en gaat u terug naar de oorspronkelijke, duidelijke code.

Gebruik de juiste algoritmen en gegevensstructuren: gebruik geen O (n2) bellen sorteeralgoritme om duizend elementen te sorteren wanneer er een O (n log n) quicksort beschikbaar is. Sla ook geen duizend items op in een array waarvoor een O (n) -zoekactie vereist is wanneer u een O (log n) binaire boom of een O (1) Python-hashtabel kunt gebruiken.

Voor meer bezoek de onderstaande link ... Python Speed Up

De volgende 3 asymptotische notaties worden meestal gebruikt om tijdcomplexiteit van algoritmen weer te geven.

1. Θ Notatie : de theta-notatie begrenst functies van boven en onder, dus definieert het exact asymptotisch gedrag. Een eenvoudige manier om Theta-notatie van een uitdrukking te krijgen, is door termen van lage orde weg te laten en hoofdconstanten te negeren. Overweeg bijvoorbeeld de volgende uitdrukking. 3n3 + 6n2 + 6000 = Θ (n3) Lagere termijnen laten vallen is altijd prima, want er zal altijd een n0 zijn waarna Θ (n3) hogere waarden heeft dan Θn2) ongeacht de betrokken constanten. Voor een gegeven functie g (n) geven we aan dat Θ (g (n)) een reeks functies volgt. Θ (g (n)) = {f (n): er bestaan positieve constanten c1, c2 en n0 zodat 0 <= c1 g (n) <= f (n) <= c2 g (n) voor alle n> = n0} De bovenstaande definitie betekent dat als f (n) theta is van g (n), de waarde f (n) altijd tussen c1 g (n) en c2 g (n) is voor grote waarden van n (n> = n0). De definitie van theta vereist ook dat f (n) niet-negatief moet zijn voor waarden van n groter dan n0.

2. Big O-notatie : de Big O-notatie definieert een bovengrens van een algoritme, het beperkt een functie alleen van bovenaf. Denk bijvoorbeeld aan het geval van invoegsortering. In het beste geval duurt het lineaire tijd en in het slechtste geval kwadratische tijd. We kunnen gerust zeggen dat de tijdcomplexiteit van Insertion-sortering O (n ^ 2) is. Merk op dat O (n ^ 2) ook lineaire tijd omvat. Als we ation-notatie gebruiken om de tijdcomplexiteit van het type Invoeging weer te geven, moeten we twee verklaringen gebruiken voor de beste en slechtste gevallen:

1. De tijdcomplexiteit van het slechtste geval van Insertion Sort is Θ (n ^ 2).
2. De complexiteit van het beste geval van invoegsortering is Θ (n).

De Big O-notatie is handig wanneer we alleen een bovengrens hebben voor de tijdcomplexiteit van een algoritme. Vaak vinden we gemakkelijk een bovengrens door eenvoudig naar het algoritme te kijken. O (g (n)) = {f (n): er bestaan positieve constanten c en n0 zodat 0 <= f (n) <= cg (n) voor alle n> = n0}

3. Ω-notatie : net zoals Big O-notatie een asymptotische bovengrens voor een functie biedt, geeft Ω-notatie een asymptotische ondergrens. Ω Notatie <kan nuttig zijn wanneer we de tijdsgebondenheid van een algoritme ondergrens hebben. Zoals besproken in de vorige post, zijn de beste case-prestaties van een algoritme over het algemeen niet nuttig, de Omega-notatie is de minst gebruikte notatie bij alle drie. Voor een gegeven functie g (n) geven we met Ω (g (n)) de set functies aan. Ω (g (n)) = {f (n): er bestaan positieve constanten c en n0 zodat 0 <= cg (n) <= f (n) voor alle n> = n0}. Laten we hier hetzelfde voorbeeld van het invoegtype beschouwen. De tijdcomplexiteit van Insertion Sort kan worden geschreven als Ω (n), maar het is geen erg nuttige informatie over insertion sort, omdat we over het algemeen geïnteresseerd zijn in het slechtste geval en soms in het gemiddelde geval.