Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Test script with three different algorithms to remove duplicate elements from an array.
if (typeof process === 'undefined') {
process = {
memoryUsage: function() {
return {
heapTotal: 1048576
}
}
}
}
var sortAndDeDup = function(unordered, compFn) {
var start = Date.now();
var heap = process.memoryUsage().heapTotal;
var result = [];
var prev;
unordered.sort(compFn).forEach(function(item) {
var equal = (compFn !== undefined && prev !== undefined)
? compFn(prev, item) === 0 : prev === item;
if (!equal) {
result.push(item);
prev = item;
}
});
console.log('----------------------------------------');
console.log('sort&dedup: %d ms', Date.now() - start);
console.log('heapTotal delta: %d MB', ((process.memoryUsage().heapTotal - heap)/1048576).toFixed(2));
console.log('result array length: %d', result.length);
console.log('----------------------------------------');
return result;
}
var objectDeDup = function(unordered) {
var start = Date.now();
var heap = process.memoryUsage().heapTotal;
var result = [];
var object = {};
unordered.forEach(function(item) {
object[item] = null;
});
//console.log(object);
result = Object.keys(object);
console.log('----------------------------------------');
console.log('object-dedup: %d ms', Date.now() - start);
console.log('heapTotal delta: %d MB', ((process.memoryUsage().heapTotal - heap)/1048576).toFixed(2));
console.log('result array length: %d', result.length);
console.log('----------------------------------------');
//console.log(object);
return result;
}
var loopAndSplice = function(unordered, compFn) {
var start = Date.now();
var heap = process.memoryUsage().heapTotal;
for(var i = 0; i < unordered.length; i++) {
for(var j = i + 1; j < unordered.length; j++) {
var equal = (compFn !== undefined)
? compFn(unordered[i], unordered[j]) === 0
: unordered[i] === unordered[j];
if (equal) {
unordered.splice(j, 1);
j--;
}
}
}
console.log('----------------------------------------');
console.log('loop&splice: %d ms', Date.now() - start);
console.log('heapTotal delta: %d MB', ((process.memoryUsage().heapTotal - heap)/1048576).toFixed(2));
console.log('result array length: %d', unordered.length);
console.log('----------------------------------------');
return unordered;
}
var loopAndShift = function(unordered, compFn) {
var start = Date.now();
var heap = process.memoryUsage().heapTotal;
var result = [];
for(var i = 0; i < unordered.length; i++) {
for(var j = i + 1; j < unordered.length; j++) {
var equal = (compFn !== undefined) ? compFn(unordered[i], unordered[j]) === 0 : unordered[i] === unordered[j];
if (equal) {
var newLength = unordered.length - 1;
if (j < newLength) {
unordered[j] = unordered[newLength];
j--;
}
unordered.length = newLength;
}
}
}
console.log('----------------------------------------');
console.log('loop&shift: %d ms', Date.now() - start);
console.log('heapTotal delta: %d MB', ((process.memoryUsage().heapTotal - heap)/1048576).toFixed(2));
console.log('result array length: %d', unordered.length);
console.log('----------------------------------------');
return unordered;
}
var filterArray = function(unordered, compFn) {
var start = Date.now();
var heap = process.memoryUsage().heapTotal;
var zero = false;
var result = [];
unordered.forEach(function(item) {
result[item] = item;
});
//console.log(result);
if (result[0] !== undefined) zero = true;
result = result.filter(Number);
if (zero === true) result.splice(0,0,0);
console.log('----------------------------------------');
console.log('filterArray: %d ms', Date.now() - start);
console.log('heapTotal delta: %d MB', ((process.memoryUsage().heapTotal - heap)/1048576).toFixed(2));
console.log('result array length: %d', result.length);
console.log('----------------------------------------');
return result;
}
var randomString = function(len, charSet) {
charSet = charSet || 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
var randomString = '';
for (var i = 0; i < len; i++) {
var randomPoz = Math.floor(Math.random() * charSet.length);
randomString += charSet.substring(randomPoz,randomPoz+1);
}
return randomString;
}
var randomStringArray = function(num, len) {
var start = Date.now();
var strings = new Array(num);
for(var i = 0; i < num / 2; i++) {
var string = randomString(len);
var index1 = Math.floor(Math.random() * num);
var index2 = Math.floor(Math.random() * num);
var count = 0;
do {
if (typeof strings[index1] === 'undefined') {
strings[index1] = string;
break;
}
index1 = (index1 < num - 1) ? ++index1 : 0;
count++;
} while(count < num);
count = 0;
do {
if (typeof strings[index2] === 'undefined') {
strings[index2] = string;
break;
}
index2 = (index2 < num - 1) ? ++index2 : 0;
count++;
} while(count < num);
}
console.log('Array generation: %d ms', Date.now() - start);
return strings;
}
var randomIntArray = function(num, range) {
var unordered = [];
var a;
for(var i = 0; i < num; i++) {
a = Math.random() * range;
a = Math.floor(a);
//a = randomString(6, 'abcdef');
//a = randomString(16, 'ab');
unordered.push(a);
}
return unordered;
}
var randomFloatArray = function(num, range) {
var start = Date.now();
var floats = new Array(num);
for(var i = 0; i < num / 2; i++) {
var value = Math.random() * range;
var index1 = Math.floor(Math.random() * num);
var index2 = Math.floor(Math.random() * num);
var count = 0;
do {
if (typeof floats[index1] === 'undefined') {
floats[index1] = value;
break;
}
index1 = (index1 < num - 1) ? ++index1 : 0;
count++;
} while(count < num);
count = 0;
do {
if (typeof floats[index2] === 'undefined') {
floats[index2] = value;
break;
}
index2 = (index2 < num - 1) ? ++index2 : 0;
count++;
} while(count < num);
}
console.log('Array generation: %d ms', Date.now() - start);
return floats;
}
var compareDedup = function(num, range) {
console.log('========================================');
//var unordered = randomIntArray(num, range);
var unordered = randomFloatArray(num, range);
//var unordered = randomStringArray(num, 40);
console.log('Array.length: %d', unordered.length);
//console.log(unordered);
var resulta = sortAndDeDup(unordered, function(a, b) { return (a - b); });
//var resulta = sortAndDeDup(unordered);
//var resultb = objectDeDup(unordered);
//var resultc = loopAndSplice(unordered, function(a, b) { return (a - b); });
//var resultc = loopAndSplice(unordered);
//var resultd = loopAndShift(unordered, function(a, b) { return (a - b); });
//var resulte = filterArray(unordered);
//console.log(resultb);
//console.log(resultc);
}
var num = 10000;
var range = num * 0.6;
compareDedup(num, range);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment