Python Language
Vitesse du programme Python

Notation

Idée basique

La notation utilisée pour décrire la vitesse de votre programme Python s'appelle la notation Big-O. Disons que vous avez une fonction:

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

Ceci est une fonction simple pour vérifier si un élément est dans une liste. Pour décrire la complexité de cette fonction, vous allez dire O (n). Cela signifie "Ordre de n" car la fonction O est appelée fonction Ordre.

O (n) - généralement n le nombre d'éléments dans le conteneur

O (k) - généralement k est la valeur du paramètre ou le nombre d'éléments du paramètre

Opérations de liste

Opérations: Cas moyen (suppose que les paramètres sont générés aléatoirement)

Append: O (1)

Copie: O (n)

Del slice: O (n)

Supprimer l'article: O (n)

Insérer: O (n)

Obtenir l'article: O (1)

Set item: O (1)

Itération: O (n)

Obtenir une tranche: O (k)

Définir la tranche: O (n + k)

Étendre: O (k)

Trier: O (n log n)

Multiplier: O (nk)

x dans s: O (n)

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

Longueur: O (1)

Opérations de deque

Un deque est une file d'attente double.

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)

Opérations: Cas moyen (suppose que les paramètres sont générés aléatoirement)

Append: O (1)

Appendleft: O (1)

Copie: O (n)

Étendre: O (k)

Extendleft: O (k)

Pop: O (1)

Popleft: O (1)

Supprimer: O (n)

Rotation: O (k)

Définir les opérations

Operation: Average Case (suppose des paramètres générés aléatoirement): le pire des cas

x dans s: O (1)

Différence s - t: O (len (s))

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

Intersection multiple s1 & s2 & s3 & ... & sn:: (n-1) * O (l) où l est 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))

Différence symétrique s ^ t: O (len (s)): O (len (s) * len (t))

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

Notations algorithmiques ...

Certains principes s'appliquent à l'optimisation dans tout langage informatique, et Python ne fait pas exception. N'optimisez pas au fur et à mesure : écrivez votre programme sans vous soucier des optimisations possibles, en vous concentrant plutôt sur le fait que le code est propre, correct et compréhensible. Si c'est trop gros ou trop lent lorsque vous avez terminé, alors vous pouvez envisager de l'optimiser.

Rappelez-vous la règle des 80/20 : dans de nombreux domaines, vous pouvez obtenir 80% du résultat avec 20% de l'effort (également appelé la règle 90/10 - cela dépend de qui vous parlez). Chaque fois que vous êtes sur le point d'optimiser le code, utilisez le profilage pour savoir où se situe 80% du temps d'exécution, afin de savoir où concentrer vos efforts.

Exécutez toujours des tests "avant" et "après" : comment saurez-vous que vos optimisations ont fait une différence? Si votre code optimisé s'avère être légèrement plus rapide ou plus petit que la version d'origine, annulez vos modifications et revenez au code d'origine.

Utilisez les bons algorithmes et structures de données: N'utilisez pas un algorithme de tri par bulles O (n2) pour trier un millier d'éléments lorsqu'un test rapide O (n log n) est disponible. De même, ne stockez pas un millier d'éléments dans un tableau qui nécessite une recherche O (n) lorsque vous pouvez utiliser un arbre binaire O (log n) ou une table de hachage Python O (1).

Pour plus de détails, visitez le lien ci-dessous ... Python Speed ​​Up

Les trois notations asymptotiques suivantes sont principalement utilisées pour représenter la complexité temporelle des algorithmes.

1. Ation Notation : La notation thêta délimite une fonction de haut en bas, elle définit donc un comportement asymptotique exact. Un moyen simple d'obtenir la notation Theta d'une expression consiste à supprimer les termes d'ordre faible et à ignorer les constantes principales. Par exemple, considérons l'expression suivante. 3n3 + 6n2 + 6000 = Θ (n3) L'abandon des termes d'ordre inférieur est toujours correct car il y aura toujours un n0 après lequel Θ (n3) aura des valeurs supérieures à Θn2) quelles que soient les constantes impliquées. Pour une fonction donnée g (n), on note Θ (g (n)) est le jeu de fonctions suivant. Θ (g (n)) = {f (n): il existe des constantes positives c1, c2 et n0 telles que 0 <= c1 g (n) <= f (n) <= c2 g (n) pour tout n> = n0} La définition ci-dessus signifie que si f (n) est thêta de g (n), alors la valeur f (n) est toujours comprise entre c1 g (n) et c2 g (n) pour les grandes valeurs de n (n> = n0). La définition de thêta exige également que f (n) soit non négatif pour les valeurs de n supérieures à n0.

2. Notation Big O : La notation Big O définit une limite supérieure d'un algorithme, elle limite une fonction uniquement par le haut. Par exemple, considérons le cas du tri par insertion. Dans le meilleur des cas, cela prend du temps linéaire dans le meilleur des cas et du temps quadratique. On peut dire sans se tromper que la complexité temporelle du tri par insertion est O (n ^ 2). Notez que O (n ^ 2) couvre également le temps linéaire. Si nous utilisons la notation Θ pour représenter la complexité temporelle du tri par insertion, nous devons utiliser deux instructions pour le meilleur et le pire des cas:

1. La pire complexité temporelle du tri par insertion est Θ (n ^ 2).
2. La meilleure complexité temporelle du tri par insertion est Θ (n).

La notation Big O est utile lorsque la complexité temporelle d'un algorithme est uniquement liée à la limite supérieure. Souvent, nous trouvons facilement une limite supérieure en regardant simplement l'algorithme. O (g (n)) = {f (n): il existe des constantes positives c et n0 telles que 0 <= f (n) <= cg (n) pour tout n> = n0}

3. Notation Ω : Tout comme la notation Big O fournit une borne supérieure asymptotique sur une fonction, la notation Ω fournit une borne inférieure asymptotique. Ω Notation <peut être utile lorsque la complexité temporelle d’un algorithme est inférieure. Comme discuté dans le post précédent, la meilleure performance d'un algorithme n'est généralement pas utile, la notation Omega est la notation la moins utilisée parmi les trois. Pour une fonction donnée g (n), on note Ω (g (n)) l'ensemble des fonctions. Ω (g (n)) = {f (n): il existe des constantes positives c et n0 telles que 0 <= cg (n) <= f (n) pour tout n> = n0}. Considérons ici le même exemple de tri par insertion. La complexité temporelle du tri par insertion peut être écrite comme Ω (n), mais ce n'est pas une information très utile sur le tri par insertion, car nous sommes généralement intéressés par le pire des cas et parfois le cas moyen.