Comment personnaliser l'égalité des objets pour l'ensemble JavaScript

167

Le nouvel ES 6 (Harmony) introduit un nouvel objet Set . L'algorithme d'identité utilisé par Set est similaire à l' ===opérateur et donc peu adapté à la comparaison d'objets:

var set = new Set();
set.add({a:1});
set.add({a:1});
console.log([...set.values()]); // Array [ Object, Object ]

Comment personnaliser l'égalité pour les objets Set afin de faire une comparaison d'objets approfondie? Existe-t-il quelque chose comme Java equals(Object)?

Czerny
la source
3
Qu'entendez-vous par «personnaliser l'égalité»? Javascript ne permet pas de surcharger l'opérateur, il n'y a donc aucun moyen de surcharger l' ===opérateur. L'objet set ES6 ne possède aucune méthode de comparaison. La .has()méthode et la .add()méthode fonctionnent uniquement sur le fait qu'il s'agit du même objet réel ou de la même valeur pour une primitive.
jfriend00
12
Par «personnaliser l'égalité», j'entends de toute façon comment le développeur peut définir certains objets à considérer comme égaux ou non.
czerny

Réponses:

107

L' Setobjet ES6 n'a pas de méthode de comparaison ni d'extensibilité de comparaison personnalisée.

Les méthodes .has(), .add()et .delete()ne fonctionnent que s'il s'agit du même objet réel ou de la même valeur pour une primitive et n'ont pas de moyen de se connecter ou de remplacer uniquement cette logique.

Vous pourriez probablement dériver votre propre objet à partir de méthodes a Setet replace .has(), .add()et .delete()avec quelque chose qui a d'abord effectué une comparaison d'objets approfondie pour trouver si l'élément est déjà dans l'ensemble, mais les performances ne seraient probablement pas bonnes car l' Setobjet sous-jacent n'aiderait pas. du tout. Vous devrez probablement simplement faire une itération de force brute sur tous les objets existants pour trouver une correspondance en utilisant votre propre comparaison personnalisée avant d'appeler l'original .add().

Voici quelques informations de cet article et une discussion sur les fonctionnalités d'ES6:

5.2 Pourquoi ne puis-je pas configurer la façon dont les cartes et les ensembles comparent les clés et les valeurs?

Question: Ce serait bien s'il y avait un moyen de configurer quelles clés de carte et quels éléments d'ensemble sont considérés comme égaux. Pourquoi n'y en a-t-il pas?

Réponse: Cette fonctionnalité a été reportée, car elle est difficile à mettre en œuvre correctement et efficacement. Une option consiste à remettre les rappels aux collections qui spécifient l'égalité.

Une autre option, disponible en Java, consiste à spécifier l'égalité via une méthode implémentée par l'objet (equals () en Java). Cependant, cette approche est problématique pour les objets mutables: en général, si un objet change, son «emplacement» dans une collection doit également changer. Mais ce n'est pas ce qui se passe en Java. JavaScript utilisera probablement la voie la plus sûre en permettant uniquement la comparaison par valeur pour les objets immuables spéciaux (les objets de valeur). La comparaison par valeur signifie que deux valeurs sont considérées comme égales si leur contenu est égal. Les valeurs primitives sont comparées par valeur en JavaScript.

jfriend00
la source
4
Ajout d'une référence d'article sur ce problème particulier. Il semble que le défi consiste à gérer un objet qui était exactement le même qu'un autre au moment où il a été ajouté à l'ensemble, mais qui a maintenant été modifié et n'est plus le même que cet objet. Est-ce dans le Setou pas?
jfriend00
3
Pourquoi ne pas implémenter un simple GetHashCode ou similaire?
Jamby
@Jamby - Ce serait un projet intéressant de créer un hachage qui gère tous les types de propriétés et les propriétés de hachage dans le bon ordre et traite des références circulaires et ainsi de suite.
jfriend00
1
@Jamby Même avec une fonction de hachage, vous devez toujours gérer les collisions. Vous ne faites que reporter le problème de l'égalité.
mpen
5
@mpen Ce n'est pas vrai, j'autorise le développeur à gérer sa propre fonction de hachage pour ses classes spécifiques, ce qui dans presque tous les cas évite le problème de collision puisque le développeur connaît la nature des objets et peut dériver une bonne clé. Dans tous les autres cas, revenez à la méthode de comparaison actuelle. Beaucoup de langues font déjà ça, js non.
Jamby
28

