Optimizacion de Algoritmos y Estructuras de Datos

Optimización de algoritmos¶

El origen de la informática y de la programación requería utilizar lenguajes muy próximos a la máquina. Estos lenguajes recibían el nombre de lenguajes ensamblador o lenguajes máquina. Al programar directamente sentencias a bajo nivel, la eficiencia de estos códigos era muy alta. Sin embargo, la complejidad de desarrollarlos era muy elevada.

Hoy en día podemos utilizar lenguajes de alto nivel, que delegan temas como el acceso a memoria, registros, etc. y que nos permiten no tener que preocuparnos por ello. La única pega que tiene esta abstracción es el problema de desarrollar algoritmos o programas informáticos altamente ineficientes.

¿Qué es un algoritmo?¶

Un algoritmo es un conjunto de instrucciones que se siguen para lograr un objetivo o producir un resultado. Este término no sirve solo para el mundo de la informática. Por ejemplo, la ejecución de tareas cotidianas tan simples como cepillarse los dientes, lavarse las manos o seguir el manual de instrucciones de armado de un mueble, se pueden ver como un algoritmo. En programación, un algoritmo es un conjunto de instrucciones informáticas que constituyen una función.

Veamos un ejemplo de un algoritmo muy sencillo, que permite definir un programa para calcular el área de un triángulo:

Proceso CalcularAreaTriangulo(base, altura)
    Multiplicar la base por la altura;
    Dividir el resultado anterior entre 2;
    Escribir "El área es", area;
FinProceso

Una vez se ha definido el algoritmo, podemos implementarlo en un lenguaje de programación como Python:

In [1]:

def calculate_triangle_area(base, height):
    product = base * height
    area = product / 2
    return f"El área es {area}"

calculate_triangle_area(20, 15)

Out[1]:

'El área es 150.0'

Complejidad temporal de los algoritmos¶

Un problema simple se puede resolver usando muchos algoritmos diferentes. Algunas soluciones simplemente toman menos tiempo y espacio que otras. Pero, ¿cómo sabemos qué soluciones son más eficientes?

La complejidad temporal es el número de operaciones que realiza un algoritmo para completar su tarea (considerando que cada operación dura el mismo tiempo). El algoritmo que realiza la tarea en el menor número de operaciones se considera el más eficiente en términos de complejidad temporal. Normalmente, los lenguajes de programación más utilizados en el análisis de datos como Python, R o Julia tratan de optimizar al máximo la complejidad computacional y es, de hecho, uno de los motivos por los que hay desarrolladores que prefieren uno u otro.

Existen varias definiciones de complejidades temporales:

$O(1)$ - Tiempo constante: La sentencia solo necesita una unidad de tiempo para terminar. Es la mejor medida de todas.
$O(n)$ - Tiempo lineal: La sentencia necesita $n$ unidades de tiempo para realizar la tarea. Si por ejemplo $n = 3$ , la sentencia necesitará $3$ unidades de tiempo para terminar.
$O(n^2)$ - Tiempo cuadrático: La sentencia necesita $n · n$ unidades de tiempo para realizar la tarea. Si por ejemplo $n = 3$ , la sentencia necesitará $3 · 3 = 9$ unidades de tiempo para terminar.
$O(C^n)$ - Tiempo exponencial: La sentencia es muy ineficiente en tiempo. Necesitará una gran cantidad de tiempo para terminar. Es la peor medida de todas.

Hay muchas medidas más para catalogar la eficiencia de las sentencias, y por lo tanto, de los algoritmos. El siguiente gráfico muestra la comparativa entre las medidas más comunes:

Gráfico comparativo de complejidad temporal

Se puede apreciar claramente que el escenario ideal es contar con algoritmos compuestos por sentencias $O(1)$ . Normalmente, Python ya cuenta con muchas de estas optimizaciones y agiliza todos los procesos y funciones, así como en las distintas librerías y paquetes, para que siempre que nosotros utilicemos alguna función sea de una complejidad muy reducida. Sin embargo, algo de lo que nosotros tenemos que ser totalmente responsables y que impacta directamente en el código y que puede afectar a su eficiencia son las buenas prácticas de la programación.

Buenas prácticas de la programación para reducir la complejidad temporal¶

1. Mantente actualizado¶

