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

[sci_nov]

Не знаете почему решение на множествах оказалось быстрее? Я предполагаю, что из-за меньшего потребления памяти.

[insecto]

Мне кажется, потому что в них никакой питонячий код не вызывается в цикле, все циклы нативные.

[sci_nov]

По идее, list comprehension для этого и рекомендован. Это надо ещё догадаться использовать множества. Возможно, что от версии python зависит.

[insecto]

list comprehensions всё равно вызывает питонячий код if i%3 == 0 or i%5 == 0 на каждой итерации, а питонячий код это тормоза. А например set(range(3, 1000, 3)) может у себя внутри очень быстро нативно поинкрементить переменную, без выхода в нижний мир.

[sci_nov]

А, да.

[wataru]

А как же самое быстрое решение на основе математики?

print((1000-1000%3)//3*(1000-1000%3+3)//2+(1000-1000%5)//5*(1000-1000%5+5)//2 - (1000-1000%15)//15*(1000-1000%15+15)//2)

На моем компе занимает 0.00827 usec, когда как самое быстрое ваше решение занимет 17.3 usek. Где-то этак в 2000 раз быстрее. Если планируете и дальше решать Project Eurler, то именно такие решения вам и стоит искать.

Берется это решение отсюда: Возьмем сумму всех чисел, делящихся на 3 и сумму всех чисел делящехся на 5. Сложив их мы получим почти то, что надо. Только числа делящееся на 3 и на 5 одновременно (делящееся на 15) будут подсчитаны дважды. Поэтому их сумму надо вычесть.

Далее, сумму чисел до n, делящехся на некое k можно подсчитать как арифметическую прогрессиюю k+2k+....+z, где z — самое большое число, делящееся на k, меньшее n.

[Balling]

Осталось запилить эвристику для всех компиляторов!

[paluke]

А главное, если надо посчитать сумму для чисел скажем до миллиарда, за то же время будет считаться.

[dmitry22275]

Вот только неправильно.

[wataru]

Действительно, я 1000 учитывал в сумме, когда как в задании стоит слово "меньше". Если поменять 1000 на 999 — то работет правильно.

[amakhrov]

Любопытна разница между list comprehension и filter. Похоже на большие накладные расходы на вызов лямбды. Которая по какой-то причине не заинлайнилась.

А reduce, кстати, единственный из функциональных вариантов не создает промежуточных списков в памяти. Реально непонятно, почему он медленнее того же sum+filter. Арифметическое суммирование в питоне медленнее функции sum?

[northzen]

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

[Imposeren]

Можно вместо объединения множеств. Попробовать sum от itertools.chain двух range