Python Language
Velocidad de Python del programa.

Notación

Idea básica

La notación utilizada al describir la velocidad de su programa Python se llama notación Big-O. Digamos que tienes una función:

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

Esta es una función simple para verificar si un elemento está en una lista. Para describir la complejidad de esta función, dirá O (n). Esto significa "Orden de n", ya que la función O se conoce como la función Orden.

O (n): generalmente n es el número de elementos en el contenedor

O (k): generalmente k es el valor del parámetro o el número de elementos en el parámetro

Lista de operaciones

Operaciones: Caso promedio (se supone que los parámetros se generan aleatoriamente)

Anexo: O (1)

Copia: O (n)

Del slice: O (n)

Eliminar elemento: O (n)

Insertar: O (n)

Obtener artículo: O (1)

Elemento de ajuste: O (1)

Iteración: O (n)

Obtener rebanada: O (k)

Establecer rebanada: O (n + k)

Extender: O (k)

Ordenar: O (n log n)

Multiplicar: O (nk)

x en s: O (n)

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

Obtener longitud: O (1)

Operaciones de deque

Un deque es una cola de doble final.

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)

Operaciones: Caso promedio (se supone que los parámetros se generan aleatoriamente)

Anexo: O (1)

Apéndice: O (1)

Copia: O (n)

Extender: O (k)

Extendente: O (k)

Pop: O (1)

Personas: O (1)

Eliminar: O (n)

Girar: O (k)

Establecer operaciones

Operación: Caso promedio (asume parámetros generados aleatoriamente): Peor caso

x en s: O (1)

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

Intersección s & t: O (min (len (s), len (t))): O (len (s) * len (t)

Intersección múltiple s1 & s2 & s3 & ... & sn:: (n-1) * O (l) donde l es 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))

Diferencia simétrica s ^ t: O (len (s)): O (len (s) * len (t))

Unión s | t: O (len (s) + len (t))

Notaciones algorítmicas ...

Hay ciertos principios que se aplican a la optimización en cualquier lenguaje de computadora, y Python no es una excepción. No optimice a medida que avanza : escriba su programa sin importar las posibles optimizaciones, concentrándose en asegurarse de que el código sea limpio, correcto y comprensible. Si es demasiado grande o demasiado lento cuando haya terminado, entonces puede considerar optimizarlo.

Recuerde la regla 80/20 : en muchos campos puede obtener el 80% del resultado con el 20% del esfuerzo (también llamada regla 90/10 - depende de con quién hable). Cuando esté a punto de optimizar el código, use la creación de perfiles para averiguar a dónde va ese 80% del tiempo de ejecución, para que sepa dónde concentrar su esfuerzo.

Ejecute siempre los puntos de referencia "antes" y "después" : ¿De qué otra manera sabrá que sus optimizaciones realmente hicieron una diferencia? Si su código optimizado resulta ser solo un poco más rápido o más pequeño que la versión original, deshaga los cambios y vuelva al código original y sin cifrar.

Use los algoritmos y las estructuras de datos correctos: No use un algoritmo de clasificación de burbuja O (n2) para ordenar mil elementos cuando haya una ordenación rápida O (n log n) disponible. Del mismo modo, no almacene mil elementos en una matriz que requiera una búsqueda O (n) cuando podría usar un árbol binario O (log n) o una tabla hash O (1) de Python.

Para más información, visite el siguiente enlace ... Python Speed ​​Up

Las siguientes 3 notaciones asintóticas se usan principalmente para representar la complejidad del tiempo de los algoritmos.

1. Θ Notación : la notación theta limita las funciones desde arriba y desde abajo, por lo que define el comportamiento asintótico exacto. Una forma sencilla de obtener la notación Theta de una expresión es eliminar los términos de orden inferior e ignorar las constantes iniciales. Por ejemplo, considere la siguiente expresión. 3n3 + 6n2 + 6000 = Θ (n3) La eliminación de los términos de orden inferior siempre está bien porque siempre habrá un n0, luego de lo cual Θ (n3) tiene valores más altos que Θn2) independientemente de las constantes involucradas. Para una función dada g (n), denotamos que Θ (g (n)) está siguiendo un conjunto de funciones. Θ (g (n)) = {f (n): existen constantes positivas c1, c2 y n0 tales que 0 <= c1 g (n) <= f (n) <= c2 g (n) para todo n> = n0} La definición anterior significa que si f (n) es theta de g (n), entonces el valor f (n) siempre está entre c1 g (n) y c2 g (n) para valores grandes de n (n> = n0). La definición de theta también requiere que f (n) no sea negativa para valores de n mayores que n0.

2. Notación Big O : La notación Big O define un límite superior de un algoritmo, limita una función solo desde arriba. Por ejemplo, considérese el caso de Insertion Sort. Lleva tiempo lineal en el mejor de los casos y el tiempo cuadrático en el peor de los casos. Podemos decir con seguridad que la complejidad temporal de la ordenación de inserción es O (n ^ 2). Tenga en cuenta que O (n ^ 2) también cubre el tiempo lineal. Si usamos la notación para representar la complejidad de tiempo de la ordenación por Inserción, tenemos que usar dos afirmaciones para el mejor y el peor de los casos:

1. La complejidad en el peor de los casos de Insertion Sort es Θ (n ^ 2).
2. El mejor caso de complejidad en el tiempo de Insertion Sort es Θ (n).

La notación Big O es útil cuando solo tenemos un límite superior en la complejidad de tiempo de un algoritmo. Muchas veces encontramos fácilmente un límite superior simplemente mirando el algoritmo. O (g (n)) = {f (n): existen constantes positivas c y n0 tales que 0 <= f (n) <= cg (n) para todos n> = n0}

3. Ω Notación : al igual que la notación Big O proporciona un límite superior asintótico en una función, la notación provides proporciona un límite inferior asintótico. Ω La notación <puede ser útil cuando tenemos un límite inferior en la complejidad del tiempo de un algoritmo. Como se discutió en la publicación anterior, el mejor rendimiento de un algoritmo generalmente no es útil, la notación Omega es la notación menos utilizada entre las tres. Para una función dada g (n), denotamos por Ω (g (n)) el conjunto de funciones. Ω (g (n)) = {f (n): existen constantes positivas c y n0 tales que 0 <= cg (n) <= f (n) para todos n> = n0}. Consideremos el mismo ejemplo de orden de inserción aquí. La complejidad temporal de la clasificación de inserción se puede escribir como Ω (n), pero no es una información muy útil sobre la clasificación de inserción, ya que generalmente estamos interesados ​​en el peor de los casos y, a veces, en el caso promedio.