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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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