Ce qui est une bonne mise en œuvre des ensembles mathématiques en JavaScript?

Question

Où est une bonne mise en œuvre des ensembles mathématiques pour JavaScript? Il devrait inclure des implémentations efficaces d'intersection, union, complément, et (pour les points de bonus), le produit cartésien.

Non, ce n'est pas devoirs. Je suis un yubikey, il est un clavier USB type une séquence choisie parmi 16 keycodes pour taper un 128 bits d'un mot de passe de temps (BdP). Pour le rendre plus utile, le logiciel doit détecter la disposition du clavier en fonction des caractères produits et cartographier ces caractères revenir à ce qu'ils seraient dans la mise en page « nous » pour la compatibilité avec le back-end existantes.

J'ai 93 séquences différentes de 16 caractères représentant tout le yubikey peut taper dans chacune des 430 configurations de clavier. (De nombreuses configurations sont identiques à cette fin.) Les applications possibles pour un OTP particulier est chaque séquence de 16 caractères qui contient tous les caractères de l'OTP.

Pour ce efficace, j'utiliser un index inverse cartographie chaque caractère possible d'une liste des configurations de clavier qui utilisent ce caractère. La réponse est l'intersection de chaque entrée de l'index inverse pour chaque caractère unique dans la BdP. Cela serpente presque toujours avec l'élément exactement 1.

Il serait plus facile d'écrire cette croix-navigateur avec une bonne mise en œuvre de Set().

code à ce jour est http://dingoskidneys.com/~dholth/yubikey/

Answer 1

Je ne connais pas d'implémentations existantes, mais si vos éléments de réglage sont des chaînes (ou une représentation de chaîne unique) vous pouvez utiliser JavaScript assez facilement des objets. Les éléments seraient les propriétés de l'objet, et la valeur pourrait être quelque chose.

// Make a set from an array of elements
function makeSet(items) {
    var set = {};
    for (var i = 0; i < items.length; i++) {
        set[items[i]] = true;
    }
    return set;
}

function copyInto(s, copy) {
    for (var item in s) {
        if (s[item] === true) {
            copy[item] = true;
        }
    }
}

function union(s1, s2) {
    var u = {};
    copyInto(s1, u);
    copyInto(s2, u);
    return u;
}

function intersection(s1, s2) {
    var i = {};
    for (var item in s1) {
        if (s1[item] === true && s2[item] === true) {
            i[item] = true;
        }
    }
    return i;
}

function difference(s1, s2) {
    var diff = {};
    copyInto(s1, diff);
    for (var item in s2) {
        if (s2[item] === true) {
            delete diff[item];
        }
    }
    return diff;
}

// etc.

Vous pouvez également utiliser item in set ou set.hasOwnProperty(item) au lieu de set[item] === true, mais la vérification par des true explicitement, vous ignorez automatiquement les fonctions qui pourraient être attachés à l'objet (au cas où quelqu'un modifié Object.prototype, ou ce n'est pas un objet ordinaire).

Answer 2

En utilisant jPaq ou d'une autre bibliothèque JavaScript qui implémente les fonctions Array.prototype.reduce et Array.prototype.forEach , vous pouvez créer une fonction de produit cartésien qui accepte deux ou plusieurs tableaux. Voici le code pour une fonction qui calcule le produit cartésien de deux ou plusieurs tableaux:

function cartesianProductOf() {
  return Array.prototype.reduce.call(arguments, function(a, b) {
    var ret = [];
    a.forEach(function(a) {
      b.forEach(function(b) {
        ret.push(a.concat([b]));
      });
    });
    return ret;
  }, [[]]);
}

En ce qui concerne cet être dans une bibliothèque, je suis ouvert aux suggestions pour la désignation de la fonction pour que je puisse l'ajouter dans jPaq . Soit dit en passant, pour ne pas plagier, j'ai eu l'idée d'utiliser de réduire cette après.

Answer 3

Utilisation title="Underscore"> Souligné 's Diminuez méthode.

function cartesianProductOf(){
    return _.reduce(arguments, function(mtrx, vals){
        return _.reduce(vals, function(array, val){
            return array.concat(
                _.map(mtrx, function(row){ return row.concat(val); })
            );
        }, []);
    }, [[]]);
}

Answer 4

Sylvester est une bonne bibliothèque pour faire de vecteur et de la matrice Math en Javascript. Il est la seule bibliothèque de mathématiques que je peux penser en ce moment.

Answer 5

Personnellement, je aime la façon dont cela est fait dans jPaq ( http://jpaq.org /documentation/Arrays+as+Sets/1.0/ ). Voici trois exemples que j'ai testé avec succès:

alert([1,2,3,4,5].subtract([2,3,5]));  // evaluates to [1,4]
alert([1,2,5].union([1,3,4,5]));  // evaluates to [1,2,5,3,4]
alert([1,2,3,5].intersect([0,1,2,4,6]));  // evaluates to [1,2]

La bonne chose à propos jPaq est le fait que vous pouvez simplement télécharger le code pour ces trois fonctions . jPaq fait en sorte que vous ne devez pas télécharger les choses supplémentaires que vous ne comptez pas utiliser de toute façon.

Answer 6

Je l'ai fait un JavaScript Définir la mise en œuvre principalement concerné par les opérations difference efficaces, intersection et union. Il est disponible à GitHub. Forks et de nouvelles opérations sont les bienvenus! : -)

Answer 7

Dans le programme qui a déclenché cette question, un ensemble est un tableau et est entrecoupent

s = [1,2,3];
q = [3,4,5];
sq = s.filter(function(x) {
    return q.indexOf(x) >= 0;
});

Bien sûr, il ne fonctionne pas par exemple.