En varias ocasiones, durante entrevistas técnicas a candidatos para puestos de Ingeniero/a o Desarrolladora de Software en la empresa donde trabajaba, me he encontrado con personas que realmente saben cómo filtrar o ordenar una lista. Sin embargo, cuando profundizo en la complejidad del problema, comienzan a surgir dificultades.

Muchas veces, como desarrolladores de software, nos acostumbramos a utilizar bibliotecas y APIs que ya tienen soluciones complejas implementadas en una sola función, lo que facilita nuestras vidas. Esto no significa que debemos dejar de lado nuestra curiosidad y capacidad para investigar cómo funcionan las cosas, al menos en su forma más básica.

En este post, vamos a analizar específicamente una función muy utilizada de la API de Kotlin: distinctBy.

Puedes encontrar la documentación oficial haciendo click en este link.

Aplicando el algoritmo en la vida real

Supongamos que tienes una lista de productos en la cual, por razones no relevantes para este post, existen elementos repetidos. Claramente, no queremos mostrar al usuario una lista de elementos duplicados. Por lo tanto, sabemos que debemos filtrar la lista.

Tenemos un par de alternativas:

Filtrando la lista con un loop

Podríamos instanciar una nueva lista vacía y recorrer la lista original, agregando elemento por elemento solo si el elemento actual de la iteración no se encuentra en esta nueva lista.

Aquí tenemos un pequeño problema, que “solo si no se encuentra en esta nueva lista” implica una búsqueda. Supongamos que no hemos utilizado un hash table y estamos utilizando un simple ArrayList.

Tendríamos algo como esto:

/**
 * Recorre la lista [products] y adiciona elementos
 * únicos a una lista nueva. Finalmente se devuelve
 * esta lista nueva.
 */
fun filterList(products: List): List {
   val newList = emptyList()
   products.forEach { product ->
       if(findProduct(products, product) == false) {
           newList.add(product)
       }
   }
   return newList
}

/**
 * Dada una lista [list], devuelve true si se encuentra
 * el [productToFind] en esta lista.
 */  
fun findProduct(list: List, productToFind: Product): Boolean {
   list.forEach { product ->
       if(product.id == productToFind.id) {
           return true
       }
   }
   return false
}

Realizando un análisis rápido, la función filterList llamará a la función findProduct N veces, donde N es el número de elementos en la lista original.

La función findProduct tomará hasta N veces para completarse. Suponiendo que el elemento a buscar se encuentra en la última posición de la lista, el peor caso (worst case scenario) será O(n).

Esto significa que la complejidad de nuestro algoritmo será O(n²). Es decir, podría tomar n² unidades de tiempo para terminar. Y si hablamos de Consumo de Memoria (espacio), tendremos una nueva lista, que es O(n).

Filtrando la lista con la función distinctBy

Genial. Resulta que conocemos la existencia de una función llamada distinctBy en la cual debemos pasarle como parámetro una función que indique el “key” que servirá como indicador de si un elemento está repetido o no. Esto puede ser un nombre, un apellido o un código.

Solo necesitamos escribir:

val newList = products.distinctBy { product -> product.code }

Y, voilá!

Listo, una sola línea de código fue suficiente y ya tenemos una nueva lista que no contiene productos repetidos con el mismo código.

Pero… ¿sabemos qué hace internamente?

Analicemos el código fuente de esta función.

Como podemos ver, es una función de extensión inline aplicable a cualquier estructura de datos que implemente la interfaz Iterable.

Esta función depende de dos clases genéricas que necesitará para su funcionamiento: una que determina los tipos de datos de la lista a devolver (los mismos que la lista original) denotados por la letra T, y otra que determina el diferenciador de los objetos, denotado con la letra K.

En las dos primeras líneas se instancian dos nuevos objetos. El primero es una estructura de datos hash table o diccionario que a su vez implementa la interfaz Set (HashSet): no permitirá elementos repetidos gracias a que contiene una hash table o tabla de hash internamente. El segundo es una lista simple que servirá como la lista filtrada resultante.

Itera sobre la lista original (mostrada como this en la instrucción for) y ejecuta la función selector que se pasa como parámetro. Esta función selector recibe el elemento actual de la iteración.

Eso significa que en cada iteración, la función { product -> product.code } estará devolviendo lo que queremos usar como identificador único para cada elemento de la lista, por eso su valor se asigna a una variable llamada “key”.

Una vez que obtenemos este identificador único (que en nuestro ejemplo es el código del producto), procedemos a insertarlo en nuestra hash table.

Como podemos ver, esta inserción ocurre dentro de un condicional if.

La interfaz Set establece que la función add devolverá true si, y solo si, el elemento fue insertado. ¿Y en qué momento el elemento no se inserta? Bueno, cuando ya existe (se verifica con una tabla de hash).

O preguntado al revés: ¿Cuándo sí se inserta el elemento? Pues cuando este elemento NO existe en la tabla de hash.

Una vez que sabemos que este identificador no existía en nuestra hash table de IDs (set.add(key) devuelve true), entonces procedemos a insertar el elemento (el producto) en nuestra nueva lista (list.add(e)).

No se realiza una búsqueda para verificar si el elemento de la iteración ya existe en la lista. Solo intentamos insertar su identificador (el código del producto) en la hash table y si esta operación es exitosa (devuelve true), entonces simplemente agregamos este producto a la lista filtrada.

Dado que se itera toda la lista original de todos modos, la complejidad temporal será O(n), sin embargo, la verificación de si un elemento ya existe o no en la lista se devuelve en tiempo constante O(1), gracias a nuestra hash table dentro de nuestro HashSet que nos dirá si el ID fue insertado o no.

Por supuesto, al crear dos nuevos objetos, el espacio de memoria utilizado será un poco mayor, pero no tan relevante, ya que el propósito del HashSet es almacenar solo los identificadores para saber si un elemento ya existe o no en la lista original.

Resumen

  1. La función distinctBy utiliza una estructura HashSet para acelerar el costo temporal con la verificación de la existencia de un elemento en nuestra lista.

  2. A diferencia de un HashMap, un HashSet solo necesita un elemento en el momento de la inserción y no puede repetirse, actúa como clave y valor al mismo tiempo (en realidad, si observamos la implementación interna, se utiliza un objeto genérico estático Object como valor).

  3. Por supuesto, distinctBy nos ofrece un mejor rendimiento que si optáramos por una implementación de dos iteraciones, una dentro de la otra. Sin embargo, también podríamos haber utilizado un HashMap e insertado sobre él utilizando el código del producto como clave y el producto como valor. El resultado sería una estructura de productos sin duplicados.

¿Qué te pareció? ¿También analizas con frecuencia las funciones que utilizamos a diario y que nos facilitan la vida? Me gustaría saber si conoces alguna otra función o API que también haga uso de estas estructuras de datos de manera eficiente y simplifique nuestro día a día desarrollando software 😄.