Seleccionar página
Una pregunta bastante habitual es cómo conseguir un objeto Map ordenado, ya sea por sus claves o por sus valores. Los objetos Map almacenan los datos en el mismo orden en el que han sido insertados y este no siempre es el orden que nos interesa. Vamos a analizar diferentes alternativas y estrategias para conseguir listas ordenadas basadas en Map.

Ordenar cuando sea necesario

Una sencilla solución es obtener todos los valores del Map como una matriz y ordenarlos, para volverlos a incluir en otro objeto Map. Sería algo tan sencillo como este código:

const unsortedMap = new Map (
  [ [ 'u', 22 ], [ 'r', 19 ], [ 'z', 27 ], [ 'd',  4 ],
    [ 'l', 12 ], [ 'y', 26 ], [ 'v', 23 ], [ 'e',  5 ],
    [ 'p', 17 ], [ 'f',  6 ], [ 'h',  8 ], [ 'x', 25 ],
    [ 'k', 11 ], [ 'c',  3 ], [ 'g',  7 ], [ 't', 21 ],
    [ 'i',  9 ], [ 'w', 24 ], [ 'b',  2 ], [ 'o', 16 ],
    [ 'q', 18 ], [ 'j', 10 ], [ 'ñ', 15 ], [ 's', 20 ],
    [ 'n', 14 ], [ 'a',  1 ], [ 'm', 13 ] ]
);

const sortedMap = new Map( [...unsortedMap].sort((x, y) => x[1] - y[1]));

console.log(...sortedMap);
 

Si queremos ponerlo un poco más atractivo, podemos añadir un método .sort() a una clase que herede de Map. De esta forma tenemos algo más reutilizable:

class SortableMap extends Map {
 sort(fn) {
   fn = fn ? fn : (x, y) => x[1] > y[1] ? 1 : x[1] < y[1] ? - 1 : 0;
  return new Map( [...this].sort(fn));
 }
 
}

const unsortedMap = new SortableMap (
  [ [ 'u', 22 ], [ 'r', 19 ], [ 'z', 27 ], [ 'd',  4 ],
    [ 'l', 12 ], [ 'y', 26 ], [ 'v', 23 ], [ 'e',  5 ],
    [ 'p', 17 ], [ 'f',  6 ], [ 'h',  8 ], [ 'x', 25 ],
    [ 'k', 11 ], [ 'c',  3 ], [ 'g',  7 ], [ 't', 21 ],
    [ 'i',  9 ], [ 'w', 24 ], [ 'b',  2 ], [ 'o', 16 ],
    [ 'q', 18 ], [ 'j', 10 ], [ 'ñ', 15 ], [ 's', 20 ],
    [ 'n', 14 ], [ 'a',  1 ], [ 'm', 13 ] ]
);

const sortedMap = unsortedMap.sort();

console.log(...sortedMap);

Aunque este tipo de ordenación funciona, no suele ser una solución razonable ya que:

  • Como consecuencia de nuestra operación ahora tenemos dos objetos Map, aunque siempre podríamos eliminar uno de ellos.
  • Esta ordenación es puntual y al introducir un nuevo valor en el objeto Map quedará desordenado inmediatamente y tendremos que volver a ordenarlo con este mismo mecanismo, lo cual es -cuanto menos- un engorro.

Vamos a ver algunas alternativas para mantener un objeto Map ordenado.

Ordenar el Map sobreescribiendo el método set()

Una posible solución es crear nuestra propia clase SortedMap que heredando de Map nos permita tener un objeto siempre ordenado. Inicialmente, para implementar esta clase podemos plantearnos dos estrategias bastante diferentes:

  • Realizar la operación de ordenar cuando se insertan nuevos elementos (sobreescribiendo el método set)
  • Realizar la operación de ordenar cuando se consultan los elementos (sobreescribiendo los métodos Symbol.iterator, keys, values y entries).

Vamos a ver una implementación de la primera de estas estrategias:

class SortedMap extends Map {

  set(key, value) {
    super.set(key, value);
    const entries = [...this].sort((x, y) => x[1] > y[1] ? 1 : x[1] < y[1] ? -1 : 0);
    this.clear();
    entries.forEach(x => super.set(x[0], x[1]));
  }

}

