良い数学的な実装はJavaScriptで実装されていますか？

Question

JavaScriptの数学的な実装はどこですか？交叉、結合、補完、および（ボーナスポイントのための）デカルト積を効率的に実装する必要があります。

いいえ、宿題ではありません。私はyubikeyを手に入れました。これは、16ビットのキーコードから選択したシーケンスを入力して128ビットのワンタイムパスワード（otp）を入力するUSB​​キーボードです。ソフトウェアをより有用にするために、ソフトウェアは生成された文字に基づいてキーボードレイアウトを検出し、それらの文字を既存のバックエンドとの互換性のために「us」レイアウトに戻します。

私は430種類のキーボードレイアウトのそれぞれにyubikeyが入力できるすべての文字を表す16通りの異なる文字列を93種類用意しています。 （この目的のために多くのレイアウトが同じです。）特定のotpの可能なマッピングは、otpのすべての文字を含む16文字の各シーケンスです。

これを効率的に見つけるために、可能な各文字をその文字を使用するキーボードレイアウトのリストにマッピングする逆インデックスを使用します。答えは、otp内の各ユニーク文字の逆インデックスの各エントリの共通部分です。これはほぼ常に1つの要素で終わります。

Set()の優れた実装でこのクロスブラウザを書く方が簡単です。

コードは、これまでhttp://dingoskidneys.com/~dholth/yubikey/

Answer 1

既存の実装についてはわかりませんが、設定された要素が文字列（または一意の文字列表現）であれば、JavaScriptオブジェクトをかなり簡単に使用できます。要素はオブジェクトのプロパティで、値は何でもかまいません。あなたはまた、代わりにset[item] === trueのitem in setまたはset.hasOwnProperty(item)を使用することができますが、trueされるのをチェックすると、明示的に、あなたは自動的に（場合は、誰かがのObject.prototypeを変更し、またはそうでないオブジェクトに添付される可能性があります任意の機能を無視

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

平らなオブジェクト）。

Answer 2

SylvesterであるがJavaScriptで、ベクトルや行列の数学を行うための良いライブラリです。私が今思う唯一の数学ライブラリです。この質問をきっかけプログラムで

Answer 3

、セットが配列され、交差する、それはIEで動作しませんもちろん

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

です。

Answer 4

私は個人的にはjPaq（http://jpaq.org/documentation/Arrays+as+Sets/1.0/）の仕組みが好きです。ここで私は成功して試験した3つの例です：

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またはArray.prototype.reduceおよびArray.prototype.forEach関数を実装する別のJavaScriptライブラリを使用すると、2つ以上の配列を受け入れるデカルト積関数を作成できます。ここでは、2つの以上のアレイのデカルト積を計算する関数のコードは次のとおりです。

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からreduceを使う考えをしました。

Answer 6

Underscoreのreduceメソッドを使用します。

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

私は、効率的なdifference、intersectionとunion事業を主とするJavaScript Set implementationをやりました。利用可能なのはat GitHubです。フォークと新しい事業は大歓迎です！ :-)