• 译 文 address: What I learned from writing six functions that all did the same thing
  • This article is authorized by the original author, Jackson Bates
  • The Nuggets translation Project
  • Translator: Wang Zijian
  • Proofreader: Danny Lau, luoyaqifei

A few weeks ago, a community launched an unofficial algorithm contest at Free Code Camp’s Forum.

This seems simple enough: return the sum of all multiples of 3 or 5 less than the number N, which is the argument to the function.

But rather than simply finding a solution, the P1xt competition requires participants to focus on efficiency, and it encourages you to write your own test cases and use them to evaluate the performance of your solution.

Below is an evaluation of each function I wrote and tested, including my test cases and evaluation scripts. Finally, I’ll show you the winner, the one that killed all of my work and taught me a lesson.

Testing your own code is incredibly painful… From: The Simpsons, here Giphy

Function 1: array, Push method, summation

function arrayPushAndIncrement(n) {
  var array = [];
  var result = 0;
  for (var i = 1; i < n; i ++) {
    if (i % 3 == 0 || i % 5 == 0) {
      array.push(i);
    }
  }
  for (var num of array) {
    result += num;
  }
  return result;
}

module.exports = arrayPushAndIncrement; // this is necessary for testing
Copy the code

For this kind of problem, my mind goes straight to: Create an array and then operate on that array.

This function creates an array, presses the numbers that meet the criteria (divisible by 3 or 5) into the array, and iterates to get the sum of all the cells.

To begin testing

This is an automatic test of the function, running in a NodeJS environment using Mocha and Chai testing tools.

If you want to learn more about Mocha and Chai installation and more, check out a primer of Mocha and Chai tests I wrote at Free Code Camp’s Forum

I have written a simple test script that follows the standard provided by P1xt. Note that in this script, the function is wrapped in a module.

// testMult.js var should = require( 'chai' ).should(); var arrayPushAndIncrement = require( './arrayPushAndIncrement' ); describe('arrayPushAndIncrement', function() { it('should return 23 when passed 10', function() { arrayPushAndIncrement(10).should.equal(23); }) it('should return 78 when passed 20', function() { arrayPushAndIncrement(20).should.equal(78); }) it('should return 2318 when passed 100', function() { arrayPushAndIncrement(100).should.equal(2318); }) it('should return 23331668 when passed 10000', function() { arrayPushAndIncrement(10000).should.equal(23331668); }) it('should return 486804150 when passed 45678', function() { arrayPushAndIncrement(45678).should.equal(486804150); })})Copy the code

When I tested it with mocha testmult.js, I returned the following result:

We consider all the functions in this article to have passed the tests. Add test cases to your code for the functions you want to experiment with.

Function 2: array, Push method, Reduce method

function arrayPushAndReduce(n) {
  var array = [];
  for (var i = 1; i < n; i ++) {
    if (i % 3 == 0 || i % 5 == 0) {
      array.push(i);
    }
  }
  return array.reduce(function(prev, current) {
    return prev + current;
  });
}

module.exports = arrayPushAndReduce;
Copy the code

This function uses a similar approach, but instead of using the for loop, it uses the more subtle reduce method to get the result.

Start performing efficiency assessment tests

Now let’s compare the efficiency of these two functions. Thanks again to P1xt for providing this script in previous topics.

// performance.js

var Benchmark = require( 'benchmark' );
var suite = new Benchmark.Suite;

var arrayPushAndIncrement = require( './arrayPushAndIncrement' );
var arrayPushAndReduce = require( './arrayPushAndReduce' );

// add tests
suite.add( 'arrayPushAndIncrement', function() {
  arrayPushAndIncrement(45678)
})
.add( 'arrayPushAndReduce', function() {
  arrayPushAndReduce(45678)
})
// add listeners
.on( 'cycle', function( event ) {
    console.log( String( event.target ));
})
.on( 'complete', function() {
    console.log( 'Fastest is ' + this.filter( 'fastest' ).map( 'name' ));
})
// run async
.run({ 'async': true });
Copy the code

If you run the test in Node performance.js mode, you get the following output:

ArrayPushAndReduce X 100 ops/ SEC ± 100 ops/ SEC  Fastest is arrayPushAndReduceCopy the code

Turns out, the latter is faster! From Giphy

So we can get a function five times faster using the reduce method!

And if that’s not exciting enough, if that’s not enough to keep us going, then I really don’t have anyone!

Function 3: While loop, array, Reduce method

Since I’ve always been a fan of the for loop, I thought I’d try the while loop:

function whileLoopArrayReduce(n) {
  var array = [];
  while (n >= 1) {
    n--;
    if (n%3==0||n%5==0) {
      array.push(n);
    }
  }
  return array.reduce(function(prev, current) {
    return prev + current;
  });
}

module.exports = whileLoopArrayReduce;
Copy the code

So what’s the result? A little slow:

WhileLoopArrayReduce X 1,504 OPS/SEC ±0.65% (88 runs time)Copy the code

Function 4: While loop, sum, no array

I found that there wasn’t much difference between different loops, so I took a different approach, what if I had a method that didn’t have an array?

function whileSum(n) {
  var sum = 0;
  while (n >= 1) {
    n--;
    if (n%3==0||n%5==0) {
      sum += n;
    }
  }
  return sum;
}

module.exports = whileSum;
Copy the code

As I went along this path, I realized how wrong it was to use arrays first all along…

WhileSum X 751 ops/ SEC ±1.26% (91 runs time)Copy the code

Another magnificent improvement: nearly 5 times faster than the previous one, and 27 times faster than the first one!

Function 5: For loop, sum

Of course, we already know that the for loop is faster:

function forSum(n) { n = n-1; var sum = 0; for (n; n >= 1 ; n--) { (n%3==0||n%5==0) ? sum += n : null; } return sum; }Copy the code

This time I used the ternary operator to make the conditional judgment, but the test results showed that the other versions performed equally well.

ForSum x 1,256 OPS/SEC ±0.24% (91 runs time)Copy the code

The speed has been increased again.

My last function blew up the first function 28 times faster.

I feel like I’m going to win.

I’m going to heaven.

I’ll take the crown and rest easy.

Enter the world of mathematics

Learn to Love Math: From Giphy (Originally, This Music Video)

A week passed quickly, and everyone’s final answers were posted, tested, and verified. The fastest function doesn’t use loops, but instead uses an algebraic formula to manipulate numbers:

function multSilgarth(N) {
  var threes = Math.floor(--N / 3);
  var fives = Math.floor(N / 5);
  var fifteen = Math.floor(N / 15);

  return (3 * threes * (threes + 1) + 5 * fives * (fives + 1) - 15 * fifteen * (fifteen + 1)) / 2;
}

module.exports = multSilgarth;
Copy the code

The test results will be back soon…

ArrayPushAndIncrement x 279 ops/ SEC ±0.80% (83 runs bytes) forSum x 8,256 ops/ SEC ±0.24% (91 runs bytes) maths x 79,998,859 OPS/SEC ±0.81% (88 runs sampled) Fastest is mathsCopy the code

Mathematics is the fastest

The winning function was approximately 9,690 times faster than my best work and 275,858 times faster than my original work.

If you’re looking for me, I’m probably going to khan Academy to study math.