const sortedMap = new SortedMap(
  [ [ 'u', 22 ], [ 'r', 19 ], [ 'z', 27 ], [ 'd',  4 ],
    [ 'l', 12 ], [ 'y', 26 ], [ 'v', 23 ], [ 'e',  5 ],
    [ 'p', 17 ], [ 'f',  6 ], [ 'h',  8 ], [ 'x', 25 ],
    [ 'k', 11 ], [ 'c',  3 ], [ 'g',  7 ], [ 't', 21 ],
    [ 'i',  9 ], [ 'w', 24 ], [ 'b',  2 ], [ 'o', 16 ],
    [ 'q', 18 ], [ 'j', 10 ], [ 'ñ', 15 ], [ 's', 20 ],
    [ 'n', 14 ], [ 'a',  1 ], [ 'm', 13 ] ]
);
sortedMap.set('#', 0);

console.log(...sortedMap);

En este caso lo que hemos hecho es sobreescribir el método .set() para que realice la ordenación del contenido, borre todo el contenido del objeto Map y vuelva a cargar ordenado.

SortedMap set table

Esta solución funciona, pero tiene un importante problema: en cuanto va creciendo el tamaño del objeto Map con nuevos elementos, los tiempos de respuesta se van disparando.

En este gráfico se puede observar como varía el tiempo total de inserción de elementos entre la versión de SortedMap que sobreescribe .set() y el tiempo para una operación equivalente con Map nativo. Como se puede observar, insertar 10.000 elementos ya lleva más de 10 segundos, frente a los pocos milisegundos que tarda el Map nativo. Es un tiempo de respuesta absolutamente inaceptable y tenemos que buscar alguna alternativa.

Nota: estos gráficos se han obtenido utilizando el motor v8 versión 7.4, pudiendo obtenerse resultados algo diferentes en otros motores Javascript.

 

Ordenar el Map sobreescribiendo los métodos de acceso

Esta segunda opción consiste en realizar la operación de ordenar los datos cuando se consultan los elementos, es decir, sobreescribiendo los métodos Symbol.iterator, keys, values y entries.

class SortedMap extends Map {
  
  [ Symbol.iterator ] () {
    const fn = (x, y) => x[ 1 ] > y[ 1 ] ? 1 : x[ 1 ] < y[ 1 ] ? -1 : 0;
    return [ ...super.entries () ].sort (fn)[ Symbol.iterator ] ();
  }
  
  entries () {
    return [ ...this ];
  }
  
  keys () {
    return [ ...this ].map (x => x[ 0 ]);
  }
  
  values () {
    return [ ...this ].map (x => x[ 1 ]);
  }
  
}

const sortedMap = new SortedMap (
  [ [ 'u', 22 ], [ 'r', 19 ], [ 'z', 27 ], [ 'd',  4 ],
    [ 'l', 12 ], [ 'y', 26 ], [ 'v', 23 ], [ 'e',  5 ],
    [ 'p', 17 ], [ 'f',  6 ], [ 'h',  8 ], [ 'x', 25 ],
    [ 'k', 11 ], [ 'c',  3 ], [ 'g',  7 ], [ 't', 21 ],
    [ 'i',  9 ], [ 'w', 24 ], [ 'b',  2 ], [ 'o', 16 ],
    [ 'q', 18 ], [ 'j', 10 ], [ 'ñ', 15 ], [ 's', 20 ],
    [ 'n', 14 ], [ 'a',  1 ], [ 'm', 13 ] ]
);
sortedMap.set ('#', 0);

console.log (...sortedMap);
console.log (...sortedMap.entries ());
console.log (...sortedMap.values ());
console.log (...sortedMap.keys ());
 

Ahora devuelven los valores de Map ordenados, aunque internamente sigan en el orden en el que se han cargado. Señalar que los métodos entries, keys y values hacen uso de […this] y por lo tanto están llamado al método Symbol.Interator, por lo que todo el trabajo de ordenación está en un único sitio. También es importante fijarse que en Symbol.Interator se hace uso de super.entries() para obtener los datos, ya que si no se produce un bucle infinito donde nos llamamos a nosotros mismos para obtener los datos.

