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