Чему я научился, написав шесть функций, которые делали одно и то же

Рассказывает Jackson Bates 


Несколько недель назад на  Free Code Camp’s Forum дали старт неофициальному алгоритмическому соревнованию.

Задача была весьма простой: вернуть сумму всех чисел, делимых без остатка на 3 и 5, входящих в диапазон от 0 до числа N, где N — входной параметр функции.

Но вместо поиска хоть какого-нибудь решения P1xt (организатор соревнования) потребовал сфокусироваться на эффективности. Что в свою очередь подразумевает написание собственных тестов и бенчмарков для оценки производительности найденных решений.

Именно такой подход я использовал для каждой написанной мной функции. В конце я покажу самое быстрое решение, которое буквально взорвало мне мозг и которое меня кое-чему научило.

Функция №1: массив, push, прибавка

Для решения задач, подобных этой, мои мозги привыкли делать следующее: создать массив, затем что-то сделать с массивом.

Эта функция создает массив и методом push добавляет в него числа, которые соответствуют условию (делятся на 3 и 5). Затем цикл пробегается по массиву, суммируя все его значения.

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

Настройка тестов

Далее для автоматизированных тестов этой функции я использовал Mocha и Chai, запущенных на NodeJS.

Если хотите получить больше информации по установке Mocha и Chai, то вы можете почитать об этом в соответствующем гайде на форуме Free Code Camp.

Я написал простой тест, используя значения, предоставленные организатором. Заметьте, что в коде ниже функция подключена как модуль.

// 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);
  })
})

Когда я запустил тест строчкой mocha testMult.js, он вернул следующее:

1-tmjwwmfxpqevv_kekowprw

Все последующие функции в этой статье прогонялись через этот же тест.

Функция №2: массив, push, reduce

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;

Эта функция использует подход, похожий на предыдущий, но вместо использования цикла for для подсчета конечной суммы в ней используется более изящный метод reduce.

Настройка бенчмарка

Теперь, когда у нас есть две функции, мы можем сравнить их эффективность. Опять же, спасибо организатору, который предоставил соответствующий скрипт на форуме.

// 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 });

Если запустить скрипт строчкой node performance.js, то вы получите следующий ответ в терминале:

arrayPushAndIncrement x 270 ops/sec ±1.18% (81 runs sampled)
arrayPushAndReduce x 1,524 ops/sec ±0.79% (89 runs sampled)
Fastest is arrayPushAndReduce

Итак, использование метода reduce дает нам 5-кратный прирост в скорости!

Если это не вдохновляет на поиск новых решений, то я уже не знаю, что может вдохновить!

Функция №3: while, массив, reduce

Поскольку я всегда полагался на цикл for, мне следовало протестировать альтернативный while цикл:

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;

И каков результат? Чуть-чуть медленнее:

whileLoopArrayReduce x 1,504 ops/sec ±0.65% (88 runs sampled)

Функция №4: while, sum, без массивов

Итак, обнаружив, что тип цикла не дает большой выгоды, я задумался: а что, если я буду использовать метод, который вообще избегает каких-либо массивов?

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

Увидев результаты, я сразу понял, насколько же я был неправ, используя только массивы...

whileSum x 7,311 ops/sec ±1.26% (91 runs sampled)

Еще одно массивное улучшение: почти в 5 раз быстрее и в 27 раз быстрее, чем мое первое решение!

Функция №5: for, sum

Конечно же мы уже знаем, что цикл for работает чуточку быстрее:

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;
}

В данном примере используется тернарный оператор для проверки соответствия условию, но мои тесты показывают, что не-тернарный вариант — такой же по производительности.

forSum x 8,256 ops/sec ±0.24% (91 runs sampled)

И опять чуть-чуть быстрее.

Мое финальное решение оказалось в 28 раз быстрее, чем самое первое.

Я чувствую себя чемпионом.

Я был на седьмом небе.

Я почивал на лаврах.

Погружаемся в математику


Неделя прошла, и на форуме появились финальные решения других участников. Функция, которая оказалась быстрее всех, не использует циклы, но использует алгебраическую формулу для подсчета чисел:

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;

Готовы узнать результат?..

arrayPushAndIncrement x 279 ops/sec ±0.80% (83 runs sampled)
forSum x 8,256 ops/sec ±0.24% (91 runs sampled)
maths x 79,998,859 ops/sec ±0.81% (88 runs sampled)
Fastest is maths

Математика быстрее всех

Победившая функция оказалась примерно в 9 690 раз быстрее, чем мое лучшее решение и в 275 858 раз быстрее, чем моя первая имплементация.

Если я вам понадоблюсь, то можете искать меня в Khan Academy, изучающим математику.

Спасибо всем, кто принял участие в соревновании и поделился своими решениями. Дух взаимопомощи помогает всем участникам осваивать новые методы.

Если вам интересно, то тут P1xt описал все правила соревнования и прочие вещи.


За перевод благодарим нашего подписчика, Даниила Высоцкого

Перевод статьи «What I learned from writing six functions that all did the same thing»