递归算法无法在指定时间内完成测试 [英] Recursive algorithm fails to complete tests in allotted time
问题描述
我正在做的测试需要二进制层析成像算法.提供一组38个测试值来测试正确性，但是完成所有测试也有1个CPU秒的时间限制.问题如下:
I was doing a test that required an algorithm for Binary Tomography. A set of 38 test values are supplied that test correctness, but there is also a time limit of 1 CPU sec to complete all the tests. The problem is as follows:
如果存在一个m×n矩阵A，且每个元素为0或1，则输出是"，这样
Output "Yes" if there exists an m-by-n matrix A, with each element either being 0 or 1, such that
否则输出否".
为每个测试提供2个阵列:
For each test, 2 arrays are provided:
- r (矩阵中每一行的总和)
- c (矩阵中每一列的总和)
- r (the sum of each row in the matrix)
- c (the sum of each column in the matrix)
在等式中:
- m 是 r 数组的长度，其中 1< = m
- n 是 c 数组的长度，其中 n< = 1000
- ri 是 r 的元素，其中 0< = ri< = n
- cj 是 c 的元素，其中 0< = cj< = m
- m is the length of the r array, where 1 <= m
- n is the length of the c array, where n <= 1000
- ri is an element of r, where 0 <= ri <= n
- cj is an element of c, where 0 <= cj <= m
是"示例
m = 3;n = 4；r = [2，3，2];c = [1、1、3、2];
m = 3; n = 4; r = [2, 3, 2]; c = [1, 1, 3, 2];
否"示例
m = 3;n = 3；r = [0，0，3];c = [0，0，3];
m = 3; n = 3; r = [0, 0, 3]; c = [0, 0, 3];
我有一个解决方案似乎可以给出正确的答案，但是它只能在超过1秒的CPU时间之前管理12/38个测试.
I have a solution that appears to give correct answers, however it only manages 12 / 38 tests before the 1 second of CPU time is exceeded.
我最初是在ES5中编写代码，然后返回并转换为ES3，以尝试从中获得更多性能.(最初将9个测试作为ES5管理).似乎没有什么可以改进当前算法的性能了(除非我弄错了).这使我相信我的算法是错误的，并且必须有一个更快的算法来执行此操作.我做了很多阅读，试图找到一个，结果很头疼:)
I originally wrote the code in ES5 and then went back and converted to to ES3 to try and get more performance out of it. (originally managed 9 tests as ES5). There doesn't seem a great deal left that I can do to the current algorithm to improve the performance (unless I am mistaken). This leads me to believe that my algorithm is at fault an that there must be a faster algorithm for doing this. I did a ton of reading trying to find one and ended up with a headache :)
因此，我正在求助于社区，看看是否有人可以提出比我目前正在使用的算法更快的算法.
So I'm turning to the community to see if anyone can suggest a faster algorithm than I am currently using.
'use strict';
const ZEROS = (function (seed) {
let string = seed;
for (let i = 0; i < 19; i += 1) {
string += seed;
}
return string;
}('00000000000000000000000000000000000000000000000000'));
const ZEROSLEN = ZEROS.length;
const permutate = function (n, ri) {
const result = [];
const memoize = {};
let count = 0;
do {
const bin = count.toString(2);
if (ZEROSLEN + bin.length > ZEROSLEN + n) {
break;
}
if (!memoize[bin] && (bin.split('1').length - 1) === ri) {
const string = (ZEROS + bin).slice(-n);
const sLen = string.length;
const perm = new Array(sLen);
for (let i = sLen - 1; i >= 0; i -= 1) {
perm[i] = +string[i];
}
memoize[bin] = result.push(perm);
}
count += 1;
} while (count);
return result;
};
const getMatrixSum = function (n, matrix) {
const mLength = matrix.length;
const rows = new Array(mLength);
const a = new Array(n);
const last = mLength - 1;
for (let x = n - 1; x >= 0; x -= 1) {
for (let y = last; y >= 0; y -= 1) {
rows[y] = matrix[y][x];
}
let sum = 0;
for (let i = rows.length - 1; i >= 0; i -= 1) {
sum += rows[i];
}
a[x] = sum;
}
return a;
};
const isEqual = function (a, b) {
const length = a.length;
if (length !== b.length) {
return false;
}
for (let i = length - 1; i >= 0; i -= 1) {
if (a[i] !== b[i]) {
return false;
}
}
return true;
};
const addRow = function (i, prev, r, c, result) {
if (result) {
return result;
}
const n = c.length;
const ri = r[i];
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
const p = permutate(n, ri);
const m = r.length;
const rsLast = m - 1;
const nextI = i + 1;
for (let x = p.length - 1; x >= 0; x -= 1) {
const permutation = p[x];
const next = prev.slice();
next.push(permutation);
const sums = getMatrixSum(n, next);
if (i < rsLast) {
let memo = 0;
for (let j = sums.length - 1; j >= 0; j -= 1) {
if (sums[j] > c[j]) {
memo += 1;
}
}
if (!memo && addRow(nextI, next, r, c, result)) {
return true;
}
} else if (isEqual(sums, c)) {
return true;
}
}
return false;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
return addRow(0, [], r, c, false) ? 'Yes' : 'No';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));可能值得注意的是，这些测试是在SpiderMonkey版本JavaScript-C24.2.0上运行的
It may be worth noting that the tests are being run on SpiderMonkey version JavaScript-C24.2.0
参考:
https://en.wikipedia.org/wiki/Discrete_tomography
https://open.kattis.com/problems/tomography
推荐答案
我还没有准备好进行测试，但是事件发生后我发现了一种效率更高的算法.
I didn't have this ready for my test, but I found a far more efficient algorithm after the event.
'use strict';
const sortNumber = function (a, b) {
return b - a;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
while (r.length) {
c.sort(sortNumber);
const ri = r.pop();
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
if (ri) {
if (!c[ri - 1]) {
return 'No';
}
for (let j = ri - 1; j >= 0; j -= 1) {
c[j] -= 1;
}
}
}
for (let j = n - 1; j >= 0; j -= 1) {
if (c[j]) {
return 'No';
}
}
return 'Yes';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));这篇关于递归算法无法在指定时间内完成测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
