代码之家 › 专栏 › 技术社区 › Robin

JavaScript:Sieve of Atkin实现中的巨大结果数组内存不足

primes benchmarking performance-testing performance javascript

Robin · 技术社区 · 5 年前

为了使上升可以忽略不计,我计算了高达50万的素数。我的问题是,JavaScript实现内存不足,因为结果数组变大了。

这是我目前的做法:

const AMOUNT = 500000000;

function getPrimes() {
  const limit = AMOUNT;
  const width = Math.sqrt(limit);
  let i, j, x, y, z;
  let primes = new Array(limit);

  const begin = performance.now();
  for (x = 1; x <= width; x++) {
    for (y = 1; y <= width; y++) {
      z = 4 * x * x + y * y;
      if (z < limit && (z % 60 == 1 || z % 60 == 13 || z % 60 == 17 || z
          % 60 == 29 || z % 60 == 37 || z % 60 == 41 || z % 60 == 49
          || z % 60 == 53)) {
        primes[z] = !primes[z];
      }

      z = 3 * x * x + y * y;
      if (z < limit && (z % 60 == 7 || z % 60 == 19 || z % 60 == 31 || z
          % 60 == 43)) {
        primes[z] = !primes[z];
      }

      z = 3 * x * x - y * y;
      if (x > y && z < limit && (z % 60 == 11 || z % 60 == 23 || z % 60
          == 47 || z % 60 == 59)) {
        primes[z] = !primes[z];
      }
    }
  }

  const end = performance.now();

  let last_prime = 0;
  for (i = limit; i >= 0; i--) {
    if(primes[i] == 1) {
      last_prime = i;
      break;
    }
  }

  primes = null;
  time_spent = end - begin;
  console.log(time_spent/1000 + ', ' + last_prime);
}

document.addEventListener("DOMContentLoaded", function() {
  let i;
  for (i = 0; i <= 10; i++) {
    getPrimes();
  }
});

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Find Primes</title>
    <script src="./find-primes.js"></script>
  </head>
  <body>
    Check the console.
  </body>
</html>

到目前为止我所做的: -确保 primes 数组在每次运行后通过使其为空来收集。 -分配整个数组一次。

我试图阻止的是,拆分数组或在不同的迭代中计算结果,因为我想基准测试原始计算性能。内存管理对测试不应该有任何影响。

我用的是:

Mozilla Firefox:67.0.2版(64位)

提前谢谢你!

0 回复 | 直到 5 年前

Patrick Roberts Benjamin Gruenbaum 5 年前

而不是 Array ,它天真地将您的每面旗帜存储为 double Uint8Array ,或其他无符号整数格式,这将使内存使用量减少至少64倍。

您需要修改初始化、切换和检查标志的方式。

初始化:

const BitArray = Uint8Array; // or Uint16Array, Uint32Array
const BITS_PER_ELEMENT = BitArray.BYTES_PER_ELEMENT * 8;
const BIT_SHIFT = Math.log2(BITS_PER_ELEMENT);
const BIT_MASK = BITS_PER_ELEMENT - 1;
let primes = new BitArray(Math.ceil(limit / BITS_PER_ELEMENT));

切换:

primes[z >> BIT_SHIFT] ^= 1 << (z & BIT_MASK);

检查:

if (primes[i >> BIT_SHIFT] & (1 << (i & BIT_MASK)))

任何选择 uint8数组 , Uint16Array ,和 Uint32Array