Launch Week Day 3: Introducing Organization Notifications in Socket.Learn More →
Socket
Book a DemoSign in
Socket
Book a DemoSign in

ml-sparse-matrix

Package Overview
Dependencies
Maintainers
7
Versions
10
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

ml-sparse-matrix - npm Package Compare versions

Comparing version
0.1.0
 to
0.1.1
+4
-10
package.json
{
"name": "ml-sparse-matrix",
"version": "0.1.0",
"version": "0.1.1",
"description": "Sparse matrix library",
"main": "dist/SparseMatrix.js",
"jsnext:main": "src/SparseMatrix.js",
"main": "src/SparseMatrix.js",
"scripts": {
"test": "npm run build && mocha",
"build": "rollup -c"
"test": "mocha"
},
"files": [
"dist",
"src"

@@ -31,10 +28,7 @@ ],

"mocha": "^2.4.5",
"rollup": "^0.26.3",
"rollup-plugin-commonjs": "^2.2.1",
"rollup-plugin-node-resolve": "^1.5.0",
"should": "^8.3.1"
},
"dependencies": {
"ml-hash-table": "^0.1.1"
"ml-hash-table": "^0.1.2"
}
}
+5
-3
src/SparseMatrix.js

@@ -1,2 +0,2 @@

import HashTable from 'ml-hash-table';
const HashTable = require('ml-hash-table');

