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

Обложка поста

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

Рассказывает 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 описал все правила соревнования и прочие вещи.


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