Comme mentionné dans la réponse de jfriend00, la personnalisation de la relation d'égalité n'est probablement pas possible .

Le code suivant présente un aperçu de la solution de contournement efficace (mais coûteuse en mémoire) :

class GeneralSet {

    constructor() {
        this.map = new Map();
        this[Symbol.iterator] = this.values;
    }

    add(item) {
        this.map.set(item.toIdString(), item);
    }

    values() {
        return this.map.values();
    }

    delete(item) {
        return this.map.delete(item.toIdString());
    }

    // ...
}

Chaque élément inséré doit implémenter une toIdString()méthode qui renvoie une chaîne. Deux objets sont considérés comme égaux si et seulement si leurs toIdStringméthodes retournent la même valeur.

Czerny
la source
Vous pouvez également demander au constructeur de prendre une fonction qui compare les éléments pour l'égalité. C'est bien si vous voulez que cette égalité soit une caractéristique de l'ensemble, plutôt que des objets qui y sont utilisés.
Ben J
1
@BenJ Le point de générer une chaîne et de la mettre dans une carte est que de cette façon, votre moteur Javascript utilisera une recherche ~ O (1) dans le code natif pour rechercher la valeur de hachage de votre objet, tout en acceptant une fonction d'égalité forcerait pour faire un balayage linéaire de l'ensemble et vérifier chaque élément.
Jamby
3
Un défi avec cette méthode est que je pense qu'elle suppose que la valeur de item.toIdString()est invariante et ne peut pas changer. Parce que si c'est possible, alors le GeneralSetpeut facilement devenir invalide avec des éléments "en double" dedans. Ainsi, une solution comme celle-ci se limiterait à certaines situations probables où les objets eux-mêmes ne sont pas modifiés lors de l'utilisation de l'ensemble ou dans lesquels un ensemble qui devient invalide n'a pas de conséquence. Tous ces problèmes expliquent probablement davantage pourquoi l'ensemble ES6 n'expose pas cette fonctionnalité car elle ne fonctionne vraiment que dans certaines circonstances.
jfriend00
Est-il possible d'ajouter l'implémentation correcte de .delete()à cette réponse?
jlewkovich
1
@JLewkovich sure
czerny
6

Comme l'indique la réponse principale , la personnalisation de l'égalité est problématique pour les objets mutables. La bonne nouvelle est (et je suis surpris que personne ne l'ait encore mentionné), il existe une bibliothèque très populaire appelée immutable-js qui fournit un riche ensemble de types immuables qui fournissent la sémantique d'égalité des valeurs profonde que vous recherchez.

Voici votre exemple utilisant immutable-js :

const { Map, Set } = require('immutable');
var set = new Set();
set = set.add(Map({a:1}));
set = set.add(Map({a:1}));
console.log([...set.values()]); // [Map {"a" => 1}]
Russell Davis
la source
10
Comment les performances de immutable-js Set / Map se comparent-elles à celles de Set / Map natif?
frankster
5

Pour ajouter aux réponses ici, j'ai mis en œuvre un wrapper de carte qui prend une fonction de hachage personnalisée, une fonction d'égalité personnalisée et stocke des valeurs distinctes qui ont des hachages équivalents (personnalisés) dans des buckets.

Comme on pouvait s'y attendre, il s'est avéré être plus lent que la méthode de concaténation de chaînes de czerny .

Source complète ici: https://github.com/makoConstruct/ValueMap

mako
la source
«Concaténation de chaînes»? Sa méthode ne ressemble-t-elle pas plus à la «substitution de chaînes» (si vous allez lui donner un nom)? Ou y a-t-il une raison pour laquelle vous utilisez le mot «concaténation»? I'm curious ;-)
binki
@binki C'est une bonne question et je pense que la réponse soulève un bon point qu'il m'a fallu un certain temps pour comprendre. En règle générale, lors du calcul d'un code de hachage, on fait quelque chose comme HashCodeBuilder qui multiplie les codes de hachage de champs individuels et n'est pas garanti pour être unique (d'où la nécessité d'une fonction d'égalité personnalisée). Cependant, lors de la génération d'une chaîne d'identifiant, vous concaténez les chaînes d'identifiant de champs individuels qui sont garantis uniques (et donc aucune fonction d'égalité nécessaire)
Pace
Donc, si vous avez Pointdéfini comme, { x: number, y: number }votre id stringest probablement x.toString() + ',' + y.toString().
Pace du
Faire en sorte que votre comparaison d'égalité crée une valeur qui ne varie que lorsque les choses doivent être considérées comme non égales est une stratégie que j'ai utilisée auparavant. Il est parfois plus facile de penser les choses de cette façon. Dans ce cas, vous générez des clés plutôt que des hachages . Tant que vous avez un dériveur de clé qui génère une clé sous une forme prise en charge par les outils existants avec l'égalité de style de valeur, ce qui finit presque toujours par être String, vous pouvez ignorer toute l'étape de hachage et de compartimentage comme vous l'avez dit et simplement utiliser directement un Mapou même un objet simple à l'ancienne en termes de clé dérivée.
binki
1
Une chose à laquelle il faut faire attention si vous utilisez réellement la concaténation de chaînes dans votre implémentation d'un dériveur de clé est que les propriétés de chaîne peuvent devoir être traitées de manière spéciale si elles sont autorisées à prendre n'importe quelle valeur. Par exemple, si vous avez {x: '1,2', y: '3'}et {x: '1', y: '2,3'}, alors String(x) + ',' + String(y)affichera la même valeur pour les deux objets. Une option plus sûre, en supposant que vous puissiez compter sur JSON.stringify()être déterministe, est de profiter de l'échappement de sa chaîne et de l'utiliser à la JSON.stringify([x, y])place.
binki
3

