Superando la comprobación estricta en Set y Map

Set y Map son unas de los mejores y más útiles manejadores de estructuras de datos que nos ofrece Javascript. Gracias a ellos podemos crear diccionarios bien estructurados y resolver algunas de las complejidades y limitaciones de modelo ofrecido por objetos y matrices. No obstante, tienen una importante limitación, las claves en el caso de Map y los valores en el caso de Set se evalúan con una comparación estricta del tipo === y esto puede ser inadecuado para algunos casos de uso.

Por ejemplo, si tenemos una lista de fechas y queremos eliminar los duplicados de esta, podemos pensar en utilizar Set, que no permite valores duplicados en su contenido. Como las fechas son objetos en Javascript, y al realizarse una comparación estricta, no se estaría evaluando si dos objetos son equivalentes o tienen el mismo valor, se está comprobando que son exactamente el mismo objeto, que no es lo que nos interesa en este caso.

const dates = [
  new Date(2019,0,1),
  new Date(2019,0,1), // Duplicated value
  new Date(2019,0,2),
  new Date(2019,0,3),
  new Date(2019,0,4),
  new Date(2019,0,5)
];

const uniqueDates = new Set(dates);

console.assert(uniqueDates.size === 5);

En este caso particular podríamos convertir las fechas en valores numéricos antes de incorporarlos en el objeto Set, pero también podemos crear una nueva versión extendida de Set que permita indicar cómo queremos hacer la comprobación de equivalencia entre los valores existentes y los nuevos valores que se desean añadir.

Nota importante: incorporar una función de comprobación de equivalencia entre los valores existentes y nuevos hace que el algoritmo pase de una complejidad constante O(1) que tenemos cuando usamos Set a una complejidad lineal O(n). Esto quiere decir que, cuanto más elementos tengamos en el objeto Set, el tiempo de ejecución irá creciendo de forma muy significativa cuando incorporamos la función de comprobación, ya que tiene que revisar la existencia del nuevo valor en todos los elementos ya existentes. Es importante tener en cuenta este aumento de complejidad y, por lo tanto, de tiempo de ejecución, antes de usar esta aproximación. Te recomendamos que leas nuestro artículo Corregir la complejidad lineal en nuestra propuesta de superación de la comprobación estricta en Set y Map donde explicamos cómo donde resolver los problemas que esta primera aproximación presenta.

Para ello lo primero que vamos a hacer es crear una clase eqSet que extiende de la clase Set nativa de Javascript. Aunque hay quien considera la herencia un antipatrón, es decir, algo que debemos evitar, lo cierto es que este tipo de extensión es muy útil y nos permite crear una versión de Set con un comportamiento específico.

class eqSet extends Set {
}

A esta clase le vamos a añadir un constructor que recibe dos parámetros, el primero sería el iterador que puede recibir Set como parámetro y que le pasaremos al constructor original en la llamada super(), y un segundo parámetro donde recibiremos la función para hacer las comprobaciones. Como el iterador inicial es opcional, tenemos que comprobar si se ha pasado la función como primer parámetro, lo cual complica un poco nuestro código, pero no demasiado:

const CHECKER = Symbol ();

class eqSet extends Set {
  constructor (iterable, checker) {
    if (typeof iterable === 'function') {
      checker  = iterable;
      iterable = undefined;
    }
    super (iterable);
    this[ CHECKER ] = checker;
  }
}

Lo que hemos hecho es guardar la función checker, que vamos a utilizar para comprobar si algún valor ya existe en el objeto Set, en una propiedad del objeto con un Symbol. De esta forma la función está disponible para cualquier método del objeto, pero no es fácilmente visible desde fuera del mismo. (ver Symbol: la privacidad que no es y Clases: nombres y símbolos).

Ahora lo que tenemos que hacer es sobre escribir los tres métodos de Set que reciben valores y utilizar la función de comprobación para saber si existen o no en el objeto. Para ello hacemos uso de this.values() que devuelve un interador con los valores, con un simplemente […this.values()] convertimos este iterador en una matriz sobre la que podemos hacer .find() pasando la función de comprobación. Con el resultado llamaremos a los métodos originales de Set por medio de super.metodo() para realizar cada operación.

const CHECKER = Symbol ();

class eqSet extends Set {
  constructor (iterable, checker) {
    if (typeof iterable === 'function') {
      checker  = iterable;
      iterable = undefined;
    }
    super (iterable);
    this[ CHECKER ] = checker;
  }
  
  add (value) {
    return super.add (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v)) || value
    );
  }
  
  delete (value) {
    return super.delete (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v))
    );
  }
  
  has (value) {
    return super.has (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v)) || value
    );
  }
  
}

