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

Question

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

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

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

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

Было бы проще написать этот кросс-браузер с хорошей реализацией 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

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

Answer 3

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

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

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

Answer 4

Мне лично нравится, как это делается в 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 является тот факт, что вы можете просто download the code for these three functions. jPaq делает это так, что вам не нужно загружать лишние вещи, которые вы не будете использовать в любом случае.

Answer 5

Используя 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. Кстати, чтобы не плагиат, я получил идею использования сокращения от this post.

Answer 6

Использование метода уменьшения Underscore.

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 7

Я сделал JavaScript Set implementation основном касается эффективных difference, intersection и union операций. Доступно at GitHub. Вилки и новые операции очень приветствуются! :-)