Skip to content

Instantly share code, notes, and snippets.

@toberndo
Created January 26, 2012 14:30
Show Gist options
  • Save toberndo/1683032 to your computer and use it in GitHub Desktop.
Save toberndo/1683032 to your computer and use it in GitHub Desktop.
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