Какова хорошая реализация математических наборов в JavaScript?

Question

Где хорошая реализация математических наборов для JavaScript?Он должен включать эффективные реализации пересечения, объединения, дополнения и (в качестве бонуса) декартова произведения.

Нет, это не домашнее задание.У меня есть yubikey, это USB-клавиатура, которая набирает последовательность, выбранную из 16 кодов клавиш, для ввода 128-битного одноразового пароля (otp).Чтобы сделать его более полезным, программное обеспечение должно определять раскладку клавиатуры на основе созданных символов и отображать эти символы обратно в раскладку «США» для совместимости с существующим серверным интерфейсом.

Итак, у меня есть 93 различных последовательности по 16 символов, представляющих все, что может ввести yubikey в каждой из 430 раскладок клавиатуры.(Для этой цели многие макеты одинаковы.) Возможные сопоставления для конкретного otp — это каждая 16-символьная последовательность, содержащая все символы в otp.

Чтобы найти это эффективно, я использую обратный индекс, сопоставляющий каждый возможный символ со списком раскладок клавиатуры, которые используют этот символ.Ответом является пересечение каждой записи обратного индекса для каждого уникального символа в otp.Почти всегда получается ровно 1 элемент.

Было бы проще написать этот кроссбраузер с хорошей реализацией Set().

Код на данный момент находится на http://dingoskidneys.com/~dholth/yubikey/

Answer 1

Я не знаю ни одной существующей реализации, но если ваши элементы набора являются строками (или имеют уникальное строковое представление), вы можете довольно легко использовать объекты JavaScript.Элементами будут свойства объекта, а значение может быть любым.

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

Вы также можете использовать item in set или set.hasOwnProperty(item) вместо set[item] === true, но проверяю true явно вы автоматически игнорируете любые функции, которые могут быть прикреплены к объекту (в случае, если кто-то изменил Object.prototype или это не простой объект).

Answer 2

Используя jPaq или другую библиотеку JavaScript, реализующую функции Array.prototype.reduce и Array.prototype.forEach, вы можете создать декартову функцию произведения, которая принимает два или более массивов.Вот код функции, которая вычисляет декартово произведение двух или более массивов:

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

Поскольку это библиотека, я открыт для предложений по именованию функции, чтобы я мог добавить ее в jPaq.Кстати, чтобы не заниматься плагиатом, идея использовать сокращение у меня возникла из эта почта.

Answer 3

С использованием Нижнее подчеркиваниеметод сокращения.

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

Сильвестр — хорошая библиотека для выполнения векторных и матричных вычислений на Javascript.Это единственная математическая библиотека, о которой я сейчас могу думать.

Answer 5

Мне лично нравится, как это сделано в jPaq (http://jpaq.org/documentation/Arrays+as+Sets/1.0/).Вот три примера, которые я успешно опробовал:

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]

Хорошая особенность jPaq заключается в том, что вы можете просто скачайте код для этих трёх функций.jPaq позволяет вам не загружать дополнительные материалы, которые вы все равно не будете использовать.

Answer 6

Я сделал JavaScript Установить реализацию в основном касается эффективного difference, intersection и union операции.Это доступно на GitHub.Форки и новые операции приветствуются!:-)

Answer 7

В программе, которая вызвала этот вопрос, набор — это массив, а пересечение — это

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

Конечно, это не работает, т.е.