historia - que es html y javascript

¿Imitando conjuntos en JavaScript?

Question

Estoy trabajando en JavaScript. Me gustaría almacenar una lista de valores de cadena únicos , desordenados, con las siguientes propiedades:

1. ¿Una forma rápida de preguntar ''es A en la lista''?
2. una forma rápida de hacer ''eliminar A de la lista si existe en la lista''
3. una forma rápida de hacer ''agregar A a la lista si aún no está presente''.

Lo que realmente quiero es un set. ¿Alguna sugerencia para la mejor manera de imitar un conjunto en JavaScript?

Esta pregunta recomienda usar un Objeto , con las claves que almacenan las propiedades y los valores establecidos en verdadero: ¿es eso una forma sensata?

Answer 1

A partir de ECMAScript 6, el conjunto de estructura de datos es una característica integrada. La compatibilidad con las versiones de node.js se puede encontrar here .

Answer 2

Acabo de notar que la biblioteca d3.js tiene implementación de conjuntos, mapas y otras estructuras de datos. No puedo discutir sobre su eficiencia, pero a juzgar por el hecho de que es una biblioteca popular, debe ser lo que necesita.

La documentación está here

Para mayor comodidad copio desde el enlace (las 3 primeras funciones son las de interés)

• d3.set ([array])

Construye un nuevo conjunto. Si se especifica una matriz, agrega la matriz dada de valores de cadena al conjunto devuelto.

• set.has (valor)

Devuelve verdadero si y solo si este conjunto tiene una entrada para la cadena de valor especificada.

• set.add (valor)

Agrega la cadena de valor especificada a este conjunto.

• set.remove (valor)

Si el conjunto contiene la cadena de valor especificada, la elimina y devuelve verdadero. De lo contrario, este método no hace nada y devuelve falso.

• set.values ​​()

Devuelve una matriz de los valores de cadena en este conjunto. El orden de los valores devueltos es arbitrario. Puede usarse como una forma conveniente de calcular los valores únicos para un conjunto de cadenas. Por ejemplo:

d3.set (["foo", "bar", "foo", "baz"]). valores (); // "foo", "bar", "baz"

• set.forEach (función)

Llama a la función especificada para cada valor en este conjunto, pasando el valor como un argumento. El contexto de esta función es este conjunto. Devoluciones no definidas. La orden de iteración es arbitraria.

• set.empty ()

Devuelve verdadero si y solo si este conjunto tiene valores cero.

• set.size ()

Devuelve el número de valores en este conjunto.

Answer 3

En la versión ES6 de Javascript, tiene un tipo de juego incorporado ( verifique la compatibilidad con su navegador ).

var numbers = new Set([1, 2, 4]); // Set {1, 2, 4}

Para agregar un elemento al conjunto, simplemente use .add() , que se ejecuta en O(1) y agrega el elemento a establecer (si no existe) o no hace nada si ya está allí. Puede agregar elementos de cualquier tipo allí (arrays, cadenas, números)

numbers.add(4); // Set {1, 2, 4}
numbers.add(6); // Set {1, 2, 4, 6}

Para verificar el número de elementos en el conjunto, simplemente puede usar .size . También se ejecuta en O(1)

numbers.size; // 4

Para eliminar el elemento del conjunto use .delete() . Devuelve verdadero si el valor estaba allí (y se eliminó) y falso si el valor no existía. También se ejecuta en O(1) .

numbers.delete(2); // true
numbers.delete(2); // false

Para verificar si el elemento existe en un conjunto, use .has() , que devuelve verdadero si el elemento está en el conjunto y falso en caso contrario. También se ejecuta en O(1) .

numbers.has(3); // false
numbers.has(1); // true

Además de los métodos que querías, hay algunos adicionales:

• numbers.clear(); Sólo eliminaría todos los elementos del conjunto.
• numbers.forEach(callback); iterando a través de los valores del conjunto en orden de inserción
• numbers.entries(); Crea un iterador de todos los valores.
• numbers.keys(); devuelve las claves del conjunto que es lo mismo que numbers.values()

También hay un Weakset que permite agregar solo valores de tipo de objeto.

Answer 4

He comenzado una implementación de Conjuntos que actualmente funciona bastante bien con números y cadenas. Mi enfoque principal era la operación de diferencia, así que traté de hacerlo lo más eficiente posible. Horquillas y revisiones de código son bienvenidos!

https://github.com/mcrisc/SetJS

Answer 5

Puedes crear un Objeto sin propiedades como

var set = Object.create(null)

que puede actuar como un conjunto y elimina la necesidad de usar hasOwnProperty .

var set = Object.create(null); // create an object with no properties

