javascript - collat​​z 序列的最大长度 - 优化

Question

我正在尝试解决 this MaxCollatzLength kata但我正在努力优化它以使其运行得足够快以应对非常大的数字。

In this kata we will take a look at the length of collatz sequences. And how they evolve. Write a function that take a positive integer n and return the number between 1 and n that has the maximum Collatz sequence length and the maximum length. The output has to take the form of an array [number, maxLength] For exemple the Collatz sequence of 4 is [4,2,1], 3 is [3,10,5,16,8,4,2,1], 2 is [2,1], 1 is [ 1 ], so MaxCollatzLength(4) should return [3,8]. If n is not a positive integer, the function have to return [].

As you can see, numbers in Collatz sequences may exceed n. The last tests use random big numbers so you may consider some optimisation in your code:

You may get very unlucky and get only hard numbers: try submitting 2-3 times if it times out; if it still does, probably you need to optimize your code more;

Optimisation 1: when calculating the length of a sequence, if n is odd, what 3n+1 will be ?

Optimisation 2: when looping through 1 to n, take i such that i < n/2, what will be the length of the sequence for 2i ?

递归解决方案很快就会破坏堆栈，所以我使用了 while 循环。我想我已经理解并应用了第一次优化。我还发现对于 n 的 2 次幂，最大长度将是 (log2 of n) + 1(对于任意大的数字，这只会减少非常少量的时间)。最后，我记住了到目前为止计算的 collat​​z 长度以避免重新计算。

不过，我不明白第二个优化是什么意思。我试图注意到一个带有一些随机样本和循环的模式，并且我已经绘制了 n < 50000 的最大 collat​​z 长度。我注意到它似乎大致遵循一条曲线，但我不知道如何继续 - 这是一条红鲱鱼？

理想情况下，我正在寻找正确方向的提示，以便我可以自己努力解决问题。

function collatz(n) {
  let result = [];

  while (n !== 1) {
    result.push(n);
    if (n % 2 === 0) n /= 2;
    else {
      n = n * 3 + 1;
      result.push(n);
      n = n / 2;
    }
  }

  result.push(1);
  return result;
}

function collatzLength(n) {
  if (n <= 1) return 1;
  if (!collatzLength.precomputed.hasOwnProperty(n)) {
    // powers of 2 are logarithm2 + 1 long
    if ((n & (n - 1)) === 0) { 
      collatzLength.precomputed[n] = Math.log2(n) + 1; 
    } else {
      collatzLength.precomputed[n] = collatz(n).length;
    }
  }
  return collatzLength.precomputed[n];
}

collatzLength.precomputed = {};

function MaxCollatzLength(n) {
  if (typeof n !== 'number' || n === 0) return [];
  let maxLen = 0;
  let numeralWithMaxLen = Infinity;

  while (n !== 0) {
    let lengthOfN = collatzLength(n);

    if (lengthOfN > maxLen) {
      maxLen = lengthOfN;
      numeralWithMaxLen = n;
    }
    n--;
  }

  return [numeralWithMaxLen, maxLen];
}

Answer 1

内存是这里取得良好性能的关键。您记住计算 Collat​​z 序列的函数的最终结果。这将帮助您重复调用 maxCollatzLength ，但不是在您第一次确定序列长度时。

此外，正如@j_random_hacker 提到的，没有必要实际创建序列作为列表；它足以存储它的长度。整数结果足够轻，可以轻松内存。

在确定 Collat​​z 序列的长度时，您已经可以使用预先计算的结果。不要一直按照序列向下，而是按照它直到找到一个已知长度的数字。

您进行的其他优化是微优化。我不确定计算 2 的幂的对数真的能给你带来任何好处。它反而会给您增加额外的测试负担。

下面的记忆化实现甚至放弃了对 1 的检查，方法是最初将 1 放入预先计算值的字典中。

var precomp = {1: 1};

function collatz(n) {
    var orig = n;
    var len = 0;

    while (!(n in precomp)) {
        n = (n % 2) ? 3*n + 1 : n / 2;
        len++;
    }

    return (precomp[orig] = len + precomp[n]);
}

function maxCollatz(n) {
    var res = [1, 1];

    for (var k = 2; k <= n; k++) {
        var c = collatz(k);

        if (c > res[1]) {
            res[0] = k;
            res[1] = c;
        }
    }

    return res;
}

我没有使用过 node.js，但是我的 Firefox 中使用了 JavaScript。它提供了合理的性能。我第一次有 collatz作为一个递归函数，这使得实现只比你的快一点点。

题中提到的第二个优化意思是如果你知道C(n) ，你也知道 C(2*n) == C(n) + 1 .您可以使用该知识预先计算所有 even n 的值。采用自下而上的方法。

如果 Collat​​z 序列的长度可以自下而上计算就好了，有点像 Erathostenes 的筛法。你必须知道你从哪里来而不是你要去哪里，但是很难知道停下来，因为要找到 n < N 的最长序列。 ，你将不得不计算许多超出n > N范围的序列.照原样，内存是一种避免重复的好方法，否则会很直接。