Python Language
Pythons programhastighet

Notation

Grundläggande idé

Notationen som används när du beskriver hastigheten för ditt Python-program kallas Big-O-notation. Låt oss säga att du har en funktion:

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

Detta är en enkel funktion för att kontrollera om ett objekt finns i en lista. För att beskriva komplexiteten hos den här funktionen säger du O (n). Detta betyder "Order of n" eftersom O-funktionen kallas Order-funktionen.

O (n) - i allmänhet är n antalet artiklar i behållaren

O (k) - generellt är k värdet på parametern eller antalet element i parametern

Lista operationer

Åtgärder: Medelfall (förutsätter att parametrar genereras slumpmässigt)

Bilaga: O (1)

Kopia: O (n)

Del skiva: O (n)

Radera objekt: O (n)

Infoga: O (n)

Hämta artikel: O (1)

Ställ in artikel: O (1)

Iteration: O (n)

Få skiva: O (k)

Ställ in skiva: O (n + k)

Förlängning: O (k)

Sortera: O (n log n)

Multiplicera: O (nk)

x i s: O (n)

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

Få längd: O (1)

Färgoperationer

En kvist är en dubbelkön.

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)

Åtgärder: Medelfall (förutsätter att parametrar genereras slumpmässigt)

Bilaga: O (1)

Appendleft: O (1)

Kopia: O (n)

Förlängning: O (k)

Extendleft: O (k)

Pop: O (1)

Popleft: O (1)

Ta bort: O (n)

Rotera: O (k)

Ställ in operationer

Funktion: Medelfall (antar parametrar som skapats slumpmässigt): Värsta fall

x i s: O (1)

Skillnad s - t: O (len (er))

Korsning s & t: O (min (len (er), len (t))): O (len (er) * len (t)

Flera korsningar s1 & s2 & s3 & ... & sn:: (n-1) * O (l) där l är max (len (s1), ..., len (sn))

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

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

Symetrisk skillnad s ^ t: O (len (er)): O (len (er) * len (t))

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

Algoritmiska notationer ...

Det finns vissa principer som gäller optimering på vilket datorspråk som helst, och Python är inget undantag. Optimera inte när du går : Skriv ditt program utan att ta hänsyn till möjliga optimeringar, koncentrera dig istället på att se till att koden är ren, korrekt och förståelig. Om det är för stort eller för långsamt när du är klar kan du överväga att optimera det.

Kom ihåg 80/20-regeln : I många fält kan du få 80% av resultatet med 20% av insatsen (kallas även 90/10-regeln - det beror på vem du pratar med). När du ska optimera koden använder du profilering för att ta reda på vart 80% av körningstiden går, så att du vet vart du ska koncentrera din insats.

Kör alltid "före" och "efter" riktmärken : Hur annars vet du att dina optimeringar faktiskt gjorde en skillnad? Om din optimerade kod visar sig vara bara något snabbare eller mindre än den ursprungliga versionen, ångra dina ändringar och gå tillbaka till den ursprungliga, tydliga koden.

Använd rätt algoritmer och datastrukturer: Använd inte en O (n2) bubbelsorteringsalgoritm för att sortera tusen element när det finns en O (n log n) kvicksort tillgänglig. På samma sätt förvara inte tusen objekt i en matris som kräver en O (n) -sökning när du kan använda ett O (log n) binärt träd eller en O (1) Python-hash-tabell.

För mer besök länken nedan ... Python Speed Up

Följande 3 asymptotiska notationer används mest för att representera tidskomplexiteten hos algoritmer.

1. Θ Notation : Theta-notationen begränsar funktioner från ovan och under, så den definierar exakt asymptotiskt beteende. Ett enkelt sätt att få Theta-notation av ett uttryck är att släppa ordningar med låg ordning och ignorera ledande konstanter. Tänk till exempel på följande uttryck. 3n3 + 6n2 + 6000 = Θ (n3) Det är alltid bra att släppa med lägre ordning eftersom det alltid kommer att finnas en n0, varefter Θ (n3) har högre värden än Θn2) oavsett de involverade konstanterna. För en given funktion g (n) anger vi Θ (g (n)) följer uppsättningen funktioner. Θ (g (n)) = {f (n): det finns positiva konstanter c1, c2 och n0 så att 0 <= c1 g (n) <= f (n) <= c2 g (n) för alla n> = n0} Ovanstående definition betyder, om f (n) är theta för g (n), då är värdet f (n) alltid mellan c1 g (n) och c2 g (n) för stora värden på n (n> = n0). Definitionen av teta kräver också att f (n) måste vara icke-negativt för värden på n större än n0.

2. Big O-notation : Big O-notationen definierar en övre gräns för en algoritm, den begränsar en funktion endast ovanifrån. Tänk till exempel på Insertion Sort. Det tar i bästa fall linjär tid och kvadratisk tid i värsta fall. Vi kan säkert säga att tidskomplexiteten för Insertion sort är O (n ^ 2). Observera att O (n ^ 2) också täcker linjär tid. Om vi använder ation notation för att representera tidskomplexiteten för Insertion sort måste vi använda två påståenden för bästa och värsta fall:

1. Det värsta fallskomplexiteten för Insertion Sort är Θ (n ^ 2).
2. Det bästa fallet med komplexitet för Insertion Sort är Θ (n).

Big O-notationen är användbar när vi bara har en övre gräns för tidskomplexiteten hos en algoritm. Många gånger hittar vi lätt en övre gräns genom att helt enkelt titta på algoritmen. O (g (n)) = {f (n): det finns positiva konstanter c och n0 så att 0 <= f (n) <= cg (n) för alla n> = n0}

3. Ω Notation : Precis som Big O-notation ger en asymptotisk övre gräns på en funktion, ger Ω notation en asymptotisk nedre gräns. Ω Notation <kan vara användbart när vi har en lägre tidsbegränsning av en algoritm. Som diskuterats i det föregående inlägget är den bästa fallprestanda för en algoritm i allmänhet inte användbar, Omega-notationen är den minst använda notationen bland alla tre. För en given funktion g (n) anger vi med Ω (g (n)) uppsättningen av funktioner. Ω (g (n)) = {f (n): det finns positiva konstanter c och n0 så att 0 <= cg (n) <= f (n) för alla n> = n0}. Låt oss överväga samma exempel på Insertion här. Tidskomplexiteten för Insertion Sort kan skrivas som Ω (n), men det är inte en mycket användbar information om insättningssortering, eftersom vi i allmänhet är intresserade av värsta fall och ibland i genomsnitt.