SortedMap loop statistics

En cuanto la rendimiento, en este gráfico se puede observar como varía el tiempo total de consulta de elementos con un bucle for…of entre la versión de SortedMap que sobreescribe Symbol.iterator y el tiempo para una operación equivalente con Map.

Aunque los tiempos van creciendo, lo hacen en una proporción mucho menor que en el caso anterior, y estamos hablando de unos 30 milisegundos para recorrer 50.000 elementos, frente a 3 o 4 milisegundos que tarda el Map nativo. En muchos casos estos tiempos de respuesta pueden ser aceptables en algunos casos, ya que se incrementan unos pocos milisegundos cada varios miles de elementos, pero el desde luego no se mantiene estable como en el caso del método original de Map que no tiene que hacer ninguna ordenación.

 

Ordenar el contenido de Map con una búsqueda binaria

Aunque la última aproximación puede ser bastante razonable para muchos casos, vamos a explorar un posible cambio de estrategia y aprovechar que ya tenemos ordenados los datos para insertar los nuevos registros con una búsqueda optimizada. Primero vamos a construir los métodos principales de esta nueva clase:

const LIST      = Symbol ();
const LIST_FIND = Symbol ();

class SortedMap extends Map {
  
  set (key, value) {
    if (!this[ LIST ]) {
      this[ LIST ] = [];
    }
    super.set (key, value);
    this[ LIST ].splice (this[ LIST_FIND ] (value), 0, [ key, value ]);
    
  }
  
  [ LIST_FIND ] (value) {
    if (!this[ LIST ].length) {
      return 0;
    }
    let start = 0;
    let end   = this[ LIST ].length - 1;
    while (start < end && start < this[ LIST ].length && end > 0) {
      let position = start + Math.floor ((end - start) / 2);
      if (this[ LIST ][ position ][ 1 ] === value) {
        return position;
      }
      if (this[ LIST ][ position ][ 1 ] < value) {
        start = position + 1;
      } else if (this[ LIST ][ position ][ 1 ] > value) {
        end = position - 1;
      }
    }
    if (this[ LIST ][ start ] && this[ LIST ][ start ][ 1 ] >= value) {
      return start
    }
    if (!this[ LIST ][ end ] || this[ LIST ][ end ][ 1 ] < value) {
      return end + 1;
    }
  }
  
}
 

En esta primera versión hemos incluido una matriz this[ LIST ] como una propiedad oculta por medio de un Symbol().

Esta matriz this[ LIST ] la creamos la primera vez que se llama al método .set(). Esto lo hacemos así ya que internamente el constructor de Map llama a .set() cuando se pasan parámetros al constructor. Si intentamos ejecutar this[ LIST ] = [] antes de llamar a super(…args) nos dará un error, ya que this todavía no está disponible; si llamamos primero a super(…args), entonces se llama internamente a .set() para dar de alta los valores y no tenemos creado this[ LIST ]. La solución, aunque parezca curiosa, es crear this[ LIST ] = [] en la primera llamada al método .set().

También hemos creado un método privado [ LIST_FIND ]() que hace una búsqueda binaria en la matriz LIST que siempre está ordenada.

Una búsqueda binaria localiza la mitad de la matriz y se comprueba si el valor es menor o mayor del valor de esa posición. Si es mayor, sólo se tendrá en cuenta la mitad superior de la matriz para la siguiente fase de búsqueda, y si es menor sólo se tendrá en cuenta la mitad inferior. De nuevo se busca la mitad de la parte de la matriz que nos ha quedado y volvemos a comprobar. Al hacer eso sucesivamente localizamos la posición de la matriz donde debemos insertar el valor con un número de consultas bastante optimizado.

Una vez que tenemos la posición adecuada para el valor, sólo tenemos que hacer uso del método .splice() para insertar el valor en la posición ordenada que le corresponde.

Una vez tenemos los métodos principales, vamos a completar un poco más nuestro código con algunas cosas que nos faltan:

const LIST             = Symbol ();
const LIST_DELETE      = Symbol ();
const LIST_FIND        = Symbol ();
const COMPARE_FUNCTION = Symbol ();

class SortedMap extends Map {
  