A medida que el hardware avanza, también lo hace el software. Si los procesadores o las tarjetas gráficas mejoran en capacidades y velocidad, también lo deben hacer los lenguajes de programación. El primer principio de todo buen desarrollador que busque un código eficiente es actualizar constantemente la versión de las librerías y del lenguaje de programación. Así, por ejemplo, Python 3 es mucho más rápido que Python 2, así que parte de esa eficiencia necesaria podrías conseguirla simplemente con la actualización del lenguaje.

2. No programes todo lo que quieras hacer en detalle, apóyate de las librerías¶

Seguramente en algún momento quieras resolver algo en Python y te pondrás manos a la obra, como calcular la media sumando primero los números y luego dividiéndolos por el tamaño total de la muestra. ¿Sabías que esto se puede hacer en una línea utilizando multitud de librerías? Además, normalmente el código que hay detrás de las funciones de estas librerías estará altamente optimizado aprovechando cada recurso disponible, por lo que será más eficiente siempre utilizarlas antes que programar las tuyas propias. Además, el código va a quedar más entendible, limpio y seguramente más escalable.

✅ Hazlo así	❌ No lo hagas así
`np.array([1, 2, 3]).mean()`	`def mean(elements):` `sum = elements.sum()` `n = len(elements)` `return sum/n` `mean(np.array([1, 2, 3]))`
`names['Gender'].replace('female', 'FEMALE', inplace=True)`	`names["Gender'].loc[names.Gender=='female'] = 'FEMALE'`

Esto también aplica a proyectos o aplicaciones que desees realizar. Puede que ya estén hechas con anterioridad y puedas partir de ese proyecto para realizar el tuyo propio. ¿Quieres realizar una calculadora? Investiga, busca a ver si alguien la ha hecho ya en Python y utilízala como punto de partida.

Aquí tienes algunos trucos de los más utilizados y necesarios en el día a día trabajando con datos: https://www.turing.com/kb/22-hottest-python-tricksfor-efficient-coding

3. Utiliza estructuras de datos eficientes¶

Python proporciona muchos mecanismos para realizar tareas computacionalmente y temporalmente eficientes, como se muestra en los siguientes ejemplos:

✅ Hazlo así	❌ No lo hagas así
`def good_list(elements):` `my_list = [value for value in range(elements)]`	`def bad_list(elements):` `my_list = []` `for value in range(elements):` `my_list.append(value)`
`def good_string_joiner(elements):` `"".join(elements)`	`def bad_string_joiner(elements):` `final_string = ""` `for value in elements:` `final_string += value`

Existen muchas formas de optimizar el código, como las que se han mostrado utilizando, en primer lugar, la comprensión de listas (list comprehension), la acumulación de strings utilizando join, collections, itertools...

Más información sobre cómo puedes eficientar al máximo tu código aprovechando las herramientas nativas y paquetes de Python aquí: https://khuyentran1401.github.io/Efficient_Python_tricks_and_tools_for_data_scientists/README.html

4. Elimina lo que no necesites¶

En cualquier lenguaje de programación, las variables y objetos ocupan memoria, de tal forma que una buena forma de mantener el código limpio es eliminar las variables que no vayamos a necesitar más. En Python puedes ver cuánta memoria ocupa tu variable con la función sys.getsizeof(variable) del paquete sys. Si observas que una variable tiene un peso considerable, podrías plantearte eliminarla para no cargar innecesariamente la memoria del entorno de ejecución, ya que cuanto más colapsado esté y más uso de su memoria se haga, peor rendimiento tendrá.

5. Aprende de otros¶

Muchas veces necesitamos inspiración de otros. Puede que hasta antes de haber leído este contenido no sabías que existían mecanismos como la comprensión de listas o la función para calcular la media de NumPy. Por eso, la mejor forma de eficientar el código es aprender del código de otros desarrolladores. La experiencia es la mejor vía hacia la eficiencia.

Buenas prácticas de la programación para mejorar el código¶

Además de haber aprendido sobre buenas prácticas para hacer un código más eficiente en tiempos y en recursos, también las hay para elaborar un código más comprensible y estándar, de forma que facilite el intercambio de conocimiento entre desarrolladores y siga un estándar común. Hay muchas propuestas y guías para elaborar un código en Python, pero la más conocida es la PEP 8 – Style Guide for Python Code, que podrás leer aquí: https://peps.python.org/pep-0008/

Este documento brinda convenciones de codificación para el código de Python que comprende la biblioteca estándar en la distribución principal de Python. Además, esta guía está en constante revisión y evoluciona con el tiempo y las versiones que van saliendo del lenguaje.