JavaScript中好的数学集实现是什么? [英] What's a good mathematical sets implementation in JavaScript?

问题描述

JavaScript的良好数学集实现在哪里?它应该包括交集，并集，补码和笛卡尔乘积的有效实现.

Where is a good mathematical sets implementation for JavaScript? It should include efficient implementations of intersection, union, complement, and (for bonus points) the Cartesian product.

不，这不是作业.我有一个yubikey，它是一个USB键盘，可以键入从16个键码中选择的序列来键入128位一次性密码(otp).为了使其更有用，软件应基于产生的字符来检测键盘布局，并将这些字符映射回它们在我们"布局中的位置，以与现有后端兼容.

No, it's not homework. I got a yubikey, it is a USB keyboard that types a sequence chosen from 16 keycodes to type a 128-bit one time password (otp). To make it more useful, software should detect the keyboard layout based on the characters produced and map those characters back to what they would be in the "us" layout for compatibility with the existing backend.

因此，我有93个不同的16个字符序列，分别代表yubikey在430个键盘布局中可以键入的所有内容. (为此，许多布局是相同的.)特定otp可能的映射是每个16个字符的序列，其中包含otp中的每个字符.

So I've got 93 different sequences of 16 characters representing everything the yubikey can type in each of 430 keyboard layouts. (Many layouts are the same for this purpose.) The possible mappings for a particular otp is each 16-character sequence that contains every character in the otp.

为了有效地找到它，我使用反向索引将每个可能的字符映射到使用该字符的键盘布局列表.答案是otp中每个唯一字符的反向索引的每个条目的交集.几乎总是以1个元素结束.

To find this efficiently I use a reverse index mapping each possible character to a list of the keyboard layouts that use that character. The answer is the intersection of each entry of the reverse index for each unique character in the otp. This almost always winds up with exactly 1 element.

使用Set()的良好实现编写此跨浏览器会更容易.

It would be easier to write this cross-browser with a good implementation of Set().

到目前为止，代码位于 http://dingoskidneys.com/~dholth/yubikey/

Code so far is at http://dingoskidneys.com/~dholth/yubikey/

推荐答案

我不知道任何现有的实现，但是如果您的set元素是字符串(或具有唯一的字符串表示形式)，则可以轻松使用JavaScript对象.元素将是对象的属性，值可以是任何东西.

I don't know of any existing implementations, but if your set elements are strings (or have a unique string representation) you can use JavaScript objects pretty easily. The elements would be the object properties, and the value could be anything.

// 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，或它不是一个普通的对象).

You could also use item in set or set.hasOwnProperty(item) instead of set[item] === true, but checking by for true explicitly, you automatically ignore any functions that might be attached to the object (in case someone modified Object.prototype, or it's not a plain object).

这篇关于JavaScript中好的数学集实现是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！