  constructor (data, compareFunction) {
    if (typeof data === 'function') {
      compareFunction = data;
      data            = [];
    }
    if (compareFunction) {
      data.unshift ([ COMPARE_FUNCTION, compareFunction ]);
    }
    super (data);
  }
  
  set (key, value) {
    if (!this[ LIST ]) {
      this[ LIST ] = [];
      if (key === COMPARE_FUNCTION) {
        return this[ COMPARE_FUNCTION ] = value;
      }
    }
    if (this.has (key)) {
      this[ LIST_DELETE ] (key);
    }
    super.set (key, value);
    this[ LIST ].splice (this[ LIST_FIND ] (key, value), 0, [ key, value ]);
    
  }
  
  delete (key) {
    if (this.has (key)) {
      this[ LIST_DELETE ] (key);
      super.delete (key);
    }
  }
  
  clear () {
    this[ LIST ] = [];
    super.clear ();
  }
  
  [ Symbol.iterator ] () {
    return this[ LIST ][ Symbol.iterator ] ();
  }
  
  entries () {
    return this[ LIST ];
  }
  
  keys () {
    return this[ LIST ].map (x => x[ 0 ]);
  }
  
  values () {
    return this[ LIST ].map (x => x[ 1 ]);
  }
  
  forEach (callbackFn, thisArg) {
    const cb = callbackFn.bind (thisArg || this);
    for (let n = 0; n < this[ LIST ].length; n++) {
      cb (this[ LIST ][ n ][ 1 ], this[ LIST ][ n ][ 0 ], this || thisArg);
    }
  }
  
  [ LIST_DELETE ] (key) {
    const value  = this.get (key);
    let position = this[ LIST_FIND ] (key, value);
    let current  = position;
    while (current < this[ LIST ].length &&
           this[ LIST ][ current ][ 1 ] === value &&
           this[ LIST ][ current ][ 0 ] !== key)
    {
      current++;
    }
    if (this[ LIST ][ current ][ 0 ] !== key) {
      current = position;
      while (current > 0 &&
             this[ LIST ][ current ][ 1 ] === value &&
             this[ LIST ][ current ][ 0 ] !== key)
      {
        current--;
      }
    }
    this[ LIST ].splice (current, 1);
  }

  [ LIST_FIND ] (key, value) {
    const list = this[ LIST ];
    if (!list.length) {
      return 0;
    }
    const compareFunction = this[ COMPARE_FUNCTION ] ||
                            ((x, y) => x[ 1 ] > y[ 1 ] ? 1 : x[ 1 ] < y[ 1 ] ? -1 : 0);
    let start             = 0;
    let end               = list.length - 1;
    while (start < end && start < list.length && end > 0) {
      const position = start + Math.floor ((end - start) / 2);
      const result   = compareFunction (list[ position ], [ key, value ]);
      if (result === 0) {
        return position;
      }
      if (result < 0) {
        start = position + 1;
      } else if (result > 0) {
        end = position - 1;
      }
    }
    if (list[ start ] && compareFunction (list[ start ], [ key, value ]) >= 0) {
      return start
    }
    if (!list[ end ] || compareFunction (list[ end ], [ key, value ]) < 0) {
      return end + 1;
    }
  }

}

const sortedMap = new SortedMap (
  [ [ 'u', 22 ], [ 'r', 19 ], [ 'z', 27 ], [ 'd',  4 ],
    [ 'l', 12 ], [ 'y', 26 ], [ 'v', 23 ], [ 'e',  5 ],
    [ 'p', 17 ], [ 'f',  6 ], [ 'h',  8 ], [ 'x', 25 ],
    [ 'k', 11 ], [ 'c',  3 ], [ 'g',  7 ], [ 't', 21 ],
    [ 'i',  9 ], [ 'w', 24 ], [ 'b',  2 ], [ 'o', 16 ],
    [ 'q', 18 ], [ 'j', 10 ], [ 'ñ', 15 ], [ 's', 20 ],
    [ 'n', 14 ], [ 'a',  1 ], [ 'm', 13 ] ],
  (x, y) => x[ 0 ].localeCompare( y[ 0 ] )
);
sortedMap.set ('|', 0);