Les comparer directement ne semble pas possible, mais JSON.stringify fonctionne si les clés viennent d'être triées. Comme je l'ai souligné dans un commentaire

JSON.stringify ({a: 1, b: 2})! == JSON.stringify ({b: 2, a: 1});

Mais nous pouvons contourner cela avec une méthode stringify personnalisée. Nous écrivons d'abord la méthode

Stringify personnalisé

Object.prototype.stringifySorted = function(){
    let oldObj = this;
    let obj = (oldObj.length || oldObj.length === 0) ? [] : {};
    for (let key of Object.keys(this).sort((a, b) => a.localeCompare(b))) {
        let type = typeof (oldObj[key])
        if (type === 'object') {
            obj[key] = oldObj[key].stringifySorted();
        } else {
            obj[key] = oldObj[key];
        }
    }
    return JSON.stringify(obj);
}

L'ensemble

Maintenant, nous utilisons un ensemble. Mais nous utilisons un ensemble de chaînes au lieu d'objets

let set = new Set()
set.add({a:1, b:2}.stringifySorted());

set.has({b:2, a:1}.stringifySorted());
// returns true

Obtenez toutes les valeurs

Après avoir créé l'ensemble et ajouté les valeurs, nous pouvons obtenir toutes les valeurs par

let iterator = set.values();
let done = false;
while (!done) {
  let val = iterator.next();

  if (!done) {
    console.log(val.value);
  }
  done = val.done;
}

Voici un lien avec tout dans un fichier http://tpcg.io/FnJg2i

relief.melone
la source
"si les clés sont triées" est un gros si, en particulier pour les objets complexes
Alexander Mills
c'est exactement pourquoi j'ai choisi cette approche;)
relief.melone
2

Peut-être que vous pouvez essayer d'utiliser JSON.stringify()pour faire une comparaison d'objets approfondie.

par exemple :

const arr = [
  {name:'a', value:10},
  {name:'a', value:20},
  {name:'a', value:20},
  {name:'b', value:30},
  {name:'b', value:40},
  {name:'b', value:40}
];

const names = new Set();
const result = arr.filter(item => !names.has(JSON.stringify(item)) ? names.add(JSON.stringify(item)) : false);

console.log(result);

GuaHsu
la source
2
Cela peut fonctionner mais n'est pas obligé de le faire en tant que JSON.stringify ({a: 1, b: 2})! == JSON.stringify ({b: 2, a: 1}) Si tous les objets sont créés par votre programme dans le même ordre, vous êtes en sécurité. Mais pas une solution vraiment sûre en général
soulagement.melone
1
Ah oui, "convertissez-le en chaîne". La réponse de Javascript pour tout.
Timmmm
2

