Estructuras de Datos para Network Engineers 101: Introducción
Tags: networking, datastructure, programming, python
Published: 2021-04-12 04:11:29

Hoy en día, tres conceptos están tomando auge en el mundo del _Networking_ y _IT_: Software Defined Network (ó Redes Definidas Por Software), Network Automation (ó Automatización de Redes) y Network Orquestation (u Orquestación de Redes). Estos se pueden involucrar entre sí, sin embargo, [sería un pecado capital confundirlos](https://etherealmind.com/difference-sdn-automation-orchestraton/). 

Debido a los nuevos paradigmas emergentes, muchos ingenieros se han tenido que tomar la tarea de aprender a programar. No todo es tan fácil a la hora de hacer este trabajo, existen conocimientos que debemos tener para que el proceso no resulte tan frustrante a la hora de diseñar una aplicación y verla funcionando, me refiero a conocimientos acerca de [Algoritmos](https://concepto.de/algoritmo-en-informatica) y Estructura de Datos, esta última, según [GeeksForGeeks](https://www.geeksforgeeks.org/data-structures/), no es más que una forma particular de organizar los datos en una computadora, de manera que estos puedan ser accedidos y utilizados de una manera **eficiente**.

A veces solemos queremos automatizar tareas en nuestra red, o también brindar un servicio que utilice la automatización como medio operativo, o tal vez quisiéramos implementar nuestra propia versión del protocolo [OSPF](https://es.wikipedia.org/wiki/Open_Shortest_Path_First) o del [STP](https://es.wikipedia.org/wiki/Spanning_tree), hasta nuestra propia aplicación de [QoS](https://es.wikipedia.org/wiki/Calidad_de_servicio). Para hacer todas estas cosas es necesario conocer **Estructuras de Datos** como Linked List, Queues, Stacks, Hash Tables, Graphs, Binary Trees, entre otras más. Afortunadamente, este es el primer post de otros más que vendrán en esta serie llamada _Estructuras de Datos para Network Engineers 101_, y estas estructuras ya mencionadas las estaremos viendo a lo largo del camino. Es bueno aclarar que no profundizaré a tal nivel que termines siendo un experto en el manejo de esas estructuras que te mencioné, pero si tendrás fundamentos sólidos para llegar a serlo con tu propia práctica.

Te pongo un ejemplo que quizás te motive a seguir leyendo: supón que estás automatizando una tarea en tu red, y en un fragmento de tu código necesitas filtrar una lista de IPs que pueda contener las mismas IPs más de una vez, de modo que las IPs no se repitan. Si tu primer approach sería hacer algo más o menos como lo que vamos a hacer a continuación, entonces esta serie es ideal para ti. Si pensaste en una manera más óptima de resolver el problema, también, te invito que te quedes, quizás aprendas algo nuevo más adelante, nadie sabe :wink:.

```python
# No tan cool :p
def remove_duplicated(l: list)->list:
	filtered_list = []
	for ip in l:
		if ip not in filtered_list:
			filtered_list.append(ip)
	return filtered_list
```
En pocas palabras lo que se intenta hacer es _recorrer la lista e ir almacenando cada Ip en otra lista nueva, si esta Ip ya está almacenada, entonces no se añade_. Realmente el algoritmo es correcto, y va a funcionar, el problema es que en el mundo del software no es suficiente con que el las aplicaciones solamente funcionen, sino que también sean eficientes a nivel de rendimiento. La idea es que tu código corra lo más óptimo posible cuando tenga entradas de miles de datos y necesite entrar a decenas de equipos en tu red de una manera muy rápida.

A continuación, te mostraré la razón de la ineficiencia del algoritmo concebido, pero no te asustes si no entiendes, no utilizaremos este método a lo largo de la serie ya que trataré de explicarte todo con cucharita y de la forma más clara y resumida posible. Cabe destacar que sí es importante que te tomes un tiempo para aprender a analizar algoritmos, lo agradecerás en un futuro.

Usando el [Modelo de la RAM](https://medium.com/@_SD10_/the-ram-model-of-computation-and-big-o-notation-a1b3cc50ec2c) para analizar el tiempo de ejecución, tenemos que.

|Instrucción|Veces que se repite|
|-----------|-------------------|
| `filtered_list = []`  |{% katex inline %} 1 {% endkatex %}|
| `for ip in l`  |{% katex inline %} n {% endkatex %}|
| `if ip not in filtered_list`  |{% katex inline %}\frac{n(n+1)}{2}{% endkatex %}|
| `filtered_list.append(ip)`  |{% katex inline %}\frac{n(n+1)}{2}{% endkatex %}|
| `return filtered_list`  |{% katex inline %} 1 {% endkatex %}|

{% katex %} T(n) = \frac{n(n+1)}{2} + \frac{n(n+1)}{2} + n + 1 + 1  {% endkatex %}
{% katex %} T(n) = n(n+1) + n + 2  {% endkatex %}
{% katex %} T(n) = n^2 + 2n + 2  {% endkatex %}

> _**Nota**: Cada instrucción está asociada a un costo ({% katex inline %} c_i {% endkatex %}), el cual no es más que una cantidad de pasos que toma para ejecutarse, pero para fines de explicación lo vamos a obviar asumiendo que es 1 para todas las instrucciones, esto para no complicar el asunto._

Si analizamos el [Time Complexity (ó Complejidad Temporal)](https://es.wikipedia.org/wiki/Complejidad_temporal) de nuestro algoritmo obtendremos que es una [Complejidad Exponencial](https://guias.makeitreal.camp/algoritmos/complejidad#complejidad-exponencial-o-n-2-o-n-3-etc) de tipo {% katex inline %} O(n) = n^2 {% endkatex %}.

Existe una mejor manera, incluso, el algoritmo es más simple y corre en una [Complejidad Lineal](https://guias.makeitreal.camp/algoritmos/complejidad#complejidad-lineal-o-n) de tipo {% katex inline %} O(n) = n {% endkatex %}.
```python
# muy cool :p
filtered_list = list(set(l))

# Dependiendo de las operaciones que necesitemos hacer sobre
# el iterable, podemos olvidarnos de convertir el set a lista.
```
Esta mejora en nuestro algoritmo se debe a que se supo utilizar una estructura de datos adecuada para los fines, la cual está basada en [conjuntos numéricos](https://es.wikipedia.org/wiki/Conjunto), esta es denominada [Set](https://tutorialedge.net/compsci/data-structures/sets-for-beginners/). No vamos a hablar mucho ahora de esta Estructura de Datos, por lo que sólo nos quedaremos sabiendo que no permite elementos repetidos en ella.

Si no has entendido nada de lo que se explicó arriba sobre _Big O Notation_, _Time Complexity_ y/o _Time Execution_, entonces tienes mucho que leer. [Te recomiendo este libro para iniciar](https://www.amazon.com/-/es/Thomas-H-Cormen-ebook-dp-B08FH8N996/dp/B08FH8N996/ref=mt_other?_encoding=UTF8&me=&qid=).

Mientras tanto, en lo que el hacha va y viene, te lo voy a explicar de una manera sencilla: El primer algoritmo concebido es ineficiente delante del segundo. ¡Listo!. Esto es culpa de la Estructura de Datos seleccionada, ya que el algoritmo que concibamos dependerá mucho de esto. Y no es que sea una mala Estructura de Datos, lo que pasa es que no es la más adecuada para los fines.

```python
>>> from timeit import timeit
>>> my_ips = ['192.168.1.1', '192.168.1.2', '192.168.2.1', '192.168.2.2', '192.168.3.1', '192.168.3.2', '192.168.4.1', '192.168.4.2', '192.168.5.1', '192.168.5.1']
>>> timeit(lambda: remove_duplicated(my_ips), number=1000) # Tiempo en segundos
0.0016276000000061686
>>> timeit(lambda: list(set(my_ips)), number=1000) # Tiempo en segundos
0.0004897999999684544
```
> _**Nota**: En este ejemplo se utilizaron las condiciones para recrear el peor caso de ejecución para el algoritmo, es decir, donde no se repite ninguna IP y este tenga que correr todas las instrucciones._

Pudimos ver como tomamos de ejemplo 10 IPs y se nota la diferencia en el tiempo de ejecución, de hecho, no es más grande porque la cantidad IPs de entrada es relativamente pequeña comparada con miles que nuestro código pudiera recibir. 

Por esto es importante saber sobre Estructuras de Datos, pueden hacer más ligeras las cosas, también, nos ayudan a concebir buenos algoritmos para tratar los problemas de una manera más fácil. 

Voy a tratar de enseñarte a través de ejemplos prácticos, la mayoría de estos aplicados al mundo del _Networking_, publicaré el código de lo que vamos a hacer en cada post y te explicaré cómo funciona, fragmento por fragmento, de una manera resumida claro está. La idea es que no dures demasiado leyendo un post que te vaya a agobiar, sería mejor que pases más tiempo profundizando por tu parte lo que voy a explicar, esto lo harás con los fundamentos que te enseñaré en cada post. Trataré de utilizar un lenguaje muy llano y divertido, para que no te canses si no entiendes algo, además, cualquier duda que tengas puede ser depositada en los comentarios y yo me tomaré de vez en cuando el tiempo para responderlas.

Entonces, si tengo tu atención, te recomiendo el siguiente post, el cual dará inicio formal a la serie y te introducirá a la primera Estructura de Datos a tratar.

<a href="https://www.buymeacoffee.com/jorgmassih"><img src="https://img.buymeacoffee.com/button-api/?text=Buy me a coffee here&emoji=⌨️&slug=jorgmassih&button_colour=5F7FFF&font_colour=ffffff&font_family=Lato&outline_colour=000000&coffee_colour=FFDD00"></a>