if (A in set) { // 1. is A in the list
  // some code
}
delete set[a]; // 2. delete A from the list if it exists in the list 
set[A] = true; // 3. add A to the list if it is not already present

Answer 6

Sí, esa es una forma sensata, eso es todo lo que es un objeto (bueno, para este caso de uso), un montón de claves / valores con acceso directo.

Necesitará verificar si ya está allí antes de agregarlo, o si simplemente necesita indicar presencia, "agregar" nuevamente no cambia nada en realidad, simplemente lo establece en el objeto nuevamente.

Answer 7

Si está programando en un entorno compatible con ES6 (como node.js, un navegador específico con las capacidades de ES6 que necesita o transpilando el código de ES6 para su entorno), puede usar el objeto Set integrado en ES6 . Tiene capacidades muy agradables y se puede utilizar como es correcto en su entorno.

Para muchas cosas simples en un entorno ES5, usar un Objeto funciona muy bien. Si obj es su objeto y A es una variable que tiene el valor que desea operar en el conjunto, puede hacer lo siguiente:

Código de inicialización:

// create empty object
var obj = {};

// or create an object with some items already in it
var obj = {"1":true, "2":true, "3":true, "9":true};

Pregunta 1: ¿Está A en la lista?

if (A in obj) {
    // put code here
}

Pregunta 2: elimine ''A'' de la lista si está allí:

delete obj[A];

Pregunta 3: agregue ''A'' a la lista si no estaba ya allí

obj[A] = true;

Para completar, la prueba de si A está en la lista es un poco más segura con esto:

if (Object.prototype.hasOwnProperty.call(obj, A))
    // put code here
}

debido al conflicto potencial entre los métodos integrados y / o las propiedades en el Objeto base como la propiedad del constructor .

Barra lateral en ES6: La versión de trabajo actual de ECMAScript 6 o algunas de ellas llamadas ES 2015 tiene un objeto Set incorporado . Se implementa ahora en algunos navegadores. Como la disponibilidad del navegador cambia con el tiempo, puede consultar la línea de Set en esta tabla de compatibilidad ES6 para ver el estado actual de la disponibilidad del navegador.

Una de las ventajas del objeto Set incorporado es que no obliga a todas las claves a una cadena como lo hace el Objeto, por lo que puede tener tanto 5 como "5" como claves separadas. Y, incluso puede usar objetos directamente en el conjunto sin una conversión de cadena. Aquí hay un artículo que describe algunas de las capacidades y la documentación de MDN sobre el objeto Set.

Ahora he escrito un polyfill para el objeto set ES6 para que pueda comenzar a usarlo ahora y se transferirá automáticamente al objeto set incorporado si el navegador lo admite. Esto tiene la ventaja de que está escribiendo código compatible con ES6 que funcionará hasta IE7. Pero, hay algunas desventajas. La interfaz de conjunto de ES6 aprovecha los iteradores de ES6 para que pueda hacer cosas como for (item of mySet) y for (item of mySet) automáticamente a través del conjunto para usted. Pero, este tipo de función de lenguaje no se puede implementar a través de polyfill. Aún puede iterar un conjunto ES6 sin usar las nuevas funciones de idiomas de ES6, pero francamente sin las nuevas características de idioma, no es tan conveniente como la otra interfaz de conjunto que se incluye a continuación.

Puede decidir cuál funciona mejor para usted después de mirar ambos. El conjunto de polietileno ES6 se encuentra aquí: https://github.com/jfriend00/ES6-Set .

Para mi información, en mis propias pruebas, he notado que la implementación de Firefox v29 Set no está totalmente actualizada en el borrador actual de la especificación. Por ejemplo, no puede encadenar llamadas al método .add() como describen las especificaciones y mi polyfill admite. Probablemente se trate de una especificación en movimiento, ya que aún no está finalizada.

Objetos de conjuntos precreados: si desea un objeto ya construido que tiene métodos para operar en un conjunto que puede usar en cualquier navegador, puede usar una serie de diferentes objetos preconstruidos que implementan diferentes tipos de conjuntos. Hay un miniSet que es un pequeño código que implementa los conceptos básicos de un objeto establecido. También tiene un objeto de conjunto más rico en características y varias derivaciones, incluido un Diccionario (le permite almacenar / recuperar un valor para cada clave) y un ObjectSet (le permite mantener un conjunto de objetos, ya sea objetos JS u objetos DOM donde puede suministrar el La función que genera una clave única para cada uno o el ObjectSet generará la clave para usted).

Aquí hay una copia del código para el miniSet (el código más actualizado está aquí en github ).

