5++ способов в одну строку на Python решить первую задачу Проекта Эйлера

в 12:04, , рубрики: filter, generator expressions, List Comprehension, map, project euler, python, reduce, Занимательные задачки, пайтон, Питон, Программирование, проект Эйлера
5++ способов в одну строку на Python решить первую задачу Проекта Эйлера - 1

Однажды меня посетила мысль, а что если попробовать решить первую задачу Проекта Эйлера всевозможными способами, но с условием, что решение должно быть в одну строку. В итоге получилось более пяти однострочных решений с применением Filter, Map, Reduce, Generator Expression и т.д. В этой статье я покажу то, к чему я пришёл.


Это моя первая статья. Стоит отнестись к ней настороженно. Уникальные решения будут оформлены в отдельные пункты. Менее уникальные - в подпункты.

Условие задачи

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.

Найдите сумму всех чисел меньше 1000, кратных 3 или 5.  

Источники: Оригинал или Русскоязычное зеркало

00 - Базовое решение

Прежде чем перейти непосредственно к однострочным решениям, разумно было бы упомянуть сначала стандартное, классическое решение:

result = 0

for i in range(1, 1000):
    if i%3 == 0 or i%5 == 0:
        result += i

print(result) # => 233168

Перебираем последовательность чисел от 1 до 999. Если перебираемое число делится на 3 или на 5 без остатка от деления, то прибавляем каждое такое число в заранее объявленную переменную result

01 - Generator Expression. Выражение-генератор

print(sum(i for i in range(1, 1000) if i%3 == 0 or i%5 == 0)) # => 233168

Числа из последовательности от 1 до 999, делящиеся на 3 или на 5 без остатка от деления, собираются в генератор. Затем функция sum() складывает содержимое генератора. 

01.a - List Comprehension. Выражение на основе списка

print(sum([i for i in range(1, 1000) if i%3 == 0 or i%5 == 0])) # => 233168

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

01.b - Set Comprehension. Выражение на основе множества

print(sum({i for i in range(1, 1000) if i%3 == 0 or i%5 == 0})) # => 233168

Тоже, что и в предыдущем, но вместо списка здесь множество.

02 - Filter

print(sum(filter(lambda i: i%3 == 0 or i%5 == 0, range(1, 1000)))) # => 233168

Функция filter схожа по принципу работы с выражением-генератором. Функция лямбда применяется к каждому элементу последовательности чисел от 1 до 999. Все числа последовательности, делящиеся на 3 или на 5 без остатка от деления, возвращаются, затем суммируются функцией sum().

03 - Map

print(sum(map(lambda i: i if i%3 == 0 or i%5 == 0 else 0, range(1, 1000)))) # => 233168

Перебираемые числа последовательности от 1 до 999, делящиеся на 3 или 5 без остатка от деления, остаются без изменений, все остальные числа заменяются на ноль. Полученная последовательность суммируется функцией sum().

04 - Reduce

from functools import reduce
print(reduce(lambda x, y: x+y if y%3 == 0 or y%5 == 0 else x, range(1, 1000), 0)) # => 233168

Из всей подборки, этот вариант "очень не очень". Как по степени реализации, так и по времени выполнения(но об этом попозже).  
Если в reduce указан инициализатор(в нашем случае ноль), то он становится накопителем. К нему по очереди прибавляются только те  числа из последовательности от 1 до 999, которые делятся на 3 или на 5 без остатка от деления. Если из функции reduce убрать инициализатор ноль, то инициализатором станет крайний левый элемент последовательности.

05 - Однострочное решение на основе множества

print(sum(set(range(3, 1000, 3)) | set(range(5, 1000, 5)))) # => 233168

Самое элегантное решение, как по красоте написания, так и по времени выполнения.  
Последовательность чисел от 1 до 999, кратную трём, помещаем во множество и объединяем со множеством, содержащим в себе последовательность чисел от 1 до 999, кратную пяти. Содержимое, полученного множества суммируем функцией sum().

05.a - Ещё одно однострочное решение на основе множества

print(sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)})) # => 233168

Похожий вариант на предыдущий, но, если использовать фигурные скобки, то последовательность чисел от 1 до 999, кратную трём и последовательность чисел от 1 до 999, кратную пяти, нужно распаковывать.

05.b - И ещё одно однострочное решение на основе множества

print(sum(set(range(3, 1000, 3)).union(range(5, 1000, 5)))) # => 233168

Создаём множество, с последовательностью чисел от 1 до 999, кратную трём и присоединяем к нему последовательность чисел от 1 до 999, кратную пяти. Затем функцией sum() суммируем.

05.c И последнее однострочное решение на основе множества

print(sum(set([*range(3, 1000, 3)] + [*range(5, 1000, 5)]))) # => 233168

По аналогии с предыдущими. Распаковываем последовательности чисел в списки. Складываем списки. Оборачиваем во множество. Затем суммируем функцией sum().

Смотрим на скорость выполнения каждого однострочного решения

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

sum(i for i in range(1, 1000) if i%3 == 0 or i%5 == 0) # 203 usec
sum([i for i in range(1, 1000) if i%3 == 0 or i%5 == 0]) # 181 usec
sum({i for i in range(1, 1000) if i%3 == 0 or i%5 == 0}) # 189 usec
sum(filter(lambda i: i%3 == 0 or i%5 == 0, range(1, 1000))) # 306 usec
sum(map(lambda i: i if i%3 == 0 or i%5 == 0 else 0, range(1, 1000))) # 313 usec
reduce(lambda x, y: x+y if y%3 == 0 or y%5 == 0 else x, range(1, 1000), 0)# 324 usec
sum(set(range(3, 1000, 3)) | set(range(5, 1000, 5))) # 47 usec
sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)}) # 47 usec
sum(set(range(3, 1000, 3)).union(range(5, 1000, 5))) # 41 usec
sum(set([*range(3, 1000, 3)] + [*range(5, 1000, 5)])) # 43 usec

Методика расчёта: python -m timeit "выражение"

Быстрее всего справились с задачей последние четыре варианта.


Заключение

Всего получилось 5 уникальных + 5 не уникальных решений. Благодаря этой задаче у меня появилось более устойчивое понимание работы функций Filter, Map, Reduce. И если раньше я недоумевал, почему функцию Reduce убрали из основного модуля, то теперь я не сомневаюсь в правильности этого решения.

В статье я старался отойти от популярного шаблона повествования "точность на грани бесполезности". Где предложения набиты под завязку "тяжёлыми" терминами, а из знакомого там только союзы и предлоги. Не уверен, что у меня получилось.

Всем спасибо.

Автор:
axelthepop

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js