javascript - 为什么这些筛子优化会破坏我的代码?
问题描述
我怎样才能纠正他们的工作?我正在尝试根据之前的建议优化我的筛子,但在这两种情况下,代码都会中断:
递增j = j + ( i * 2)
会破坏代码。
显然,我和其他人一样缺少一些关于优化的概念。但总的来说,您只需将素数的所有倍数标记为非素数即可。优化是下一步。
// prime-3
// sieve implementation
function prime3(n) {
const sieve = (new Array(n)).fill(true);
// Only iterate up to the square root n for marking
for (let i = 2; i * i <= n; i += 1) {
if (sieve[i]) {
// recommended optimization breaks the code
// j = j + ( i * 2 )
for (let j = i * i; j <= n; j = j + i) {
sieve[j] = false;
}
}
}
return makePrimes(sieve, n);
};
function makePrimes(sieve, n) {
let primes = [];
for (let i = 2; i < n; i++) {
if (sieve[i]) {
primes.push(i);
}
}
return primes;
}
console.log(prime3(100));
解决方案
你的优化需要先去掉偶数后应用(除了2)。因为当 时i==2
,您通过递增有效地跳过了所有偶数i*2
。
这是一个工作代码:
// prime-3
// sieve implementation
function prime3(n) {
let sieve = (new Array(n)).fill(true);
for (let i = 4; i < n; i+=2) {
sieve[i] = false;
}
// Only iterate up to the square root n for marking
for (let i = 2; i * i <= n; i += 1) {
if (sieve[i]) {
// now it works
// j = j + ( i * 2 )
for (let j = i * i; j <= n; j = j + i*2) {
sieve[j] = false;
}
}
}
return makePrimes(sieve, n);
};
function makePrimes(sieve, n) {
let primes = [];
for (let i = 2; i < n; i++) {
if (sieve[i]) {
primes.push(i);
}
}
return primes;
}
console.log(prime3(100));
编辑
刮这个。进一步的测试确实表明 prime3 比简单的筛子快 3 倍。
该代码虽然有效,但似乎有太多技巧要做,并引入了额外的计算和混乱。在我的比较中,一个简单的筛选代码(如下所示)执行答案中的代码。同样,KISS 是原则。
原始答案中的脚本用了 317 毫秒来筛选 1M 个数字,而简单的筛选只用了 241 毫秒。
function simpleSieve(n) {
let a = new Array(n)
let answer = []
let p
for (let i = 2; i < n; i ++) {
a[i] = i
}
for (let i = 2; i < n; i++) {
if (a[i]) {
answer.push(a[i])
p = a[i]
for(let j = p; j < n; j += p) {
a[j] = 0
}
}
}
return answer
}
编辑 2
用 cpp 和 prime3 重新测试确实比简单的筛子快 3 倍:
p3:
n = 100000000, t = 866717 microseconds.
n = 200000000, t = 2354425 microseconds.
n = 300000000, t = 3689165 microseconds.
n = 400000000, t = 4950224 microseconds.
n = 500000000, t = 6119779 microseconds.
n = 600000000, t = 7375925 microseconds.
n = 700000000, t = 8647293 microseconds.
n = 800000000, t = 10477116 microseconds.
n = 900000000, t = 11589894 microseconds.
n = 1000000000, t = 12806997 microseconds.
simple:
n = 100000000, t = 2316019 microseconds.
n = 200000000, t = 6063749 microseconds.
n = 300000000, t = 9783295 microseconds.
n = 400000000, t = 13315450 microseconds.
n = 500000000, t = 16640474 microseconds.
n = 600000000, t = 20282461 microseconds.
n = 700000000, t = 24219469 microseconds.
n = 800000000, t = 29203786 microseconds.
n = 900000000, t = 32965856 microseconds.
n = 1000000000, t = 37694084 microseconds.
为了完整性,这里的代码:
void simpleSieve(int n) {
bool *a = (bool *)calloc(n, sizeof(bool));
int p;
memset(a, true, sizeof(bool) * n);
for (int i = 2; i < n; i++) {
if (a[i]) {
p = i;
for (int j = p; j < n; j += p) {
a[j] = 0;
}
}
}
free(a);
}
void prime3(int n) {
bool *sieve = (bool*)calloc(n, sizeof(bool));
sieve[2] = true;
for (int i = 3; i < n; i+=2) {
sieve[i] = true;
}
int step;
for (int i = 2; i * i <= n; i += 1) {
if (sieve[i]) {
step = i*2;
for (int j = i * i; j <= n; j = j + step) {
sieve[j] = false;
}
}
}
free(sieve);
}
推荐阅读
- ios - ToolbarItems 在 iOS 中看起来不正确
- javascript - JavaScript 如何快速声明默认值为 0 的 16 长度数组?
- php - Box Spout 单元格高度宽度增加/减少?
- linux - 在 shell 脚本中将逗号分隔的命令行参数转换为 json
- javascript - 检查时间是否介于 2 次之间
- r - 在任何平台上的 R 中从目录和文件名中(递归地)删除空格
- fortran - 用 fortran 95 编写的程序,它显示警告整数除法被截断为 '0' [-Winteger-division] 并且一些输出数据是 NaN
- python - 如何在 django-import/export 上导入 auth.User
- angularjs - Angular JS - 使用通用模板区分保存和更新
- typescript - Typescript Pick 文字类型