@@ -128,3 +128,5 @@ class SparseMatrix {

const result = new SparseMatrix(m * p, n * q);
const result = new SparseMatrix(m * p, n * q, {
initialCapacity: this.cardinality * other.cardinality
});
this.forEachNonZero((i, j, v1) => {

@@ -179,3 +181,3 @@ other.forEachNonZero((k, l, v2) => {

export default SparseMatrix;
module.exports = SparseMatrix;

@@ -182,0 +184,0 @@ /*

-691
dist/SparseMatrix.js
'use strict';
function __commonjs(fn, module) { return module = { exports: {} }, fn(module, module.exports), module.exports; }
/**
* Performs a binary search of value in array
* @param array - Array in which value will be searched. It must be sorted.
* @param value - Value to search in array
* @return {number} If value is found, returns its index in array. Otherwise, returns a negative number indicating where the value should be inserted: -(index + 1)
*/
function binarySearch(array, value) {
var low = 0;
var high = array.length - 1;
while (low <= high) {
var mid = (low + high) >>> 1;
var midValue = array[mid];
if (midValue < value) {
low = mid + 1;
} else if (midValue > value) {
high = mid - 1;
} else {
return mid;
}
}
return -(low + 1);
}
const largestPrime = 0x7fffffff;
const primeNumbers = [
//chunk #0
largestPrime, // 2^31-1
//chunk #1
5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877, 205759,
411527, 823117, 1646237, 3292489, 6584983, 13169977, 26339969, 52679969, 105359939,
210719881, 421439783, 842879579, 1685759167,
//chunk #2
433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379, 452759, 905551, 1811107,
3622219, 7244441, 14488931, 28977863, 57955739, 115911563, 231823147, 463646329, 927292699,
1854585413,
//chunk #3
953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407, 978821, 1957651, 3915341,
7830701, 15661423, 31322867, 62645741, 125291483, 250582987, 501165979, 1002331963,
2004663929,
//chunk #4
1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713, 535481, 1070981, 2141977, 4283963,
8567929, 17135863, 34271747, 68543509, 137087021, 274174111, 548348231, 1096696463,
//chunk #5
31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286973, 573953,
1147921, 2295859, 4591721, 9183457, 18366923, 36733847, 73467739, 146935499, 293871013,
587742049, 1175484103,
//chunk #6
599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081, 620171, 1240361, 2480729,
4961459, 9922933, 19845871, 39691759, 79383533, 158767069, 317534141, 635068283, 1270136683,
//chunk #7
311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089, 328213, 656429, 1312867,
2625761, 5251529, 10503061, 21006137, 42012281, 84024581, 168049163, 336098327, 672196673,
1344393353,
//chunk #8
3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899,
701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557,
359339171, 718678369, 1437356741,
//chunk #9
43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327, 92657, 185323, 370661, 741337,
1482707, 2965421, 5930887, 11861791, 23723597, 47447201, 94894427, 189788857, 379577741,
759155483, 1518310967,
//chunk #10
379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311, 390647, 781301, 1562611,
3125257, 6250537, 12501169, 25002389, 50004791, 100009607, 200019221, 400038451, 800076929,
1600153859,
//chunk #11
13, 29, 59, 127, 257, 521, 1049, 2099, 4201, 8419, 16843, 33703, 67409, 134837, 269683,
539389, 1078787, 2157587, 4315183, 8630387, 17260781, 34521589, 69043189, 138086407,
276172823, 552345671, 1104691373,
//chunk #12
19, 41, 83, 167, 337, 677,
1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899,
701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557,
359339171, 718678369, 1437356741,
//chunk #13
53, 107, 223, 449, 907, 1823, 3659, 7321, 14653, 29311, 58631, 117269,
234539, 469099, 938207, 1876417, 3752839, 7505681, 15011389, 30022781,
60045577, 120091177, 240182359, 480364727, 960729461, 1921458943
];
primeNumbers.sort((a, b) => a - b);
function nextPrime(value) {
let index = binarySearch(primeNumbers, value);
if (index < 0) {
index = -index - 1;
}
return primeNumbers[index];
}
var index = __commonjs(function (module) {
module.exports = newArray
function newArray (n, value) {
n = n || 0
var array = new Array(n)
for (var i = 0; i < n; i++) {
array[i] = value
}
return array
}
});
var newArray = (index && typeof index === 'object' && 'default' in index ? index['default'] : index);
const FREE = 0;
const FULL = 1;
const REMOVED = 2;
const defaultInitialCapacity = 277;
const defaultMinLoadFactor = 0.2;
const defaultMaxLoadFactor = 0.5;
class HashTable {
constructor(options = {}) {
if (options instanceof HashTable) {
this.table = options.table.slice();
this.values = options.values.slice();
this.state = options.state.slice();
this.minLoadFactor = options.minLoadFactor;
this.maxLoadFactor = options.maxLoadFactor;
this.distinct = options.distinct;
this.freeEntries = options.freeEntries;
this.lowWaterMark = options.lowWaterMark;
this.highWaterMark = options.maxLoadFactor;
return;
}
const initialCapacity = options.initialCapacity === undefined ? defaultInitialCapacity : options.initialCapacity;
if (initialCapacity < 0) {
throw new RangeError(`initial capacity must not be less than zero: ${initialCapacity}`);
}
const minLoadFactor = options.minLoadFactor === undefined ? defaultMinLoadFactor : options.minLoadFactor;
const maxLoadFactor = options.maxLoadFactor === undefined ? defaultMaxLoadFactor : options.maxLoadFactor;
if (minLoadFactor < 0 || minLoadFactor >= 1) {
throw new RangeError(`invalid minLoadFactor: ${minLoadFactor}`);
}
if (maxLoadFactor <= 0 || maxLoadFactor >= 1) {
throw new RangeError(`invalid maxLoadFactor: ${maxLoadFactor}`);
}
if (minLoadFactor >= maxLoadFactor) {
throw new RangeError(`minLoadFactor (${minLoadFactor}) must be smaller than maxLoadFactor (${maxLoadFactor})`);
}
let capacity = initialCapacity;
capacity = nextPrime(capacity);
if (capacity === 0) capacity = 1;
this.table = newArray(capacity, 0);
this.values = newArray(capacity, 0);
this.state = newArray(capacity, 0);
this.minLoadFactor = minLoadFactor;
if (capacity === largestPrime) {
this.maxLoadFactor = 1;
} else {
this.maxLoadFactor = maxLoadFactor;
}
this.distinct = 0;
this.freeEntries = capacity;
this.lowWaterMark = 0;
this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
}
clone() {
return new HashTable(this);
}
get size() {
return this.distinct;
}
get(key) {
const i = this.indexOfKey(key);
if (i < 0) return 0;
return this.values[i];
}
set(key, value) {
let i = this.indexOfInsertion(key);
if (i < 0) {
i = -i - 1;
this.values[i] = value;
return false;
}
if (this.distinct > this.highWaterMark) {
const newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
this.rehash(newCapacity);
return this.set(key, value);
}
this.table[i] = key;
this.values[i] = value;
if (this.state[i] === FREE) this.freeEntries--;
this.state[i] = FULL;
this.distinct++;
if (this.freeEntries < 1) {
const newCapacity = chooseGrowCapacity(this.distinct + 1, this.minLoadFactor, this.maxLoadFactor);
this.rehash(newCapacity);
}
return true;
}
remove(key) {
const i = this.indexOfKey(key);
if (i < 0) return false;
this.state[i] = REMOVED;
this.distinct--;
if (this.distinct < this.lowWaterMark) {
const newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
this.rehash(newCapacity)
}
return true;
}
delete(key) {
const i = this.indexOfKey(key);
if (i < 0) return false;
this.state[i] = FREE;
this.distinct--;
if (this.distinct < this.lowWaterMark) {
const newCapacity = chooseShrinkCapacity(this.distinct, this.minLoadFactor, this.maxLoadFactor);
this.rehash(newCapacity)
}
return true;
}
containsKey(key) {
return this.indexOfKey(key) >= 0;
}
indexOfKey(key) {
const table = this.table;
const state = this.state;
const length = this.table.length;
const hash = key & 0x7fffffff;
let i = hash % length;
let decrement = hash % (length - 2);
if (decrement === 0) decrement = 1;
while (state[i] !== FREE && (state[i] === REMOVED || table[i] !== key)) {
i -= decrement;
if (i < 0) i += length;
}
if (state[i] === FREE) return -1;
return i;
}
containsValue(value) {
return this.indexOfValue(value) >= 0;
}
indexOfValue(value) {
const values = this.values;
const state = this.state;
for (var i = 0; i < state.length; i++) {
if (state[i] === FULL && values[i] === value) {
return i;
}
}
return -1;
}
indexOfInsertion(key) {
const table = this.table;
const state = this.state;
const length = table.length;
const hash = key & 0x7fffffff;
let i = hash % length;
let decrement = hash % (length - 2);
if (decrement === 0) decrement = 1;
while (state[i] === FULL && table[i] !== key) {
i -= decrement;
if (i < 0) i += length;
}
if (state[i] === REMOVED) {
const j = i;
while (state[i] !== FREE && (state[i] === REMOVED || table[i] !== key)) {
i -= decrement;
if (i < 0) i += length;
}
if (state[i] === FREE) i = j;
}
if (state[i] === FULL) {
return -i - 1;
}
return i;
}
ensureCapacity(minCapacity) {
if (this.table.length < minCapacity) {
const newCapacity = nextPrime(minCapacity);
this.rehash(newCapacity);
}
}
rehash(newCapacity) {
const oldCapacity = this.table.length;
if (newCapacity <= this.distinct) throw new Error('Unexpected');
const oldTable = this.table;
const oldValues = this.values;
const oldState = this.state;
const newTable = newArray(newCapacity, 0);
const newValues = newArray(newCapacity, 0);
const newState = newArray(newCapacity, 0);
this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor);
this.highWaterMark = chooseHighWaterMark(newCapacity, this.maxLoadFactor);
this.table = newTable;
this.values = newValues;
this.state = newState;
this.freeEntries = newCapacity - this.distinct;
for (var i = 0; i < oldCapacity; i++) {
if (oldState[i] === FULL) {
var element = oldTable[i];
var index = this.indexOfInsertion(element);
newTable[index] = element;
newValues[index] = oldValues[i];
newState[index] = FULL;
}
}
}
forEachKey(callback) {
for (var i = 0; i < this.state.length; i++) {
if (this.state[i] === FULL) {
if (!callback(this.table[i])) return false;
}
}
return true;
}
forEachValue(callback) {
for (var i = 0; i < this.state.length; i++) {
if (this.state[i] === FULL) {
if (!callback(this.values[i])) return false;
}
}
return true;
}
forEachPair(callback) {
for (var i = 0; i < this.state.length; i++) {
if (this.state[i] === FULL) {
if (!callback(this.table[i], this.values[i])) return false;
}
}
return true;
}
}
function chooseLowWaterMark(capacity, minLoad) {
return (capacity * minLoad) | 0;
}
function chooseHighWaterMark(capacity, maxLoad) {
return Math.min(capacity - 2, (capacity * maxLoad) | 0);
}
function chooseGrowCapacity(size, minLoad, maxLoad) {
return nextPrime(Math.max(size + 1, (4 * size / (3 * minLoad + maxLoad)) | 0));
}
function chooseShrinkCapacity(size, minLoad, maxLoad) {
return nextPrime(Math.max(size + 1, (4 * size / (minLoad + 3 * maxLoad)) | 0));
}
class SparseMatrix {
constructor(rows, columns, options = {}) {
if (rows instanceof SparseMatrix) { // clone
const other = rows;
this._init(other.rows, other.columns, other.elements.clone(), other.threshold);
return;
}
if (Array.isArray(rows)) {
const matrix = rows;
rows = matrix.length;
options = columns || {};
columns = matrix[0].length;
this._init(rows, columns, new HashTable(options), options.threshold);
for (var i = 0; i < rows; i++) {
for (var j = 0; j < columns; j++) {
var value = matrix[i][j];
if (this.threshold && Math.abs(value) < this.threshold) value = 0;
if (value !== 0) {
this.elements.set(i * columns + j, matrix[i][j]);
}
}
}
} else {
this._init(rows, columns, new HashTable(options), options.threshold);
}
}
_init(rows, columns, elements, threshold) {
this.rows = rows;
this.columns = columns;
this.elements = elements;
this.threshold = threshold || 0;
}
static eye(rows = 1, columns = rows) {
const min = Math.min(rows, columns);
const matrix = new SparseMatrix(rows, columns, {initialCapacity: min});
for (var i = 0; i < min; i++) {
matrix.set(i, i, 1);
}
return matrix;
}
clone() {
return new SparseMatrix(this);
}
to2DArray() {
const copy = new Array(this.rows);
for (var i = 0; i < this.rows; i++) {
copy[i] = new Array(this.columns);
for (var j = 0; j < this.columns; j++) {
copy[i][j] = this.get(i, j);
}
}
return copy;
}
isSquare() {
return this.rows === this.columns;
}
isSymmetric() {
if (!this.isSquare()) return false;
var symmetric = true;
this.forEachNonZero((i, j, v) => {
if (this.get(j, i) !== v) {
symmetric = false;
return false;
}
return v;
});
return symmetric;
}
get cardinality() {
return this.elements.size;
}
get size() {
return this.rows * this.columns;
}
get(row, column) {
return this.elements.get(row * this.columns + column);
}
set(row, column, value) {
if (this.threshold && Math.abs(value) < this.threshold) value = 0;
if (value === 0) {
this.elements.remove(row * this.columns + column);
} else {
this.elements.set(row * this.columns + column, value);
}
return this;
}
mmul(other) {
if (this.columns !== other.rows)
console.warn('Number of columns of left matrix are not equal to number of rows of right matrix.');
const m = this.rows;
const p = other.columns;
const result = new SparseMatrix(m, p);
this.forEachNonZero((i, j, v1) => {
other.forEachNonZero((k, l, v2) => {
if (j === k) {
result.set(i, l, result.get(i, l) + v1 * v2);
}
return v2;
});
return v1;
});
return result;
}
kroneckerProduct(other) {
const m = this.rows;
const n = this.columns;
const p = other.rows;
const q = other.columns;
const result = new SparseMatrix(m * p, n * q);
this.forEachNonZero((i, j, v1) => {
other.forEachNonZero((k, l, v2) => {
result.set(p * i + k, q * j + l, v1 * v2);
return v2;
});
return v1;
});
return result;
}
forEachNonZero(callback) {
return this.elements.forEachPair((key, value) => {
const i = (key / this.columns) | 0;
const j = key % this.columns;
const r = callback(i, j, value);
if (r === false) return false; // stop iteration
if (r !== value) {
if (r === 0) {
this.elements.remove(key);
} else {
this.elements.set(key, r);
}
}
return true;
});
}
getNonZeros() {
const cardinality = this.cardinality;
const rows = new Array(cardinality);
const columns = new Array(cardinality);
const values = new Array(cardinality);
var idx = 0;
this.forEachNonZero((i, j, value) => {
rows[idx] = i;
columns[idx] = j;
values[idx] = value;
idx++;
return value;
});
return {rows, columns, values};
}
}
SparseMatrix.prototype.klass = 'Matrix';
SparseMatrix.identity = SparseMatrix.eye;
SparseMatrix.prototype.tensorProduct = SparseMatrix.prototype.kroneckerProduct;
/*
Add dynamically instance and static methods for mathematical operations
*/
var inplaceOperator = `
(function %name%(value) {
if (typeof value === 'number') return this.%name%S(value);
return this.%name%M(value);
})
`;
var inplaceOperatorScalar = `
(function %name%S(value) {
this.forEachNonZero((i, j, v) => v %op% value);
return this;
})
`;
var inplaceOperatorMatrix = `
(function %name%M(matrix) {
matrix.forEachNonZero((i, j, v) => {
this.set(i, j, this.get(i, j) %op% v);
return v;
});
return this;
})
`;
var staticOperator = `
(function %name%(matrix, value) {
var newMatrix = new SparseMatrix(matrix);
return newMatrix.%name%(value);
})
`;
var inplaceMethod = `
(function %name%() {
this.forEachNonZero((i, j, v) => %method%(v));
return this;
})
`;
var staticMethod = `
(function %name%(matrix) {
var newMatrix = new SparseMatrix(matrix);
return newMatrix.%name%();
})
`;
var operators = [
// Arithmetic operators
['+', 'add'],
['-', 'sub', 'subtract'],
['*', 'mul', 'multiply'],
['/', 'div', 'divide'],
['%', 'mod', 'modulus'],
// Bitwise operators
['&', 'and'],
['|', 'or'],
['^', 'xor'],
['<<', 'leftShift'],
['>>', 'signPropagatingRightShift'],
['>>>', 'rightShift', 'zeroFillRightShift']
];
for (var operator of operators) {
for (var i = 1; i < operator.length; i++) {
SparseMatrix.prototype[operator[i]] = eval(fillTemplateFunction(inplaceOperator, {name: operator[i], op: operator[0]}));
SparseMatrix.prototype[operator[i] + 'S'] = eval(fillTemplateFunction(inplaceOperatorScalar, {name: operator[i] + 'S', op: operator[0]}));
SparseMatrix.prototype[operator[i] + 'M'] = eval(fillTemplateFunction(inplaceOperatorMatrix, {name: operator[i] + 'M', op: operator[0]}));
SparseMatrix[operator[i]] = eval(fillTemplateFunction(staticOperator, {name: operator[i]}));
}
}
var methods = [
['~', 'not']
];
[
'abs', 'acos', 'acosh', 'asin', 'asinh', 'atan', 'atanh', 'cbrt', 'ceil',
'clz32', 'cos', 'cosh', 'exp', 'expm1', 'floor', 'fround', 'log', 'log1p',
'log10', 'log2', 'round', 'sign', 'sin', 'sinh', 'sqrt', 'tan', 'tanh', 'trunc'
].forEach(function (mathMethod) {
methods.push(['Math.' + mathMethod, mathMethod]);
});
for (var method of methods) {
for (var i = 1; i < method.length; i++) {
SparseMatrix.prototype[method[i]] = eval(fillTemplateFunction(inplaceMethod, {name: method[i], method: method[0]}));
SparseMatrix[method[i]] = eval(fillTemplateFunction(staticMethod, {name: method[i]}));
}
}
function fillTemplateFunction(template, values) {
for (var i in values) {
template = template.replace(new RegExp('%' + i + '%', 'g'), values[i]);
}
return template;
}
module.exports = SparseMatrix;