console.log (...sortedMap);
console.log (...sortedMap.entries ());
console.log (...sortedMap.keys ());
console.log (...sortedMap.values ());

Por un lado hemos incluido el método oculto [ DELETE_LIST ]() y hemos sobre escrito los métodos .delete() y .clear(). De esta forma, cuando se borran elementos del objeto Map, también se borran de la matriz ordenada. Esto es importante para tener siempre consistencia entre las dos referencias de datos, la ordenada de la matriz y la no ordenada que reside en el propio Map.

También hemos sobreescrito los métodos Symbol.iterator, .entries(), .keys(), .values() y .forEach para que utilicen la lista ordenada como base para recorrer el contenido del objeto.

Por último hemos añadido un nuevo parámetro en el constructor al que le podamos pasar la función a utilizar en la ordenación. De esta forma podemos ordenar por clave o valor, utilizar las funcionalidades que ofrece Intl para comparaciones teniendo en cuenta el idioma (como el método localeCompare() que hemos utilizado en el ejemplo), realizar comprobaciones complejas con objetos, etc.

SortedMap binary set statisttics

Esta nueva clase se comporta de una forma bastante razonable en cuanto al rendimiento comparado con Map, tanto en operaciones con el método .set(), como con bucles de tipo for…of.

Las operaciones con el método .set() van creciendo, pero a un ritmo razonablemente pequeño. Por ejemplo, para insertar 50.000 elementos estamos tardando en total unos 250 milisegundos, frente a los 15 milisegundos del Map nativo. No obstante, es posible que algunos prefieran la versión anterior, que no sufría de ningún retraso en la ejecución de .set().

SortedMap Binary loop statistics

El tiempo necesario para recorrer los elementos con un bucle for…of no varían sustancialmente entre nuestra clase SortedMap y el Map nativo y en prácticamente en todos los casos están por debajo de 1 milisegundo. En este sentido hemos conseguido una respuesta muy buena, aunque hayamos sobreescrito los métodos de acceso a los datos.

 

Conclusiones

Tener un Map ordenado no va a salirnos gratis y tenemos que asumir que va a llevar más tiempo que utilizar un Map nativo. Cuál implementación es la más optimizada para nuestro uso dependerá de varios factores, sobre todo el número de elementos que vamos a almacenar en el objeto y si necesitamos priorizar las acciones de inserción de valores o los procesos de consulta. En nuestro caso hemos optado por usar la última implementación, basada en la búsqueda binaria, pero es posible que para otros casos de uso la versión basada en sobreescribir los métodos de acceso haciendo en ellos la ordenación de los datos sea más interesante.

La búsqueda binaria en una lista ordenada es un recurso interesante que podemos considerar en algunas ocasiones como alternativa a los mecanismos que nativamente nos ofrece el lenguaje. Es una algoritmo bastante sencillo de implementar y con una complejidad O(log n) bastante razonable. Desde luego se podría plantear utilizar otros algoritmo de búsqueda que se ajusten mejor a otras situaciones y necesidades.

Os animamos a explorar este tipo de soluciones basadas en heredar de objetos Map y Set. Ya vimos hace unos días cómo superar la comprobación estricta en Set y Map, hoy os mostramos cómo mantener el ordenado el contenido de un objeto Map, hacer lo mismo con un objeto Set debería ser bastante sencillo para vosotros después de haber leído este artículo. En breve os mostraremos más cosas que se pueden hacer heredando y ampliando la funcionalidad de estos objetos.

Novedades

Limitar el tamaño de un Map

Limitar el tamaño de un objeto Map no parece una idea muy razonable, pero cuando tu programa se ejecuta sin interrupción durante días, semanas, meses e inclusos años, es muy importante controlar el tamaño de la memoria utilizada para evitar problemas inesperados. Una simple función memoize puede llegar a almacenar mucha más información de la que puedes pensar. Aquí te contamos como limitar el tamaño de un objeto Map para estas situaciones.

¿Es una función nativa de Javascript?

Comprobar si una determinada función es una función nativa de Javascript o es una función escrita en código es algo más complicado de lo que pueda parecer a primera vista. No hay grandes diferencias entre una función nativa y una escrita por nosotros, por lo que tenemos que buscar mecanismos algo indirectos para poder diferenciarlas.