"use strict";
//-------------------------------------------
// Simple implementation of a Set in javascript
//
// Supports any element type that can uniquely be identified
//    with its string conversion (e.g. toString() operator).
// This includes strings, numbers, dates, etc...
// It does not include objects or arrays though
//    one could implement a toString() operator
//    on an object that would uniquely identify
//    the object.
// 
// Uses a javascript object to hold the Set
//
// This is a subset of the Set object designed to be smaller and faster, but
// not as extensible.  This implementation should not be mixed with the Set object
// as in don''t pass a miniSet to a Set constructor or vice versa.  Both can exist and be
// used separately in the same project, though if you want the features of the other
// sets, then you should probably just include them and not include miniSet as it''s
// really designed for someone who just wants the smallest amount of code to get
// a Set interface.
//
// s.add(key)                      // adds a key to the Set (if it doesn''t already exist)
// s.add(key1, key2, key3)         // adds multiple keys
// s.add([key1, key2, key3])       // adds multiple keys
// s.add(otherSet)                 // adds another Set to this Set
// s.add(arrayLikeObject)          // adds anything that a subclass returns true on _isPseudoArray()
// s.remove(key)                   // removes a key from the Set
// s.remove(["a", "b"]);           // removes all keys in the passed in array
// s.remove("a", "b", ["first", "second"]);   // removes all keys specified
// s.has(key)                      // returns true/false if key exists in the Set
// s.isEmpty()                     // returns true/false for whether Set is empty
// s.keys()                        // returns an array of keys in the Set
// s.clear()                       // clears all data from the Set
// s.each(fn)                      // iterate over all items in the Set (return this for method chaining)
//
// All methods return the object for use in chaining except when the point
// of the method is to return a specific value (such as .keys() or .isEmpty())
//-------------------------------------------


// polyfill for Array.isArray
if(!Array.isArray) {
    Array.isArray = function (vArg) {
        return Object.prototype.toString.call(vArg) === "[object Array]";
    };
}

function MiniSet(initialData) {
    // Usage:
    // new MiniSet()
    // new MiniSet(1,2,3,4,5)
    // new MiniSet(["1", "2", "3", "4", "5"])
    // new MiniSet(otherSet)
    // new MiniSet(otherSet1, otherSet2, ...)
    this.data = {};
    this.add.apply(this, arguments);
}

MiniSet.prototype = {
    // usage:
    // add(key)
    // add([key1, key2, key3])
    // add(otherSet)
    // add(key1, [key2, key3, key4], otherSet)
    // add supports the EXACT same arguments as the constructor
    add: function() {
        var key;
        for (var i = 0; i < arguments.length; i++) {
            key = arguments[i];
            if (Array.isArray(key)) {
                for (var j = 0; j < key.length; j++) {
                    this.data[key[j]] = key[j];
                }
            } else if (key instanceof MiniSet) {
                var self = this;
                key.each(function(val, key) {
                    self.data[key] = val;
                });
            } else {
                // just a key, so add it
                this.data[key] = key;
            }
        }
        return this;
    },
    // private: to remove a single item
    // does not have all the argument flexibility that remove does
    _removeItem: function(key) {
        delete this.data[key];
    },
    // usage:
    // remove(key)
    // remove(key1, key2, key3)
    // remove([key1, key2, key3])
    remove: function(key) {
        // can be one or more args
        // each arg can be a string key or an array of string keys
        var item;
        for (var j = 0; j < arguments.length; j++) {
            item = arguments[j];
            if (Array.isArray(item)) {
                // must be an array of keys
                for (var i = 0; i < item.length; i++) {
                    this._removeItem(item[i]);
                }
            } else {
                this._removeItem(item);
            }
        }
        return this;
    },
    // returns true/false on whether the key exists
    has: function(key) {
        return Object.prototype.hasOwnProperty.call(this.data, key);
    },
    // tells you if the Set is empty or not
    isEmpty: function() {
        for (var key in this.data) {
            if (this.has(key)) {
                return false;
            }
        }
        return true;
    },
    // returns an array of all keys in the Set
    // returns the original key (not the string converted form)
    keys: function() {
        var results = [];
        this.each(function(data) {
            results.push(data);
        });
        return results;
    },
    // clears the Set
    clear: function() {
        this.data = {}; 
        return this;
    },
    // iterate over all elements in the Set until callback returns false
    // myCallback(key) is the callback form
    // If the callback returns false, then the iteration is stopped
    // returns the Set to allow method chaining
    each: function(fn) {
        this.eachReturn(fn);
        return this;
    },
    // iterate all elements until callback returns false
    // myCallback(key) is the callback form
    // returns false if iteration was stopped
    // returns true if iteration completed
    eachReturn: function(fn) {
        for (var key in this.data) {
            if (this.has(key)) {
                if (fn.call(this, this.data[key], key) === false) {
                    return false;
                }
            }
        }
        return true;
    }
};

MiniSet.prototype.constructor = MiniSet;