N在JavaScript中选择k组合
N在JavaScript中选择k组合
提问于 2018-07-31 23:31:43
有人要求我解决\\binom{n}\n}的问题。我做了以下的实现，我想知道是否有任何反馈。
输入：
n =整数
k =整数
输出：
result =整数数组
约束：
时间：\$O(\binom{n}{k})\$
空间：\$O(\binom{n}{k})\$
输出数组的顺序并不重要。
n和k均为阳性。
资源：
function combinations(n, k) {
let result= [];
function recurse(start, combos) {
if(combos.length === k) {
return result.push(combos.slice());
}
// Check if you can actually create a combo of valid length
// given current start number
// For example: 5 choose 4 can't begin with [3] since it would never have 4 numbers
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;
}我想知道使用回溯解决方案来优化时间是否有什么原因。
// function combinations(n, k) {
// let result = []
// function combine(combo, currentNumber){
// if(combo.length === k) {
// result.push(combo);
// return;
// }
// if(currentNumber > n) {
// return;
// }
// let newCombo1 = combo.slice();
// let newCombo2 = combo.slice();
// newCombo2.push(currentNumber);
// combine(newCombo2, currentNumber + 1);
// combine(newCombo1, currentNumber + 1);
// }
// combine([], 1);
// return result;
// }
// speed: 1120.756 ms
//backtracking method
function combinations(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;
}
console.time("Naive Combinations")
console.log(combinations(20, 10))
console.timeEnd("Naive Combinations")
// speed: 320.756 ms回答 1
Code Review用户
回答已采纳
发布于 2018-08-05 17:41:25
性能测试.
请注意，这个答案是关于性能，而不是复杂性。
为什么会有奇怪的性能结果？
结果不同的原因是测试不佳。
与大多数语言不同的是，JavaScript从未完全编译过。在后台，有多个级别的优化引擎，它们查看正在运行的代码，并在代码运行时应用优化。
然而，优化器在第一次运行代码时有一个最明显的代价。它还可以比其他代码更快地优化一些代码。
为了比较函数，您需要让优化器完成它的任务(每个浏览器都有非常不同的优化方法)。只有在该函数运行了几次之后，才能开始得到准确的结果。
当我测试您的代码时，我发现“回溯”方法平均要慢不到5%。
测试示例
代码段是一个向下和肮脏的性能测试器，它将测试多个周期的函数，并给出函数时间的平均结果。
请注意，结果不是单个调用，而是连续多个调用的结果。测试人员将首先确保测试在启动前不低于定时器分辨率。
例如，我一直将测试周期保持在较低的水平，但数据仍然不稳定，在优化器满意之前需要更多的时间。
其中包括问题中的两个函数，以及使用不递归调用和修改一个函数的替代方法。
性能提高.
在你的功能中
函数组合(n，k){ let result= []；函数递归(启动，组合){ if(combos.length === k) {返回result.push(combos.slice())；} if(combos.length +(result=+ 1) < k) { return；} recurse(start + 1，combos)；combos.push( start )；recurse(start + 1，combos)；combos.pop()；} recurse(1，[])；返回结果；}
combos数组将作为参数传递。没有必要这样做，因为它是同一个数组。在recurse函数之外声明它。
您在一个路径中返回数组，而另两个路径返回undefined。将返回类型保持不变。
您正在递归，然后测试combos.length === k，但是您可以在调用之前进行测试，省去了调用的需要。
对于箭头函数来说，接缝是一个轻微的偏爱，因此将recurse函数更改为这样。
修改后的函数始终是最快的。
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;
}测试示例
注意，时间是调整的，以确保良好的时间分辨率。作为绝对性能数字，结果是毫无意义的。它们只有在测试运行中才具有比较意义。
//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 Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/200700
复制相关文章
相似问题
腾讯云开发者