Si intentamos ejecutar este código va a pasar algo muy interesante. La llamada a super() del constructor va a llamar a add() de nuestra clase y se va a encontrar que [CHECKER] todavía no ha sido asignado, lanzando un error. Podemos pensar rápidamente en cambiar de posición las líneas 9 y 10 del código, pero this no está disponible hasta que no llamemos a super(), por lo que no podemos intercambiar estas dos líneas de posición. La solución es llamar a super() sin parámetros y hacer nosotros la llamada de forma explícita para crear los elementos iniciales.

const CHECKER = Symbol ();

class eqSet extends Set {
  constructor (iterable, checker) {
    super ();
    if (typeof iterable === 'function') {
      checker  = iterable;
      iterable = undefined;
    }
    this[ CHECKER ] = checker;
    for (let i of iterable) {
      this.add(i);
    }
  }
  
  add (value) {
    return super.add (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v)) || value
    );
  }
  
  delete (value) {
    return super.delete (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v))
    );
  }
  
  has (value) {
    return super.has (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v))
    );
  }
  
}

Ahora sí podemos ejecutar nuestro código sin problemas:

const dates = [
  new Date(2019,0,1),
  new Date(2019,0,1), // Duplicated value
  new Date(2019,0,2),
  new Date(2019,0,3),
  new Date(2019,0,4),
  new Date(2019,0,5)
];

const uniqueDates = new eqSet(dates, (a, b) => a.valueOf() === b.valueOf());

console.assert(uniqueDates.size === 5);

Si nos fijamos bien, la función que se ha pasado para comprobar los valores es muy limitada, ya que sólo funcionará correctamente en este caso, pero no en otros que podamos establecer. Hace poco publicamos la función equivalent() y por lo tanto tenemos a nuestra disposición una función universal de comprobación de valores equivalentes en Javascript, podemos utilizar esta función por defecto como comprobación y mantener el parámetro opcional cuando queramos hacer una evaluación de equivalencias específica.

import equivalent from './equivalent.mjs';

const CHECKER = Symbol ();

class eqSet extends Set {
  constructor (iterable, checker) {
    super ();
    if (typeof iterable === 'function') {
      checker  = iterable;
      iterable = undefined;
    }
    this[ CHECKER ] = checker || equivalent;
    if (iterable) {
      for (let i of iterable) {
        this.add (i);
      }
    }
  }
  
  add (value) {
    return super.add (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v)) || value
    );
  }
  
  delete (value) {
    return super.delete (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v))
    );
  }
  
  has (value) {
    return super.has (
      [ ...this.values () ].find ((v) => this[ CHECKER ] (value, v)) || value
    );
  }
  
}

const dates = [
  new Date (2019, 0, 1),
  new Date (2019, 0, 1), // Duplicated value
  new Date (2019, 0, 2),
  new Date (2019, 0, 3),
  new Date (2019, 0, 4),
  new Date (2019, 0, 5)
];

const uniqueDates = new eqSet (dates);

console.assert (uniqueDates.size === 5);

Si queremos hacer la misma operación con Map, es decir, que la comprobación de las claves se realice por medio de una función, sólo tenemos que aplicar la técnica que hemos descrito aquí para el constructor y los métodos adecuados a este caso.

import equivalent from './equivalent.mjs';

const CHECKER = Symbol ('checker function');

class eqMap extends Map {
  
  constructor (iterable, checker) {
    super ();
    if (typeof iterable === 'function') {
      checker  = iterable;
      iterable = undefined;
    }
    this[ CHECKER ] = checker || equivalent;
    if (iterable) {
      for (let i of iterable) {
        this.set (i[ 0 ], i[ 1 ]);
      }
    }
  }
  
  delete (key) {
    return super.delete (
      [ ...this.keys () ].find ((k) => this[ CHECKER ] (key, k))
    );
  }
  
  get (key) {
    return super.get (
      [ ...this.keys () ].find ((k) => this[ CHECKER ] (key, k))
    );
  }
  
  has (key) {
    return super.has (
      [ ...this.keys () ].find ((k) => this[ CHECKER ] (key, k))
    );
  }
  
  set (key, value) {
    return super.set (
      [ ...this.keys () ].find ((k) => this[ CHECKER ] (key, k)) || key,
      value
    );
  }
  
}

const m = new eqMap();

m.set({a: 1}, 1);
m.set({a: 1}, 2);

console.assert( m.size === 1 );
console.assert( m.get({a:1}, 2));

Ahora tenemos un sistema completo y flexible, donde dos objetos con los mismos valores son tratados como una única entrada en Set y Map aunque no sean exactamente el mismo objeto. El problema es que esta proximación hace que el tiempo de respuesta vaya empeorando de forma muy significativa cuando aumenta el número de elementos dentro de los objetos eqSet y eqMap, por lo que en la práctica, aunque cumple nuestro objetivo, pueden provocar un serio problema de rendimiento de los programas con volumenes relativamente altos. . Te recomendamos que leas nuestro artículo Corregir la complejidad lineal en nuestra propuesta de superación de la comprobación estricta en Set y Map donde explicamos cómo donde resolver los problemas que esta primera aproximación presenta.