Che cosa è una buona implementazione set di matematica in JavaScript?

Question

Dove è una buona implementazione set di matematica per JavaScript? Esso dovrebbe includere implementazioni efficienti di intersezione, unione, complemento, e (per i punti bonus) il prodotto cartesiano.

No, non è compiti. Ho ottenuto un YubiKey, si tratta di una tastiera USB che tipi di sequenza scelta da 16 keycodes di digitare un one time password a 128 bit (OTP). Per renderlo più utile, il software dovrebbe rilevare il layout della tastiera in base ai caratteri prodotte e mappare quei personaggi indietro a quello che sarebbe nel layout "noi" per la compatibilità con il backend esistenti.

Così ho 93 diverse sequenze di 16 caratteri che rappresentano tutto il YubiKey possibile digitare in ciascuna delle 430 layout di tastiera. (Molti layout sono lo stesso per questo scopo.) Le possibili mapping per un particolare OTP è ogni sequenza di 16 caratteri che contiene ogni carattere OTP.

Per trovare questo modo efficiente io uso un indice inverso mappatura ogni personaggio possibile un elenco dei layout di tastiera che utilizzano tale carattere. La risposta è l'intersezione di ogni voce dell'indice inversa per ogni personaggio unico nel otp. Questo si snoda quasi sempre su con esattamente 1 elemento.

Sarebbe più facile scrivere questo cross-browser con una buona implementazione di Set().

Codice finora è a http://dingoskidneys.com/~dholth/yubikey/

Answer 1

Non so di eventuali implementazioni esistenti, ma se i vostri elementi del set sono stringhe (o avere una rappresentazione stringa univoca) è possibile utilizzare gli oggetti abbastanza facilmente JavaScript. Gli elementi sarebbero le proprietà degli oggetti, e il valore potrebbe essere qualsiasi cosa.

// 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.

Si potrebbe anche usare item in set o set.hasOwnProperty(item) invece di set[item] === true, ma il controllo, ad true in modo esplicito, si ignora automaticamente tutte le funzioni che potrebbero essere collegati con l'oggetto (nel caso qualcuno modificata Object.prototype, o non è un oggetto semplice).

Answer 2

jPaq o un'altra libreria JavaScript che implementa le funzioni Array.prototype.reduce e Array.prototype.forEach , è possibile creare una funzione di prodotto cartesiano che accetta due o più array. Ecco il codice per una funzione che calcola il prodotto cartesiano di due o più array:

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;
  }, [[]]);
}

Per quanto riguarda questo essere in una biblioteca, io sono aperto a suggerimenti per la denominazione della funzione in modo che posso aggiungere in jPaq . Tra l'altro, in modo da non plagiare, ho avuto l'idea di utilizzare ridurre da questo dopo .

Answer 3

Underscore ' s ridurre metodo.

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 è una buona biblioteca per fare vettoriale e matrice matematica in Javascript. E 'l'unica libreria matematica mi viene in mente al momento.

Answer 5

Io personalmente piace come si è fatto in jPaq ( http://jpaq.org /documentation/Arrays+as+Sets/1.0/ ). Ecco tre esempi che ho provato con successo:

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 cosa bella di jPaq è il fatto che si può solo scaricare il codice per queste tre funzioni . jPaq rende così non c'è bisogno di scaricare il materiale extra che non verrà utilizzato in ogni caso.

Answer 6

Ho fatto un JavaScript impost all'attuazione riguarda principalmente operazioni difference efficiente, intersection e union. E 'disponibile a GitHub . Forche e nuove operazioni sono i benvenuti! : -)

Answer 7

Nel programma che ha scatenato questa domanda, un insieme è un array e si intersecano è

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

Naturalmente non funziona in IE.