Python Language
Python velocità del programma

Notazione

Idea base

La notazione usata quando descrive la velocità del tuo programma Python è chiamata notazione Big-O. Diciamo che hai una funzione:

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

Questa è una semplice funzione per verificare se un elemento è in una lista. Per descrivere la complessità di questa funzione, dirai O (n). Questo significa "Ordine di n" poiché la funzione O è nota come funzione Ordine.

O (n) - generalmente n è il numero di elementi nel contenitore

O (k) - generalmente k è il valore del parametro o il numero di elementi nel parametro

Elenca le operazioni

Operazioni: caso medio (presuppone che i parametri siano generati casualmente)

Aggiungi: O (1)

Copia: O (n)

Del slice: O (n)

Elimina oggetto: O (n)

Inserisci: O (n)

Ottieni l'oggetto: O (1)

Set item: O (1)

Iterazione: O (n)

Ottieni una fetta: O (k)

Imposta slice: O (n + k)

Estendi: O (k)

Ordina: O (n log n)

Moltiplicare: O (nk)

x in s: O (n)

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

Ottieni la lunghezza: O (1)

Operazioni di deque

Una deque è una coda a doppio attacco.

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)

Operazioni: caso medio (presuppone che i parametri siano generati casualmente)

Aggiungi: O (1)

Appendleft: O (1)

Copia: O (n)

Estendi: O (k)

Extendleft: O (k)

Pop: O (1)

Popleft: O (1)

Rimuovi: O (n)

Ruota: O (k)

Imposta le operazioni

Operazione: caso medio (presuppone che i parametri siano generati casualmente): caso peggiore

x in s: O (1)

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

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

Intersezione multipla s1 & s2 & s3 & ... & sn:: (n-1) * O (l) dove l è 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))

Differenza simmetrica s ^ t: O (len (s)): O (len (s) * len (t))

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

Notifiche algoritmiche ...

Ci sono alcuni principi che si applicano all'ottimizzazione in qualsiasi linguaggio del computer, e Python non fa eccezione. Non ottimizzare mentre procedi : scrivi il tuo programma senza tener conto delle possibili ottimizzazioni, concentrandoti invece a fare in modo che il codice sia pulito, corretto e comprensibile. Se è troppo grande o troppo lento quando hai finito, puoi considerare di ottimizzarlo.

Ricorda la regola 80/20 : in molti campi puoi ottenere l'80% del risultato con il 20% dello sforzo (chiamato anche regola 90/10, dipende da chi stai parlando). Ogni volta che stai per ottimizzare il codice, utilizza la creazione di profili per scoprire dove sta andando l'80% del tempo di esecuzione, quindi sai dove concentrare i tuoi sforzi.

Esegui sempre i benchmark "prima" e "dopo" : in quale altro modo saprai che le tue ottimizzazioni hanno effettivamente fatto la differenza? Se il tuo codice ottimizzato risulta essere solo leggermente più veloce o più piccolo della versione originale, annulla le modifiche e torna al codice originale, chiaro.

Utilizzare gli algoritmi e le strutture dati corretti: non utilizzare un algoritmo di ordinamento di bolle O (n2) per ordinare migliaia di elementi quando è disponibile un quicksort O (n log n) disponibile. Allo stesso modo, non memorizzare un migliaio di elementi in una matrice che richiede una ricerca O (n) quando è possibile utilizzare un albero binario O (log n) o una tabella di hash Python O (1).

Per ulteriori informazioni visita il link sottostante ... Python Speed ​​Up

Le seguenti 3 notazioni asintotiche sono usate principalmente per rappresentare la complessità temporale degli algoritmi.

1. Θ Notazione : la notazione theta limita una funzione dall'alto e dal basso, quindi definisce il comportamento asintotico esatto. Un modo semplice per ottenere la notazione Theta di un'espressione è di eliminare i termini di ordine basso e ignorare le costanti principali. Ad esempio, considera la seguente espressione. 3n3 + 6n2 + 6000 = Θ (n3) L'eliminazione dei termini di ordine inferiore è sempre soddisfacente perché ci sarà sempre un n0 dopo il quale Θ (n3) ha valori superiori a Θn2) indipendentemente dalle costanti coinvolte. Per una data funzione g (n), denotiamo che Θ (g (n)) sta seguendo un insieme di funzioni. Θ (g (n)) = {f (n): esistono costanti positive c1, c2 e n0 tali che 0 <= c1 g (n) <= f (n) <= c2 g (n) per tutti n> = n0} La definizione sopra indica che se f (n) è theta di g (n), allora il valore f (n) è sempre tra c1 g (n) e c2 g (n) per valori grandi di n (n> = n0). La definizione di theta richiede anche che f (n) debba essere non negativo per valori di n maggiori di n0.

2. Notazione O grande : La notazione O grande definisce un limite superiore di un algoritmo, limita una funzione solo dall'alto. Ad esempio, si consideri il caso di Insertion Sort. Nel caso peggiore ci vuole tempo lineare nel migliore dei casi e nel tempo quadratico. Possiamo tranquillamente affermare che la complessità temporale di Insertion sort è O (n ^ 2). Nota che O (n ^ 2) copre anche il tempo lineare. Se usiamo la notazione to per rappresentare la complessità temporale di Insertion sort, dobbiamo utilizzare due istruzioni per i casi migliori e peggiori:

1. La complessità temporale peggiore di Insertion Sort è Θ (n ^ 2).
2. La migliore complessità del tempo del caso di Insertion Sort è Θ (n).

La notazione Big O è utile quando abbiamo solo il limite superiore alla complessità temporale di un algoritmo. Molte volte troviamo facilmente un limite superiore semplicemente osservando l'algoritmo. O (g (n)) = {f (n): esistono costanti positive c e n0 tali che 0 <= f (n) <= cg (n) per tutto n> = n0}

3. Notazione Ω : proprio come la notazione Big O fornisce un limite superiore asintotico su una funzione, la notazione Ω fornisce un limite inferiore asintotico. Ω Notation <può essere utile quando abbiamo una complessità legata al tempo inferiore di un algoritmo. Come discusso nel post precedente, la migliore performance del caso di un algoritmo non è generalmente utile, la notazione Omega è la notazione meno utilizzata tra tutte e tre. Per una data funzione g (n), denotiamo con Ω (g (n)) l'insieme di funzioni. Ω (g (n)) = {f (n): esistono costanti positive c e n0 tali che 0 <= cg (n) <= f (n) per tutto n> = n0}. Consideriamo lo stesso esempio di Insertion sort qui. La complessità temporale di Insertion Sort può essere scritta come Ω (n), ma non è una informazione molto utile sull'inserimento sort, in quanto siamo generalmente interessati al caso peggiore ea volte nel caso medio.