Estructuras de Datos para Network Engineers 101: Introducción

#networking #datastructure #programming #python

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.

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 y Estructura de Datos, esta última, según GeeksForGeeks, 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 o del STP, hasta nuestra propia aplicación de QoS. 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 😉.

# 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 para analizar el tiempo de ejecución, tenemos que.

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

T(n) = \frac{n(n+1)}{2} + \frac{n(n+1)}{2} + n + 1 + 1

T(n) = n(n+1) + n + 2

T(n) = n^2 + 2n + 2

Nota: Cada instrucción está asociada a un costo ( $c_i$ ), 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) de nuestro algoritmo obtendremos que es una Complejidad Exponencial de tipo $O(n) = n^2$ .

Existe una mejor manera, incluso, el algoritmo es más simple y corre en una Complejidad Lineal de tipo $O(n) = n$ .

# 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, esta es denominada Set. 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.

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.

>>> 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.