Pour les utilisateurs de Typescript, les réponses des autres (en particulier czerny ) peuvent être généralisées à une belle classe de base de type sécurisé et réutilisable:

/**
 * Map that stringifies the key objects in order to leverage
 * the javascript native Map and preserve key uniqueness.
 */
abstract class StringifyingMap<K, V> {
    private map = new Map<string, V>();
    private keyMap = new Map<string, K>();

    has(key: K): boolean {
        let keyString = this.stringifyKey(key);
        return this.map.has(keyString);
    }
    get(key: K): V {
        let keyString = this.stringifyKey(key);
        return this.map.get(keyString);
    }
    set(key: K, value: V): StringifyingMap<K, V> {
        let keyString = this.stringifyKey(key);
        this.map.set(keyString, value);
        this.keyMap.set(keyString, key);
        return this;
    }

    /**
     * Puts new key/value if key is absent.
     * @param key key
     * @param defaultValue default value factory
     */
    putIfAbsent(key: K, defaultValue: () => V): boolean {
        if (!this.has(key)) {
            let value = defaultValue();
            this.set(key, value);
            return true;
        }
        return false;
    }

    keys(): IterableIterator<K> {
        return this.keyMap.values();
    }

    keyList(): K[] {
        return [...this.keys()];
    }

    delete(key: K): boolean {
        let keyString = this.stringifyKey(key);
        let flag = this.map.delete(keyString);
        this.keyMap.delete(keyString);
        return flag;
    }

    clear(): void {
        this.map.clear();
        this.keyMap.clear();
    }

    size(): number {
        return this.map.size;
    }

    /**
     * Turns the `key` object to a primitive `string` for the underlying `Map`
     * @param key key to be stringified
     */
    protected abstract stringifyKey(key: K): string;
}

L'exemple d'implémentation est alors aussi simple: il suffit de remplacer la stringifyKeyméthode. Dans mon cas, je stringify une uripropriété.

class MyMap extends StringifyingMap<MyKey, MyValue> {
    protected stringifyKey(key: MyKey): string {
        return key.uri.toString();
    }
}

Un exemple d'utilisation est alors comme s'il s'agissait d'un régulier Map<K, V>.

const key1 = new MyKey(1);
const value1 = new MyValue(1);
const value2 = new MyValue(2);

const myMap = new MyMap();
myMap.set(key1, value1);
myMap.set(key1, value2); // native Map would put another key/value pair

myMap.size(); // returns 1, not 2
Jan Dolejsi
la source
-1

Créez un nouvel ensemble à partir de la combinaison des deux ensembles, puis comparez la longueur.

let set1 = new Set([1, 2, 'a', 'b'])
let set2 = new Set([1, 'a', 'a', 2, 'b'])
let set4 = new Set([1, 2, 'a'])

function areSetsEqual(set1, set2) {
  const set3 = new Set([...set1], [...set2])
  return set3.size === set1.size && set3.size === set2.size
}

console.log('set1 equals set2 =', areSetsEqual(set1, set2))
console.log('set1 equals set4 =', areSetsEqual(set1, set4))

set1 est égal à set2 = true

set1 est égal à set4 = faux

Stefan Musarra
la source
2
Cette réponse est-elle liée à la question? La question concerne l'égalité des éléments par rapport à une instance de la classe Set. Cette question semble discuter de l'égalité de deux instances de Set.
czerny
@czerny vous avez raison - je regardais à l'origine cette question stackoverflow, où la méthode ci-dessus pourrait être utilisée: stackoverflow.com/questions/6229197/...
Stefan Musarra
-2

À quelqu'un qui a trouvé cette question sur Google (comme moi) voulant obtenir une valeur d'une carte en utilisant un objet comme clé:

Attention: cette réponse ne fonctionnera pas avec tous les objets

var map = new Map<string,string>();

map.set(JSON.stringify({"A":2} /*string of object as key*/), "Worked");

console.log(map.get(JSON.stringify({"A":2}))||"Not worked");

Production:

Travaillé

DigaoParceiro
la source