Чему я научился, написав шесть функций, которые делали одно и то же
cherezzabo
Несколько недель назад на Free Code Camp’s Forum дали старт неофициальному алгоритмическому соревнованию.
Задача была весьма простой: вернуть сумму всех чисел, делимых без остатка на 3 и 5, входящих в диапазон числа N, где N - входной параметр функции.
Но вместо поиска хоть какого-нибудь решения, P1xt (организатор соревнования - прим. переводчика) потребовал сфокусироваться на эффективности. Что в свою очередь подразумевает написание собственных тестов и бенчмарков для оценки производительности найденных решений.
Именно такой подход я использовал для каждой написанной мной функции. В конце я покажу самое быстрое решение, которое буквально взорвало мне мозг и которое меня кое-чему научило.
Функция №1: массив, push, прибавка
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
Для проблем подобных этой, мои мозги привыкли к следующему: создать массив, затем что-то сделать с массивом.
Эта функция создает массив и методом push добавляет в него числа, которые соответствуют условию (делятся на 3 и 5). Затем цикл пробегается по массиву, суммируя все его значения.
Настройка тестов
Далее для автоматизированных тестов этой функции я использовал 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 он вернул следующее:
Все последующие функции в этой статье прогонялись через этот же тест.
Функция №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 описал все правила соревнования и прочие вещи.