Comprender la eficacia del código

Completados

Comprender la eficacia del código

Dos funciones pueden resolver el mismo problema y ejecutarse a velocidades muy diferentes. La diferencia procede del algoritmo, que es el conjunto de pasos que sigue el código.

Considere la posibilidad de buscar un nombre en una libreta de teléfonos con 1 millón de nombres:

  • Enfoque 1: Compruebe todas las páginas en orden hasta que encuentre el nombre. En el peor de los casos, esto toma 1 millón de verificaciones.
  • Enfoque 2: Use el orden alfabético. Abra la página central, decida si el nombre viene antes o después de ella y descarte la mitad de los nombres. Repita. Esto encuentra cualquier nombre en unas 20 comprobaciones.

El problema es el mismo, pero el segundo enfoque hace mucho menos trabajo. Esto es eficiencia algorítmica.

Describa el crecimiento con notación Big O

La notación big O describe cómo crece el número de pasos que toma un algoritmo a medida que crecen los datos. No mide el tiempo en milisegundos. Se describe un patrón que puede usar para comparar algoritmos.

O(1): tiempo constante

El número de pasos no cambia cuando crecen los datos.

def get_first_item(my_list):
    return my_list[0]

Obtener el primer elemento tarda el mismo tiempo en una lista de 10 o 10 millones de elementos.

O(n): tiempo lineal

El número de pasos aumenta en proporción a los datos.

def find_maximum(my_list):
    max_value = my_list[0]
    for item in my_list:
        if item > max_value:
            max_value = item
    return max_value

El bucle se ejecuta una vez para cada elemento. Con 100 elementos, se ejecuta 100 veces. Con 1 millón de elementos, se ejecuta 1 millón de veces.

O(n²): tiempo cuadrático

El número de pasos crece con el cuadrado de los datos. Los bucles anidados sobre los mismos datos son una causa común.

def find_duplicates(my_list):
    duplicates = []
    for i in range(len(my_list)):
        for j in range(i + 1, len(my_list)):
            if my_list[i] == my_list[j]:
                duplicates.append(my_list[i])
    return duplicates

La función compara cada elemento con cada elemento después de él. Con 100 elementos, son aproximadamente 5.000 comparaciones. Con 1.000 elementos, es aproximadamente 500.000 comparaciones. Diez veces más datos significa aproximadamente 100 veces más trabajo.

Comparar los patrones

En la tabla siguiente se muestra lo que sucede con el número de pasos al duplicar los datos:

Pattern Nombre Efecto de duplicar los datos
O(1) Constante No hay cambio.
O(n) Lineal El trabajo se duplica.
O(n²) Cuadrático El trabajo se cuadruplica.

Para una lista de 1 millón de elementos, un algoritmo de O(n) toma aproximadamente 1 millón de pasos. Un algoritmo O(n²) requiere aproximadamente 1 billón de pasos, lo que puede ser poco práctico.

La elección del algoritmo suele ser más importante que pequeños cambios en el código. Un algoritmo O(n²) lento acaba perdiendo frente a un algoritmo O(n), sin importar lo cuidadosamente que lo ajuste.

Decidir cuándo importa la eficiencia

No todas las funciones tienen que ser eficientes. Hazte estas preguntas:

  • ¿Los datos se vuelven grandes, por ejemplo, con más de unos pocos miles de elementos?
  • ¿La función se ejecuta con frecuencia?
  • ¿Hay un enfoque diferente que requiera menos trabajo?

Una función O(n²) que procesa 10 elementos una vez está bien. La misma función en una búsqueda que se ejecuta miles de veces en millones de elementos es un problema grave.