By @P1xt
If there is, I haven’t found a comprehensive reference. Personally, I like seeing “proof” so I tend to just code up a quick node script with a function for each of the various ways I might consider solving a problem (once I’ve winnowed down the possible solutions to the ones that, on the face, seem the least complex - logarithmic or linear time as opposed to quadratic or polynomial) and use the benchmark npm module to give me cold hard data about which of the remaining solutions are the most efficient. Then, I weight differences in efficiency against ease of maintenance and code readability.
For instance, I just ran benchmark on the three solutions in the wiki and the refactor I did on the advanced solution, and my prediction proved true - the basic solution is actually the fastest of the four, which makes sense because for loops are wicked fast, and array methods are slower. The results:
pairwiseBasic x 2,109,026 ops/sec ±0.98% (86 runs sampled)
pairwiseIntermediate x 141,785 ops/sec ±7.66% (75 runs sampled)
pairwiseAdvanced x 368,720 ops/sec ±1.43% (80 runs sampled)
pairwiseRefactored x 1,041,321 ops/sec ±1.82% (77 runs sampled)
Now, I’m going to see if there’s any way to boost the Basic algorithm to make it even faster using some of the tactics from the advanced algorithm.
Edit -
Actually, once I profiled a couple different versions, the fastest I could come up with was:
function pairwiseRefactored2(arr, arg) {
var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;
for(i = 0; i < len; i++) {
for(j = i + 1; j < len; j++) {
if(pairArr[i] + pairArr[j] == arg) {
sum += i + j;
//Set the indices to NaN so that they can't be used in next iteration
pairArr[i] = pairArr[j] = NaN;
break;
}
}
}
return sum;
}
Which adds only a couple minor efficiencies over the basic solution. First, it only calculates the length of the array once and then uses that variable instead of using pairArr.length over and over for each repeat of each loop. Second, it adds a break within the if statement, because if that index was matched and set to NaN, there’s no reason to check it against the rest of the j’s.
I tried using indexOf in place of the second for loop, but it was only modestly faster than my refactor of the advanced solution and still only half(ish) the speed of the basic.
For anyone interested in the giant wall o text:
Benchmark Results and Script
Benchmark Results
pairwiseBasic x 2,181,940 ops/sec ±1.12% (75 runs sampled)
pairwiseIntermediate x 164,147 ops/sec ±0.86% (82 runs sampled)
pairwiseAdvanced x 367,085 ops/sec ±1.75% (75 runs sampled)
pairwiseRefactored x 1,070,409 ops/sec ±1.56% (82 runs sampled)
pairwiseRefactored2 x 2,516,796 ops/sec ±0.95% (79 runs sampled)
pairwiseRefactored3 x 1,131,890 ops/sec ±0.96% (82 runs sampled)
Fastest is pairwiseRefactored2
Benchmark Script
var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;
function pairwiseBasic(arr, arg) {
// Set sum of indices to zero
var sum = 0;
// make a local copy of the arguments object so we don't modify it directly
var pairArr = arr.slice();
// looping from first element
for(i = 0; i < pairArr.length; i++) {
//Looping from second element by setting first element constant
for(j = i + 1; j < pairArr.length; j++) {
// Check whether the sum is equal to arg
if(pairArr[i] + pairArr[j] == arg) {
//Add the indices
sum += i + j;
//Set the indices to NaN so that they can't be used in next iteration
pairArr[i] = pairArr[j] = NaN;
}
}
}
return sum;
}
function pairwiseIntermediate(arr, arg) {
// Create empty array to keep the arrays we will add.
var index = [];
// Loop to check the first number.
for (var a in arr) {
// temporal first number.
var temp = arr[a];
// Second loop to check against the first number.
for (var i = 1; i < arr.length; i++) {
// temporal second number.
var temp2 = arr[i];
// Key element, this check to make sure that the numbers add to arg
// also that the second index is greater than the first, and that neither
// of those indices are already on the array.
if (temp + temp2 === arg && i > a && index.indexOf(+a) === -1 && index.indexOf(+i) === -1) {
// if true then add both indices as integers then stop checking to avoid repeats.
index.push(+a, +i);
break;
}
}
}
// After the two loops are done, check if index is empty to return 0
// or if it is not, then use Array.reduce(callbackFunc) to return the sum
// of the numbers.
if (index.length >= 1) {
var addAll = function(a, b) {
return a + b;
};
return index.reduce(addAll);
} else
return 0;
}
function pairwiseAdvanced(arr, arg) {
// search array for elements that when paired, equal the second argument, then sum their indices
// make a local copy of the arguments object so we don't modify it directly
var pairArr = arr.slice();
return pairArr.reduce( function (a,b,index){ // use native reduce to collect running total of summed indices
var search = arg - b; // get difference of current item so we know what value will sum to arg
// check if search value in rest of the array, but also make sure it doesn't match current search index
if ( pairArr.indexOf(search) != -1 && pairArr.indexOf(search) != index ){
var total = index + pairArr.indexOf(search); // if found, add to the runnning total
pairArr.splice(index,1,NaN); // remove current index from the array
pairArr.splice(pairArr.indexOf(search),1,NaN); // remove the other matched element from the array
return a + total; //return the running total back to reduce for next item
}
return a; // simply return previous total if no operations needed
},0);
}
function pairwiseRefactored(arr, arg) {
var pairArr = arr.slice();
return pairArr.reduce( function (a,b,index){
// find a match that will sum to correct total
var searchIdx = pairArr.indexOf(arg -b);
// if match found and it's not this same index
if ( searchIdx != -1 && searchIdx != index ){
// mark indexes used and add into running total
pairArr[index] = pairArr[searchIdx] = NaN;
return a + index + searchIdx;
}
// else skip this one and move to the next
return a;
},0);
}
function pairwiseRefactored2(arr, arg) {
var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;
for(i = 0; i < len; i++) {
for(j = i + 1; j < len; j++) {
if(pairArr[i] + pairArr[j] == arg) {
sum += i + j;
//Set the indices to NaN so that they can't be used in next iteration
pairArr[i] = pairArr[j] = NaN;
break;
}
}
}
return sum;
}
function pairwiseRefactored3(arr, arg) {
var sum = 0, pairArr = arr.slice(), len = pairArr.length, i, j;
for(i = 0; i < len; i++) {
var searchIdx = pairArr.indexOf(arg - pairArr[i]);
// if match found and it's not this same index
if ( searchIdx != -1 && searchIdx != i ){
// mark indexes used and add into running total
pairArr[i] = pairArr[searchIdx] = NaN;
sum += i + searchIdx;
}
}
return sum;
}
// add tests
suite
.add('pairwiseBasic', function() {
pairwiseBasic([1,4,2,3,0,5], 7);
})
.add('pairwiseIntermediate', function() {
pairwiseIntermediate([1,4,2,3,0,5], 7);
})
.add('pairwiseAdvanced', function() {
pairwiseAdvanced([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored', function() {
pairwiseRefactored([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored2', function() {
pairwiseRefactored2([1,4,2,3,0,5], 7);
})
.add('pairwiseRefactored3', function() {
pairwiseRefactored3([1,4,2,3,0,5], 7);
})
// add listeners
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
// run async
.run({ 'async': true });