Подражая множествам в JavaScript?
Я работаю в JavaScript. Я хотел бы сохранить список уникальных неупорядоченных строковых значений со следующими свойствами:
- быстрый способ спросить "А в списке"?
- быстрый способ сделать "удалить А из списка, если он существует в списке"
- быстрый способ сделать "добавить А в список, если его еще нет".
Что я действительно хочу, так это набор. Какие-нибудь предложения для лучшего способа подражать множеству в JavaScript?
В этом вопросе рекомендуется использовать объект с ключами, хранящими свойства, и для всех значений установлено значение true: это разумный путь?
7 ответов
Если вы программируете в среде с поддержкой ES6 (например, node.js, конкретный браузер с необходимыми вам возможностями ES6 или переносите код ES6 для своей среды), то вы можете использовать Set объект, встроенный в ES6. Он обладает очень хорошими возможностями и может использоваться как есть в вашей среде.
Для многих простых вещей в среде ES5 использование объекта работает очень хорошо. Если obj ваш объект и A переменная, значение которой вы хотите оперировать в наборе, тогда вы можете сделать это:
Код инициализации:
// 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};
Вопрос 1: есть A в списке:
if (A in obj) {
// put code here
}
Вопрос 2: Удалить "А" из списка, если он там есть:
delete obj[A];
Вопрос 3: Добавьте "А" в список, если его там еще не было
obj[A] = true;
Для полноты теста на A в списке немного безопаснее с этим:
if (Object.prototype.hasOwnProperty.call(obj, A))
// put code here
}
из-за потенциального конфликта между встроенными методами и / или свойствами базового объекта, такого как constructor имущество.
Боковая панель на ES6: текущая рабочая версия ECMAScript 6 или что-то, называемое ES 2015, имеет встроенный объект Set. Это реализовано сейчас в некоторых браузерах. Поскольку доступность браузера меняется со временем, вы можете посмотреть на строку Set в этой таблице совместимости ES6, чтобы увидеть текущий статус доступности браузера.
Одно из преимуществ встроенного объекта Set заключается в том, что он не приводит все ключи к строке, как это делает объект, поэтому вы можете использовать как 5, так и "5" в качестве отдельных ключей. И вы даже можете использовать объекты непосредственно в наборе без преобразования строки. Вот статья, которая описывает некоторые возможности и документацию MDN для объекта Set.
Теперь я написал polyfill для объекта set ES6, чтобы вы могли начать использовать его сейчас, и он автоматически перейдет к встроенному объекту set, если браузер его поддерживает. Преимущество этого в том, что вы пишете ES6-совместимый код, который будет работать вплоть до IE7. Но есть некоторые недостатки. Интерфейс ES6 использует преимущества итераторов ES6, поэтому вы можете for (item of mySet) и он будет автоматически перебирать набор для вас. Но этот тип языковой функции не может быть реализован через polyfill. Вы по-прежнему можете выполнять итерацию набора ES6 без использования новых языковых функций ES6, но, честно говоря, без новых языковых функций это не так удобно, как другой интерфейс набора, который я включаю ниже.
Вы можете решить, какой из них лучше для вас, посмотрев на оба. ESF set polyfill находится здесь: https://github.com/jfriend00/ES6-Set.
К вашему сведению, в моем собственном тестировании я заметил, что реализация Firefox v29 Set не полностью соответствует текущей версии спецификации. Например, вы не можете цепи .add() вызовы методов, описанные в спецификации, и моя поддержка polyfill. Вероятно, это вопрос спецификации в движении, так как она еще не завершена.
Предварительно построенные объекты. Если вы хотите, чтобы уже созданный объект имел методы для работы с набором, который можно использовать в любом браузере, вы можете использовать серию различных предварительно созданных объектов, которые реализуют различные типы наборов. Существует мини-набор, представляющий собой небольшой код, который реализует основы заданного объекта. Он также имеет более функциональный набор объектов и несколько дериваций, включая Словарь (давайте сохраним / получим значение для каждого ключа) и ObjectSet (давайте сохраним набор объектов - либо объекты JS, либо объекты DOM, для которых вы либо предоставите функция, которая генерирует уникальный ключ для каждого или ObjectSet будет генерировать ключ для вас).
Вот копия кода для miniSet (самый актуальный код здесь на 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;
Вы можете создать объект без свойств, таких как
var set = Object.create(null)
который может действовать как набор и исключает необходимость использования 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
В версии ES6 Javascript вы встроили тип для набора ( проверьте совместимость с вашим браузером).
var numbers = new Set([1, 2, 4]); // Set {1, 2, 4}
Чтобы добавить элемент в набор, вы просто используете .add(), который работает в O(1) и либо добавляет элемент для установки (если он не существует), либо ничего не делает, если он уже существует. Вы можете добавить туда элемент любого типа (массивы, строки, числа)
numbers.add(4); // Set {1, 2, 4}
numbers.add(6); // Set {1, 2, 4, 6}
Чтобы проверить количество элементов в наборе, вы можете просто использовать .size, Также работает в O(1)
numbers.size; // 4
Для удаления элемента из набора используйте .delete(), Возвращает true, если значение было (и было удалено), и false, если значение не существовало. Также работает в O(1),
numbers.delete(2); // true
numbers.delete(2); // false
Чтобы проверить, существует ли элемент в наборе, используйте .has(), который возвращает истину, если элемент находится в наборе, и ложь в противном случае. Также работает в O(1),
numbers.has(3); // false
numbers.has(1); // true
В дополнение к методам, которые вы хотели, есть несколько дополнительных:
numbers.clear();просто удалить все элементы из набораnumbers.forEach(callback);перебирая значения набора в порядке вставкиnumbers.entries();создать итератор всех значенийnumbers.keys();возвращает ключи набора, который совпадает сnumbers.values()
Существует также Weakset, который позволяет добавлять только значения типа объекта.
Я начал реализацию наборов, которая в настоящее время довольно хорошо работает с числами и строками. Основное внимание было уделено разностной операции, поэтому я старался сделать ее максимально эффективной. Форкс и обзоры кода приветствуются!
Я только что заметил, что в библиотеке d3.js есть реализация наборов, карт и других структур данных. Я не могу спорить об их эффективности, но, судя по тому, что это популярная библиотека, она должна быть именно тем, что вам нужно.
Документация здесь
Для удобства копирую по ссылке (первые 3 функции представляют интерес)
- d3.set ([массив])
Создает новый набор. Если указан массив, добавляет указанный массив строковых значений в возвращаемый набор.
- set.has (значение)
Возвращает true тогда и только тогда, когда в этом наборе есть запись для указанной строки значения.
- Set.add (значение)
Добавляет указанную строку значения в этот набор.
- set.remove (значение)
Если набор содержит указанную строку значений, удаляет ее и возвращает true. В противном случае этот метод ничего не делает и возвращает false.
- set.values ()
Возвращает массив значений строки в этом наборе. Порядок возвращаемых значений произвольный. Может использоваться как удобный способ вычисления уникальных значений для набора строк. Например:
d3.set (["foo", "bar", "foo", "baz"]). values (); // "foo", "bar", "baz"
- set.forEach (функция)
Вызывает указанную функцию для каждого значения в этом наборе, передавая значение в качестве аргумента. Этот контекст функции является этим набором. Возвращает неопределенное. Порядок итерации произвольный.
- set.empty ()
Возвращает true тогда и только тогда, когда этот набор имеет нулевые значения.
- set.size ()
Возвращает количество значений в этом наборе.
Да, это разумный способ - это все, чем является объект (ну, в данном случае)- набор ключей / значений с прямым доступом.
Вам нужно проверить, чтобы увидеть, находится ли он уже там, прежде чем добавить его, или если вам просто нужно указать присутствие, "добавление" его снова фактически ничего не меняет, оно просто устанавливает его на объекте снова.