
程序功能是将质数依次写入文件, 执行 ts-node main.ts, 代码在下面
常规判断是否是质数, 是逐个判断 [2, Math.sqrt(num)] 是否能整除目标数, 我的思路是维护一个质数数组, 先从该数组中逐个判断是否能整除, 然后再依次加一, 效率还行(?), 每秒能判断十万个左右, 加上写入文件的话每秒能 1.5 万个左右
但是跑到 2.2 千万时, 程序报错了, 重新执行, 从 2.2 千万跑到 3.5 千万时又报错了; 就我的渣渣水平来看, 大概是内存溢出? 但是我从头到尾看了我的程序, 除了那个质数数组一直占用内存, 其他的变量应该都能被回收啊, cpu 占用也一直在 50%左右, 不高啊, 求助为什么崩了呢?
部分报错如下
[4828:000002AA1DB95410] 818854 ms: Mark-sweep 1753.6 (2051.2) -> 1753.6 (2051.2) ms (average mu = 0.191, current mu = 0.000) last resort GC in old space requeste [4828:000002AA1DB95410] 819628 ms: Mark-sweep 1753.6 (2051.2) -> 1753.6 (2052.2) ms (average mu = 0.207, current mu = 0.227) allocation failure GC in old space r ... FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScr memory ------------ 代码 -----------
// main.ts import * as fs from "fs" const primeStr = fs.readFileSync("primes.txt", { encoding: "utf-8", flag: "a+", }) const primes = primeStr.split(",").map((n) => +n).filter((n) => n >= 2) let primeLastIdx = primes.length - 1 function checkIsInt(num: number) { return num === num >> 0 } /** * 返回 a 是否是 b 的因子 * * 返回值 true: 是因子 * 返回值 false: 不是因子, 且大于 a 的数都不是因子 * 返回值 1: 不是因子, 但大于 a 的数可能存在因子 */ function isFactorOf(a: number, b: number) { const devided = b / a if (a > devided) { return false } if (checkIsInt(devided)) { return true } return 1 } function checkIsPrime(num: number) { let prime: number for (let i = 0; i <= primeLastIdx; i += 1) { prime = primes[i] const isFactor = isFactorOf(prime, num) if (isFactor === 1) { continue } return !isFactor } for (let i = prime + 1; true; i += 1) { const isFactor = isFactorOf(i, num) if (isFactor === 1) { continue } return !isFactor } } function main() { for (let i = primes[primeLastIdx] + 1 || 2; i < 101000000; i += 1) { process.stdout.write(`\r${i}`) if (checkIsPrime(i)) { primeLastIdx += 1 primes.push(i) fs.writeFileSync("./primes.txt", `${i},`, { encoding: "utf-8", flag: "a+", }) } } } main() ---------------- 新增 bug report ---------------
bug report, 有兴趣的可以帮忙看看(我是一点看不懂 T_T)
估计是 #8 所说的原因,文件写入改用:
const fd = fs.openSync(fileName, "a+") __for (...) { ____if (isPrime(...)) { ________fs.writeSync(fd, "...") ____} __} 之后速度很快,也不崩溃了,在十几亿的情况下还能保持每秒100万左右。(我还用C++重写了,结果C++的速度还不如js,果然菜鸟写什么语言都慢。。。)
执行情况如下:
>>> 开始执行 加载质数表文件: [质数表.txt]...
<<< 执行完毕 加载质数表文件: [质数表.txt], 耗时 240 ms
>>> 开始执行 解析质数表文件...
<<< 执行完毕 解析质数表文件, 耗时 45.267 秒
>>> 开始执行 检测 [616399999, 2147483643]...
100.0%: 2,147,200,001
<<< 执行完毕 检测 [616399999, 2147483643], 耗时 22 分 42 秒
共计检测 1,531,083,644 个数, 平均每秒检测 1,123,675
1 crella 2020-08-15 19:30:18 +08:00 via Android 我看不出来什么问题,建议用不同进程执行,每个进程读取指定区间的已知质数群的 txt 文件,运算后再写入文件 |
2 crella 2020-08-15 19:42:37 +08:00 via Android 或者试试 redis ?因为不是编译语言的语言的数组相对来说占内存多很多 |
3 roscoecheung1993 2020-08-15 21:24:35 +08:00 快照了一下,疑似写完文件后会往事件循环队列里放一个异步任务的对象,分配了相当多的 Object |
4 noe132 2020-08-15 21:55:41 +08:00 你 stdout 写的太频繁了,影响了执行速度。 建议每 1024 个数输出一下,能快不少。我这目测有 6-8 倍的提升。 if (i % 1024 === 0) { process.stdout.write(`\r${i}`) } 质数判断也有优化空间,随便改一改似乎能有 1 倍的性能提升 node 12.16.1 似乎并没有出现内存泄漏 private bytes 一直稳定在 110MB 左右, |
5 xiaoming1992 OP @crella #1 用多进程, 可能效率还会提升不少, 但由于目前已经存在未知的 bug, 所以不想再做其他优化引入新的变量了。 #2 redis 同理 @noe132 #4 对对对,我忘了 stdout 也会影响性能了。。。还有方便说说质数判断怎么优化吗? @roscoecheung1993 方便说说如何快照任务队列吗?我这边想试试看看。毕竟看我的程序好像没有哪儿用到异步了,怎么会分配异步任务呢。。。 |
6 xiaoming1992 OP @noe132 原来一直是 stdout 影响了速度, 我改成 `if (i % 20000 === 0)` 后, 速度直接飙升到将近 1 千万 每秒。。。是我年轻了, 我直觉以为 stdout 性能没问题呢 |
7 learningman 2020-08-16 00:12:30 +08:00/span> 质数算法那么多。。。线性筛,埃氏筛,一堆 |
8 roscoecheung1993 2020-08-16 00:34:43 +08:00 @xiaoming1992 跑的时候给 node 传参 --inspect,在浏览器里连上 inspector 可以捕获堆快照和调用栈 异步这个可能是 stdout.write 或者 fs.writeFileSync 触发的某些回调,没细看。 感觉也可能是算的比 IO 快太多,导致 IO 堆积了 |