Sequence List

The seqlist module encapsulates four algorithms: shuffling, topk, lottery, binary search, array elements can be numbers or objects, and the implementation of the algorithm takes into account the impact of time complexity and space complexity on performance.

Installation

npm install --save seqlist

Usage

let seqlist = require('seqlist');

Tests

To run the test suite, first install the dependencies, then run npm test:

git clone [email protected]:Yann-Wang/seqlistjs.git --depth 1
cd SeqList
npm install
npm test

Method

• shuffle
• topk
• draw
• binarySearch

shuffle(returnOriginal)

• first, get one thrid of the sequence list and use riffle shuffle. Then, use perfect shuffle. At last, get the one third and use perfect shuffle alike.
• time complexity is O(n), space complexity is O(n).
• the array to shuffle should be even.
• when the argument of the method is true, return the original array. Otherwise, return a new array.

let SeqList = require('seqlist');

let arr = [1,2,3,4,5,6,7,8];
let seqlist = new SeqList(arr);
let result = seqlist.shuffle();

console.log(result);

let arr2 = [{x:1},{x:2}];
let seqlist2 = new SeqList(arr2);
let result2 = seqlist2.shuffle();

console.log(result2);

let arr3 = [1,2,3,4,5,6,7,8];
let seqlist3 = new SeqList(arr3);
let result3 = seqlist3.shuffle(true);

console.log(result3);

topk(k,state[,propertyName])

• use heap sort algorithm.
• time complexity is O(nlgk), space complexity is O(1).
• when the state is 'max', return the max top k elements. when the state is 'min', return the min top k elements.

let SeqList = require('seqlist');

let arr = [3,2,1,6,4,8,5,7];
let seqlist = new SeqList(arr);
let result = seqlist.topk(4,'max');

console.log(result);

let arr2 = [{x:3},{x:2},{x:1},{x:6},{x:4},{x:8},{x:5},{x:7}];
let seqlist2 = new SeqList(arr2);
let result2 = seqlist2.topk(4,'min','x');

console.log(result2);

draw(n)

• use disorder algorithm.
• draw k numbers from a array randomly.
• time complexity is O(k), space complexity is O(1).
• return a array which includes k numbers.

let SeqList = require('seqlist');

let arr = [3,2,1,6,4,8,5,7];
let seqlist = new SeqList(arr);
let result = seqlist.draw(3);

console.log(result);


let arr2 = [{x:3},{x:2},{x:1},{x:6},{x:4},{x:8},{x:5},{x:7}];
let seqlist2 = new SeqList(arr2);
let result2 = seqlist2.draw(3);

console.log(result2);

binarySearch(lower_bound,upper_bound,value[,propertyName])

• use binary search algorithm.
• the sequence list should be ordered.
• time complexity is O(lgn), space complexity is O(1).
• return a section which includes the left, but doesn't include the right.

 let SeqList = require('seqlist');
 
 let arr = [0,1,2,3,4,5,5,5,8,9];
 let seqlist = new SeqList(arr);
 let result = seqlist.binarySearch(0,arr.length,5);
 
 console.log(result);
 
 
 let arr2 = [{x:0},{x:1},{x:2},{x:3},{x:4},{x:5},{x:5},{x:5},{x:8},{x:9}];
 let seqlist2 = new SeqList(arr2);
 let result2 = seqlist2.binarySearch(0,arr.length,{x:5},'x');
 
 console.log(result2);

Support

Tested in Node.js 0.10.0-7.5.0