有什么方法可以提高JS中for循环的性能吗

Is there any way to increase performance for this for loop in JS?

本文关键字：for 循环 性能 JS 方法 什么      更新时间：2023-09-26

我试图解决项目euler 10问题（找到200万以下所有素数的和），但代码需要很长时间才能完成，我如何让它更快？

    console.log("Starting...")
var primes = [1000];
var x = 0;
var n = 0;
var i = 2;
var b = 0;
var sum = 0;
for (i; i < 2000000; i++) {
    x = 0;
    if (i === 2) {
            primes[b] = i
            sum += primes[b];
            console.log(primes[b]);
            b++;
        }
    for (n = i - 1; n > 1; n--) {
        if (i % n === 0) {
            x++;
        }
        if (n === 2 && x === 0) {
            primes[b] = i;
            sum += primes[b];
            console.log(primes[b]);
            b++;
        }
    }
}
console.log(sum)

您可以做的最大的超简单的事情使其更快：

  • 当你找到一个除数时，就跳出内循环！

  • 当你检查素性时，从小除数开始，而不是从大除数开始。你会发现复合材料的速度要快得多。

  • 您只需要检查除数<=数学sqrt（n）

  • 你只需要检查素数。你有他们的名单。

  • 在循环外处理2，然后在循环内只做奇数：for(i=3;i<2000000;i+=2)

这是另一个基于埃拉托斯特尼筛的版本。它需要更多的内存，但如果这与你无关，它也很快。

// just a helper to create integer arrays
function range(from, to) {
    var numbers = [];
    for (var i=from ; i<=to ; i++) {
        numbers.push(i);
    }
    return numbers;
}
function primesUpTo(limit) {
    if (limit < 2) return [];
    var sqrt = Math.floor(Math.sqrt(limit));
    var testPrimes = primesUpTo(sqrt);
    var numbers = range(sqrt+1, limit);
    testPrimes.forEach(function(p) {
        numbers = numbers.filter(function(x) { return x % p > 0 });
    });
    return testPrimes.concat(numbers); 
}
var primes = primesUpTo(2000000);
var sum = primes.reduce(function(acc, e) { return acc + e });

由于您无论如何都保留一个素数数组，因此可以将过程分为两个步骤：

  • 生成上限为200万的素数
  • 以及总结

正如其他人所指出的，你只需要检查一个候选数是否可以被另一个不大于该候选数平方根的素数除。如果你可以把一个数字写成素数的乘积，那么其中一个素数总是小于或等于这个数字的平方根。

这个代码可以进一步优化，但它比你的初始版本快几个数量级：

function primesUpTo(limit) {
    if (limit < 2) return [];
    var sqrt = Math.floor(Math.sqrt(limit));
    var testPrimes = primesUpTo(sqrt);
    var result = [].concat(testPrimes);
    for (var i=sqrt+1 ; i<=limit ; i++) {
        if (testPrimes.every(function(x) { return (i % x) > 0 })) {
            result.push(i);
        }
    }
    return result;
}
var primes = primesUpTo(2000000);
var sum = primes.reduce(function(acc, e) { return acc + e });
相关文章：