Performance testing.
Please note this answer is about performance not complexity.
Why the strange performance result?
The reason for the different results is down to poor testing.
JavaScript unlike most languages is never fully compiled. In the background there are multi level optimization engines that look at the running code and apply optimizations as the code is running.
The optimizer however has a penalty that is most evident when the code is first run. It can also optimize some code quicker than others.
To compare functions you need to let the optimizer do its thing (each browser have very different optimizing methods). Only after the function has been run several times can you start to get accurate results.
When I tested your code I found that the "backtracking" method was on average less than 5% slower.
Testing example
The snippet is a down and dirty performance tester that will test functions over many cycles and give a mean result of the function time.
Note that the result is not of a single call but that of many calls in a row. The tester will first make sure that the tests are not below the timer resolution before starting.
As an example I have kept the total test cycles low, but the numbers are still not stable and would take some more time before the optimizer is happy.
Included are your two functions as in the question, and alternative method using no recursive calls and a modification of one of your functions.
Performance increase.
In you function
function combinations(n, k) {
let result= [];
function recurse(start, combos) {
if(combos.length === k) {
return result.push(combos.slice());
}
if(combos.length + (n - start + 1) < k){
return;
}
recurse(start + 1, combos);
combos.push(start);
recurse(start + 1, combos);
combos.pop();
}
recurse(1, []);
return result;
}
The combos array is being passed as an argument. There is no need to as it is the same array. Declare it outside the recurse function.
You are returning the array in one path and the other two your return undefined. Keep the return types the same.
You are recursing and then test for combos.length === k but you can test before the call saving the need to call.
There seams to be a slight favor for an arrow function, so changed the recurse function to such.
The modified function is consistently the quickest.
function combinationsAV2(n, k) {
const result= [];
const combos = [];
const recurse = start => {
if (combos.length + (n - start + 1) < k) { return }
recurse(start + 1);
combos.push(start);
if(combos.length === k) {
result.push(combos.slice());
}else if(combos.length + (n - start + 2) >= k){
recurse(start + 1);
}
combos.pop();
}
recurse(1, combos);
return result;
}
Testing example
Note that the timing is adjusted to ensure good time resolution. The results are meaningless as absolute performance figures. They only have comparative meaning within a test run.
//n!/(r!(n-r)!)
Math.factorials = [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000];
Math.biCof = (n,r) => Math.factorials[n] / (Math.factorials[r] * Math.factorials[n-r]);
function combinationsG(n, k) {
const result= [];
const combo= [];
const last = k - 1; // points to last item in combo
var i = k;
while (i--) {
combo.push(k - i);
}
const starts = [...combo];
var pos,count = Math.biCof(n,k)
while (count --) {
result.push([...combo]);
combo[last] += 1;
if (combo[last] > n) {
pos = 0;
while (combo[last - pos] > n-pos) {
pos += 1;
combo[last-pos] += 1;
if (pos === k) { break }
}
while (pos > 0) {
combo[last-pos+1] = combo[last-pos] + 1
pos --;
}
}
}
return result;
}
function combinationsAV2(n, k) {
const result= [];
const combos = [];
const recurse = start => {
if(combos.length + (n - start + 1) < k){
return;
}
recurse(start + 1);
combos.push(start);
if(combos.length === k) {
result.push(combos.slice());
}else if(combos.length + (n - start + 2) >= k){
recurse(start + 1);
}
combos.pop();
}
recurse(1, combos);
return result;
}
function combinationsA(n, k) {
let result= [];
function recurse(start, combos) {
if(combos.length === k) {
return result.push(combos.slice());
}
if(combos.length + (n - start + 1) < k){
return;
}
recurse(start + 1, combos);
combos.push(start);
recurse(start + 1, combos);
combos.pop();
}
recurse(1, []);
return result;
}
//backtracking method
function combinationsB(n, k) {
let result = [];
let stack = [];
function combine(currentNumber){
if(stack.length === k) {
let newCombo = stack.slice();
result.push(newCombo);
return;
}
if(currentNumber > n) {
return;
}
stack.push(currentNumber);
combine(currentNumber + 1);
stack.pop();
combine(currentNumber + 1);
}
combine(1);
return result;
}
/*===========UTIL to display results============*/
function log(data) {
const div = document.createElement("div");
div.textContent = data;
logger.appendChild(div);
}
log.clear = function(){ logger.innerHTML = "" }
/*================TESTING CODE==================*/
const tests = {
data : [15,3], // arguments for function calls
functions : [ { // functions to test and a name as reference
name : "Backtracking method",
func : combinationsB,
},{
name : "Native Combinations",
func : combinationsA,
},{
name : "Modified Native",
func : combinationsAV2,
},{
name : "While loops",
func : combinationsG,
},
],
cycles : 100,
prepCycles : 30, // Number of cycles to run before testing. This
// is a optimizer shake down and use to ensure test times
// are above the timerResolution
testPerCycle : 20,
timedCycleTrim : 1, // used to increase runtime if time to low
timedCycles : 2, // number of calls to test function * timedCycleTrim
timerResolution : 0.4, // this is the minimum resolution of the timer in ms
// Note that due to security concerns performance timers
// have had the time resolution reduced to stop
// code attempting to access CPU caches
testInterval : 10, // Time between test cycles.
resolutionError : false, // If the run time of the timedCycles is lower than
// the timer resolution then the accumulating error
// makes results meaningless. This flag is set true
// when test time is too small. In the prep phase
// timedCycleTrim is used to increase the time
// till a time above timerResolution is found
}
log.clear()
startTest(tests);
function startTest(tests){
function doCycle(test){
var totalTime, count, time, j, i;
const data = tests.data;
i = tests.testPerCycle;
totalTime = count = 0;
while (i--) {
j = tests.timedCycles * tests.timedCycleTrim;
/* ========= TEST LOOP ==========*/
const now = performance.now();
while (j --) { test.func(...data) }
time = performance.now() - now;
if (time <= tests.timerResolution) {
tests.resolutionError = true;
return;
}
count ++;
totalTime += time;
}
test.count += count;
test.time += totalTime;
test.mean = test.time / test.count;
}
function resetTest(test){
test.count = 0;
test.time = 0;
}
function showTestStatus(test) {
if (test.count) {
log(`Test '${test.name}' mean ${test.mean.toLocaleString(undefined,numFormat)}ms`);
// log(`Total ${test.time.toLocaleString(undefined,numFormat)}ms over ${test.count} cycles`);
} else {
log(`Test '${test.name}' not yet tested`);
}
}
function eachTest(call,testArr = tests.functions){
testArr.forEach(call)
}
const selectors = {
index : 0,
random() { return tests.functions[Math.random() * tests.functions.length | 0] },
ordered() { return tests.functions[(selectors.index++) % tests.functions.length ] },
}
function setupPrep() {
selectors.index = 0;
cycles = tests.prepCycles * tests.functions.length;
selector = selectors.ordered;
prepPhase = true;
tests.resolutionError = false;
eachTest(resetTest);
setTimeout(doNextCycle, tests.testInterval);
}
function doNextCycle() {
const test = selector();
doCycle(test)
cycles --;
if (tests.resolutionError) {
if (prepPhase) {
if (tests.timedCycleTrim === 100) {
log(`Test '${test.name}' is not responding to cycle trim. Test aborted` );
} else {
tests.timedCycleTrim += 2;
log(`Timed cycles increased to : ${tests.timedCycles * tests.timedCycleTrim}` );
setupPrep();
}
} else {
log(`'${test.name}' failed, function runtime too low. Test aborted.` );
}
} else {
if (cycles) {
if (!prepPhase) {
log.clear();
log(`Test status ${cycles / (tests.cycles * tests.functions.length) * 100 | 0}%`);
eachTest(showTestStatus);
}
setTimeout(doNextCycle, tests.testInterval);
} else if (!prepPhase) {
log.clear();
log("Testing complete...");
log("Calls per cycles : " + tests.timedCycles * tests.timedCycleTrim);
log("----------------------------------------");
eachTest(showTestStatus,[...tests.functions].sort((a, b) => a.mean - b.mean));
} else {
log("Prep complete...")
prepPhase = false;
cycles = tests.cycles * tests.functions.length;
selector = selectors.random;
eachTest(resetTest);
setTimeout(doNextCycle, tests.testInterval);
}
}
}
const numFormat = {minimumFractionDigits: 3, maximumFractionDigits: 3};
var cycles, selector, prepPhase;
log("Starting tests. Calibrating run times... ");
setupPrep();
}
<code id="logger"></code>
