数羊(比阿特丽克斯·特罗特)

Question

我正试图解决CodeWars上的一个问题，这是谷歌2016年CodeJam资格赛的一部分。https://www.codewars.com/kata/bleatrix-trotter-the-counting-sheep/train/javascript

我相信我的代码可以解释所有的测试用例，我唯一的问题是它不能在代码战中提交，因为它的运行时大于12000 ms。

如何使我的代码更有效率？还有一个测试循环是否无限的最佳实践吗？

function trotter(n) {
  var tracker = [];
  var sum = [];
  var snacker = n;
  for(var i = 0; tracker.length < 10; i++){
    sum = snacker.toString().split('');
    sum.forEach(function(num) {
        if (tracker.indexOf(num) == -1) {
             tracker.push(num);
        }
    });
    snacker += n;
  }
  return tracker.length === 10 ? snacker - n : "INSOMNIA";
}

Answer 1

当性能和可读性降低不是一个问题时，您应该：

• 喜欢for和while循环而不是内置的map，forEach.
• 在最近(2016年)版本的JavaScript中，for循环，特别是反向for循环，似乎是最具表现力的选择。 此外，请记住，您不需要使用它的3个表达式。例如，对我来说. 设found = 0；for (；查找< 10;) { 和 设j= chars.length；for (;j;) { 始终返回比初始化槽和while循环中的初始化结果更好的结果，尽管在后一种情况下，差别不是很大。 有关更多信息，请参见Javascript性能: While For Loops
• 当在while或for的表达式(如for (let i = 0; i < array.length; ++i) )中使用for (let i = 0; i < array.length; ++i)时，更倾向于声明上述限制条件，这样就不会每次计算限制条件，因为这涉及到对象查找： const totalElements = array.length；for (设i= 0；i< totalElements；++i) {.}
• 更喜欢前增量而不是后增量。后者将创建一个临时变量，存储预增量值，该值将返回给您，而前者将首先执行增量，然后返回增量值。不需要临时变量。 有关此问题的更多信息，请参见增量后与增量前- Javascript优化 实际上，如果结果是相同的，无论您使用哪一个，那么我建议您尽可能使用预增量。
• 避免具有等效表达式的内置方法。例如，(n + '')比n.toString()具有更高的性能。
• 避免类型转换，更喜欢使用整数而不是浮点数或字符串作为现代JS引擎标记变量类型。这意味着，一方面，更改类型将导致性能损失，另一方面，持续使用它们将允许引擎进行特定类型的优化。 有关此问题的更多信息，请参见https://www.html5rocks.com/en/tutorials/speed/v8/
• 在可能的情况下使用位运算符。例如，整数除法可以用Math.floor(a /b)完成，也可以用a / b | 0进行，速度几乎是a / b | 0的两倍。 有关JavaScript中整数除法的更多信息，请参见以下有趣的线程：如何在JavaScript中执行整数除法并得到余数？
• 更喜欢对象查找(object.prop或object['prop'])，而不是使用Array.prototype.indexOf(...)。 请参阅Javascript:什么查找更快: array.indexOf还是对象哈希？
• 如果有更简单的结构或不可变的数据结构，请避免使用arrays和objects及相关方法。 例如，@RobG的解决方案使用splice。虽然我不知道内部实现，但它可能正在转移删除元素之后的元素，以便再次压缩数组并更新其length。 但是，在我的解决方案中，数组的length总是相同的，您只是将其值从false更改为true，这所涉及的开销要小得多，因为不需要重新分配空间。
• 如果可能的话，可以使用类型化数组，尽管我在这里尝试了Uint8Array，两者都分配给了true和1，但它们都没有改进时间；前者的时间实际上增加了一倍，而第一个则保持了大致相同。也许它有一个BooleanArray，它可以工作。

请记住，这只是一些技术或特性的列表，我认为这可能有助于加快您的示例。我强烈建议您阅读我添加的外部链接，以便更好地理解它们如何和为什么工作，以及它们还可以应用在哪里。

此外，一般来说，您保存代码的级别越低，即使用基本数据类型和操作，它的性能就越好。

为了证明这一点，下面我将向您展示使用整数除法(n / 10) | 0和余数(%)的这段代码的高度优化版本。

​

function trotter(N) {
  if (N === 0) return 'INSOMNIA';
  
  const digits = [false, false, false, false, false, false, false, false, false, false];
    
  let n;
  let last = 0;
  let found = 0;
 
  for (;found < 10;) {
    n = last += N;
    
    for (;n;) {
      const digit = n % 10;
            
      n = (n / 10) | 0;
            
      if (!digits[digit]) {
        digits[digit] = true;
        
        ++found;
      }
    }
  }
  
  return last;
}

const numbers = [0, 2, 7, 125, 1625, 1692];
const outputs = ['INSOMNIA', 90, 70, 9000, 9750, 5076];

// CHECK IT WORKS FIRST:

numbers.map((number, index) => {
  if (trotter(number) !== outputs[index]) {
    console.log('EXPECTED = ' + outputs[index]);
    console.log('     GOT = ' + trotter(number));

    throw new Error('Incorrect value.');
  }
});


// PERF. TEST:

const ITERATIONS = 1000000;

const t0 = performance.now();

for (let i = 0; i < ITERATIONS; ++i) {
  numbers.map((number, index) => trotter(number));
}

const t1 = performance.now();

console.log(`AVG. TIME: ${ (t1 - t0) / ITERATIONS } ms. with ${ ITERATIONS } ITERATIONS`);

​

   AVG. TIME: 0.0033206450000000005 ms. with 1000000 ITERATIONS

     BROWSER: Google Chrome Version 59.0.3071.86 (Official Build) (64-bit)
          OS: macOS Sierra

BRAND, MODEL: MacBook Pro (Retina, 15-inch, Mid 2015)
   PROCESSOR: 2,8 GHz Intel Core i7
      MEMORY: 16 GB 1600 MHz DDR3

下面可以看到我的初始答案，它使用这里列出的一些其他优化，但仍然将number变量n转换为string，并使用String.prototype.split()获取其数字。

它几乎比上面的慢5倍！

​

function trotter(N) {
  if (N === 0) return 'INSOMNIA';
  
  const digits = [false, false, false, false, false, false, false, false, false, false];
  
  let n = N;
  let i = 0;
  let found = 0;
  
  for (;found < 10;) {
    // There's no need for this multiplication:

    n = N * ++i;
    
    // Type conversion + Built-in String.prototype.split(), both can
    // be avoided:

    const chars = (n + '').split('');
    
    let j = chars.length;
    
    for (;j;) {
      const digit = chars[--j];
            
      if (!digits[digit]) {
        digits[digit] = true;
        
        ++found;
      }
    }
  }
  
  return n;
}

const numbers = [0, 2, 7, 125, 1625, 1692];
const outputs = ['INSOMNIA', 90, 70, 9000, 9750, 5076];

// CHECK IT WORKS FIRST:

numbers.map((number, index) => {
  if (trotter(number) !== outputs[index]) {
    console.log('EXPECTED = ' + outputs[index]);
    console.log('     GOT = ' + trotter(number));

    throw new Error('Incorrect value.');
  }
});


// PERF. TEST:

const ITERATIONS = 1000000;

const t0 = performance.now();

for (let i = 0; i < ITERATIONS; ++i) {
  numbers.map((number, index) => trotter(number));
}

const t1 = performance.now();

console.log(`AVG. TIME: ${ (t1 - t0) / ITERATIONS } ms. with ${ ITERATIONS } ITERATIONS`);

​

   AVG. TIME: 0.016428575000000004 ms. with 1000000 ITERATIONS

     BROWSER: Google Chrome Version 59.0.3071.86 (Official Build) (64-bit)
          OS: macOS Sierra

BRAND, MODEL: MacBook Pro (Retina, 15-inch, Mid 2015)
   PROCESSOR: 2,8 GHz Intel Core i7
      MEMORY: 16 GB 1600 MHz DDR3

Answer 2

下面的代码没有特殊的优化，并使用所有ECMA-262 ed 3种方法。它在339毫秒内进行了全套测试。

​

function trotter(n){
  var nums = ['0','1','2','3','4','5','6','7','8','9'];
  var i = 1;

  // Zero creates an infinite loop, so skip it
  if (n !== 0) {

    // While there are numbers to remove, keep going
    // Limit loops to 100 just in case
    while (nums.length && i < 100) {
      // Get test number as an array of digits
      var d = ('' + (n * i)).split('');

      // For each digit, if in nums remove it
      for (var j=0, jLen=d.length; j<jLen; j++) {
        var idx = nums.indexOf(d[j]);

        if (idx > -1) nums.splice(idx, 1);
      }

      i++;
    }
  }
  // If there are numbers left, didn't get to sleep
  // Otherwise, return last number seen (put d back together and make a numer)
  return nums.length? 'INSOMNIA' : Number(d.join(''));
}

console.log('0   : ' + trotter(0));
console.log('125 : ' + trotter(125));
console.log('1625: ' + trotter(1625));

​

大多数情况是在大约10次迭代中解决的，但是125、1250、12500等需要73次迭代，我认为这是任何数字最多的一次。

由于数组方法可能比较慢，下面是一个关于https://jsperf.com/trotter-tests/1的字符串版本

​

function trotter(n){
  var found = '';
  if (n !== 0) {
    var i = 1;
    while (found.length < 10) {
      var d = i * n + '';
      var j = d.length;
      while (j) {
        var c = d[--j];
        var idx = found.indexOf(c);
        if (idx == -1) found += c;
      }
      i++;
    }
  }
  return found.length == 10? +d : 'INSOMNIA';
}

[0,    // Infinte loop case
 125,  // Max loop case
 1625] // just a number
 .forEach(function (n) {
  console.log(n + ' : ' + trotter(n));
});

​

虽然执行while (found.length)并不是最优的，但通常只计算10次，因此在条件之外移动并不是很重要。另一种方法是包括一个计数器，每次向查找中添加一个数字时都会递增，但这并不是要优化性能，而是要找到一些合理的东西，在代码战中通过(未公开的)测试。

Answer 3

另一种方法：

​

    function trotter(n){
      var unseen = '0123456789', last = 0;
      while (unseen != '' && last < 72*n) {
        last += n;
        var reg = new RegExp('[' + last + ']+', 'g');
        unseen = unseen.replace(reg, '');
      }
      return unseen != '' ? 'INSOMNIA' : last;
    };

    console.log('0   : ' + trotter(0));
    console.log('125 : ' + trotter(125));
    console.log('1625: ' + trotter(1625));

​