C++ / estructura de datos

Bienvenidos sean a este post, hoy veremos un resumen sobre la estructura de datos.

Como programadores trabajamos continuamente con estructura de datos. Tomemos como ejemplo los array. Siendo estos utilizados para almacenar y ordenar colecciones de datos pero tambien manejaremos otras estructura de datos para nuestros proyectos. Si sabemos como aplicarlo, esto impacta directamente en la performance de nuestros programas. Por esta razon, es necesario que nos familiaricemos con ellos como son vector, list, map, etc. Vamos a suponer que tenemos un cliente de email, analicemoss las tareas basicas durante su diseño e implementacion.

Tomemos como base que un cliente de email es un programa que enlista correos desde varios remitentes. Tambien se ve envuelto en el envio de correos y no solamente en la recepcion. Vamos a suponer que nos centraremos en el envio y recepcion. Primero, el cliente debe tener la disponibilidad de poder ver todos sus emails en el inbox. Asi como tambien la parte encargada de enviar, reenviar alguno, eliminar los recibidos y los enviados. Vamos a ver un simple struct para crear los objetos email:

struct Email
{
  std::string asunto;
  std::string cuerpo;
  std::string desde;
  std::chrono::time_point datetime;
};

Como pueden ver tenemos unas variables para poder almacenar los distintos datos que tendran cada correo. Pero como podemos almacenar los email? Una forma simple puede ser de la siguiente manera:

const int MAX_EMAILS = 1'000'000;
Email inbox[MAX_EMAILS];

De la manera mas simple como es un array, y para este caso le establecemos un limite de un millon de elementos o emails. Esta es una forma practica de poder tener todos los que necesittemos siempre a mano. Y si bien, al inicio cuando tengamos pocos no tendremos grandes inconvenientes. Cuando lleguemos a una gran cantidad se nos presentaran los primeros inconvenientes. De por si, nuestro primer problema sera como ordenar los emails porque habitualmente se muestra como primer email al ultimo recibido y este sera el ultimo elemento agregado a inbox. Esto hara que surjan los inconvenientes cuando comencemos a trabajar con miles de emails.

Tomemos como ejemplo lo siguiente, necesitamos buscar la palabra amigo en todos nuestros emails. Para ello debemos buscar en todos los emails a aquellos que posean esta palabra y almacenarlos en otro array. Para ello podemos usar el siguiente codigo:

std::vector<Email> buscar(const std::string& palabra) {
  std::vector<Email> resultados;  
  for (todos-los-emails) {
    if (inbox[i].asunto.contains(palabra)) {
      resultados.push_back(inbox[i]);
    }
  }
  return resultados;
}

Esta funcion simple devuelve un objeto de tipo vector y recibe un tipo string con la palabra a buscar. Creamos el objeto y mediante un bucle pasaremos por todos los emails y si el asunto del email posee la palabra a buscar se agrega a resultados y una vez finalizado se devuelve el objeto con todos los resultados. En la vida real, este simple procedimiento puede llevar un tiempo. Ahora vamos a suponer que en el campo asunto tenemos mas palabras, y nosotros debemos comparar la palabra recibida con cada una de ellas. En el peor de los casos, no tenemos ninguna coincidencia. Esto va a derivar en una muy larga espera y desperdicio de procesos de computacion.

Por esta razon, es fundamental elegir la estructura de datos correcta y aplicarlo para mejorar la eficiencia de la aplicacion. Vamos a suponer esto, tenemos una tabla hash que mapea palabras a objetos email. Esto hara que cada palabra sea mapeado a una lista de objetos email que contienen esa palabra. Esto simple enfoque hara que sea mas eficiente porque nuestra funcion de busqueda puede ser de la siguiente manera:

std::vector<Email> buscar(const std::string& palabra) {
  return tabla[palabra];
}

Como pueden ver es mucho mas simple y eficiente sin necesidad de procesar cada elemento pero esto requerira que cada email sea procesado previamente y se mantenga actualizada esa tabla hash. Pero eso se puede hacer al momento de recibir o enviar el email, denigrara un poco la performance pero no sera mas significativo que el metodo anterior de busqueda.

En resumen, hoy hemos visto estructura de datos, que son, por que debemos seleccionarlas correctamente, asi como un ejemplo simple donde podemos ver como seleccionar la estructura de datos correcta puede mejorar la eficiencia. Espero les haya sido de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.