Планета гаджетов / технологий
Содержание
Рассказывает Jackson Bates
Несколько недель назад на Free Code Camp’s Forum дали старт неофициальному алгоритмическому соревнованию.
Задача была весьма простой: вернуть сумму всех чисел, делимых без остатка на 3 и 5, входящих в диапазон от 0 до числа N, где N — входной параметр функции.
Но вместо поиска хоть какого-нибудь решения P1xt (организатор соревнования) потребовал сфокусироваться на эффективности. Что в свою очередь подразумевает написание собственных тестов и бенчмарков для оценки производительности найденных решений.
Именно такой подход я использовал для каждой написанной мной функции. В конце я покажу самое быстрое решение, которое буквально взорвало мне мозг и которое меня кое-чему научило.
Для решения задач, подобных этой, мои мозги привыкли делать следующее: создать массив, затем что-то сделать с массивом.
Эта функция создает массив и методом push добавляет в него числа, которые соответствуют условию (делятся на 3 и 5). Затем цикл пробегается по массиву, суммируя все его значения.
function arrayPushAndIncrement(n) { for (var i = 1; i < n; i ++) { if (i % 3 == 0 || i % 5 == 0) { array.push(i); for (var num of array) { module.exports = arrayPushAndIncrement; // this is necessary for testing |
Далее для автоматизированных тестов этой функции я использовал Mocha и Chai, запущенных на NodeJS.
Если хотите получить больше информации по установке Mocha и Chai, то вы можете почитать об этом в соответствующем гайде на форуме Free Code Camp.
Я написал простой тест, используя значения, предоставленные организатором. Заметьте, что в коде ниже функция подключена как модуль.
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, он вернул следующее:
Все последующие функции в этой статье прогонялись через этот же тест.
function arrayPushAndReduce(n) { 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.
Теперь, когда у нас есть две функции, мы можем сравнить их эффективность. Опять же, спасибо организатору, который предоставил соответствующий скрипт на форуме.
var Benchmark = require( ‘benchmark’ ); var suite = new Benchmark.Suite; var arrayPushAndIncrement = require( ‘./arrayPushAndIncrement’ ); var arrayPushAndReduce = require( ‘./arrayPushAndReduce’ ); suite.add( ‘arrayPushAndIncrement’, function() { arrayPushAndIncrement(45678) .add( ‘arrayPushAndReduce’, function() { arrayPushAndReduce(45678) .on( ‘cycle’, function( event ) { console.log( String( event.target )); .on( ‘complete’, function() { console.log( ‘Fastest is ‘ + this.filter( ‘fastest’ ).map( ‘name’ )); |
Если запустить скрипт строчкой 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-кратный прирост в скорости!
Если это не вдохновляет на поиск новых решений, то я уже не знаю, что может вдохновить!
Поскольку я всегда полагался на цикл for, мне следовало протестировать альтернативный while цикл:
function whileLoopArrayReduce(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) |
Итак, обнаружив, что тип цикла не дает большой выгоды, я задумался: а что, если я буду использовать метод, который вообще избегает каких-либо массивов?
if (n%3==0||n%5==0) { module.exports = whileSum; |
Увидев результаты, я сразу понял, насколько же я был неправ, используя только массивы…
whileSum x 7,311 ops/sec ±1.26% (91 runs sampled) |
Еще одно массивное улучшение: почти в 5 раз быстрее и в 27 раз быстрее, чем мое первое решение!
Конечно же мы уже знаем, что цикл for работает чуточку быстрее:
for (n; n >= 1 ;n—) { (n%3==0||n%5==0) ? sum += n : null; |
В данном примере используется тернарный оператор для проверки соответствия условию, но мои тесты показывают, что не-тернарный вариант — такой же по производительности.
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) |
Победившая функция оказалась примерно в 9 690 раз быстрее, чем мое лучшее решение и в 275 858 раз быстрее, чем моя первая имплементация.
Если я вам понадоблюсь, то можете искать меня в Khan Academy, изучающим математику.
Спасибо всем, кто принял участие в соревновании и поделился своими решениями. Дух взаимопомощи помогает всем участникам осваивать новые методы.
Если вам интересно, то тут P1xt описал все правила соревнования и прочие вещи.
За перевод благодарим нашего подписчика, Даниила Высоцкого
Перевод статьи «What I learned from writing six functions that all did the same thing»