Задача Эйлера проекта 1 в Python - Умножения 3 и 5

Я хотел бы предложить предложения по оптимизации этого решения грубой силы для проблемы 1 . В настоящее время алгоритм проверяет каждое целое число от 3 до 1000. Я хотел бы как можно больше сократить количество ненужных вызовов isMultiple:

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

Найдите сумму всех кратных 3 или 5 ниже 1000.
«»»

end = 1000

def Solution01 ():
    «»»
        Разрешено грубой силой
        #OPTIMIZE
    «»»
    sum = 0
    для i в диапазоне (3, конец):
        если isMultiple (i):
            sum + = i
    печать (сумма)

def isMultiple (i):
    return (i% 3 == 0) или (i% 5 == 0)
50 голосов | спросил Robert S Ciaccio 20 Jam1000000amThu, 20 Jan 2011 00:04:27 +030011 2011, 00:04:27

9 ответов


40

Сумма 3 + 6 + 9 + 12 + ... + 999 = 3 (1 + 2 + 3 + ... + 333) = 3 (n (n + 1)) /2 для n = 333. И 333 = 1000/3, где «/» является интегральной арифметикой.

Также обратите внимание, что кратные 15 отсчитываются дважды.

Итак,

def sum_factors_of_n_below_k (k, n):
    m = (k-1) //n
    return n * m * (m + 1) //2

def solution_01 ():
    return (sum_factors_of_n_below_k (1000, 3) +
            sum_factors_of_n_below_k (1000, 5) -
            sum_factors_of_n_below_k (1000, 15))
ответил 27 Jpm1000000pmThu, 27 Jan 2011 18:27:51 +030011 2011, 18:27:51
26

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

valid = set ([])

для i в диапазоне (3, конец, 3):
  valid.add (я)

для i в диапазоне (5, конец, 5):
  valid.add (я)

total = sum (действительный)

Есть еще немного избыточности (числа, кратные как 3, так и 5, дважды проверяются), но это минимально.

ответил g.d.d.c 20 Jam1000000amThu, 20 Jan 2011 00:23:04 +030011 2011, 00:23:04
16

Я бы избавился от циклов для и использовал sum для выражений генератора.

def solution_01 (n):
    partialsum = sum (xrange (3, n, 3))
    return partialsum + sum (x для x в xrange (5, n, 5), если x% 3)

Обратите внимание, что мы используем xrange вместо range для python 2. Я никогда не видел случая, когда это не ускоряется для for цикл или генератор. Кроме того, использование выражения генератора с sum должно быть быстрее, чем добавлять их вручную в цикле для.

Если вы хотите сделать это с помощью наборов, то по-прежнему нет необходимости в для loops

def solution_01 (n):
    values ​​= set (range (3, n, 3)) | set (диапазон (5, n, 5))
    возвращаемая сумма (значения)

Здесь мы просто передаем кратность в конструктор set, беря объединение двух множеств и возвращаем их сумму. Здесь я использую range вместо xrange. По какой-то причине я видел, что это быстрее при переходе в list. Я думаю, это было бы быстрее для set. Вы, вероятно, захотите провести сравнительный анализ.

ответил aaronasterling 20 Jam1000000amThu, 20 Jan 2011 09:23:09 +030011 2011, 09:23:09
14

Ну, этот является ответом на вопрос Project Euler, поэтому, возможно, лучшим решением является в основном карандаш-бумага.

sum (i для i в диапазоне (n + 1)) # суммирует все числа от нуля до n

- треугольное число, то же самое, что и

n * (n + 1) /2

Это треугольная функция, которую все мы знаем и любим. Скорее, более формально,

треугольник (n) = n * (n + 1) /2

Имея это в виду, отметим далее, что сумма ряда

3, 6, 9, 12, 15, 18, 21, 24, ...

есть 3 * указанная выше треугольная функция. И суммы

5, 10, 15, 20, 25, 30, 35, ...

5 * - функция треугольника. Однако у нас есть одна проблема с этими текущими суммами, так как число, равное 15 или 30, будет подсчитываться в каждом числе треугольников. Чтобы не волноваться, принцип включения-исключения приходит на помощь! Сумма

15, 30, 45, 60, 75, 90, 105, ...

- 15 * функция треугольника. Ну, если это пока мало смысла, не беспокойтесь. Найти сумму ряда от 1 до n, увеличивая на k, составляет только

triangle_with_increments (n, k = 1) = k * (n /k) * (n /k + 1) /2

с этим и принцип исключения включения, окончательный ответ - это

triangle_with_increments (100, 5) + triangle_with_increments (100, 3) - triangle_with_increments (100, 15)

Ого. Кто? проблема сложности n вдруг стала постоянной. Это то, что я называю оптимизацией ИМХО: P. Но, со всей серьезностью, Project Euler просит вас ответить на проблемы с минимальной вычислительной сложностью.

ответил Filipq 12 62011vEurope/Moscow11bEurope/MoscowSat, 12 Nov 2011 05:39:34 +0400 2011, 05:39:34
11

Я бы сделал это следующим образом:

total = 0

для i в диапазоне (3, конец, 3):
  total + = i

для i в диапазоне (5, конец, 5):
  если i% 3! = 0: # Добавить только число, если оно еще не было
    total + = i # было добавлено как кратное 3

Основной подход такой же, как и gddc: итерация всех кратных 3, затем 5. Однако вместо использования набора для удаления дубликатов мы просто проверяем, что кратные 5 не также кратные 3. Это имеет следующие преимущества:

  1. Проверка делимости дешевле, чем добавление в набор.
  2. Мы строим общую сумму пошагово, поэтому нам не нужен отдельный вызов для суммирования в конце.
  3. Мы избавились от множества, поэтому нам нужно только постоянное пространство.
ответил sepp2k 20 Jam1000000amThu, 20 Jan 2011 07:38:14 +030011 2011, 07:38:14
7
Решение

g.d.d.c немного избыточно в том, что он дважды проверяет числа, кратные 3 и 5. Мне было интересно об оптимизации для этого, так что это немного длиннее комментария, но на самом деле не является ответом само по себе, поскольку он полностью полагается на потрясающий ответ g.d.d.c в качестве вдохновения.

Если вы добавляете кратные к допустимому списку для нескольких «3», а затем выполняете другой проход по всему списку (1-1000) для нескольких «5», тогда вы испытываете некоторую избыточность.

Порядок их добавления:

добавить сначала 3-кратные
 добавить 5 кратных секунд

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

То есть, если ваш алгоритм похож на

добавить 3-кратные к списку

добавьте 5-кратные к списку, если они не столкнутся

он будет немного хуже, чем

добавить 5-кратный список

добавьте 3-кратные к списку, если они не сталкиваются

а именно, потому что существует больше 3-кратных, чем 5-кратных, и поэтому вы делаете больше «если они не сталкиваются» с проверками.

Итак, вот некоторые мысли, которые следует иметь в виду, с точки зрения оптимизации:

  • Было бы лучше, если бы мы могли перебирать список через
  • Было бы лучше, если бы мы не проверяли числа, которые не были кратными 3 и 5.

Один из возможных способов - заметить частоту кратных. То есть, обратите внимание, что LCM (наименьшее общее число) 3 и 5 составляет 15:

3 6 9 12 15 18 21 24 27 30
               || ||
  5 10 15 20 25 30

Таким образом, вы должны хотеть в оптимальном случае использовать частотное представление кратных 3 и 5 в диапазоне (1,15) снова и снова до тех пор, пока вы не достигнете 1000. (действительно 1005, которое делится на 15 равномерно 67 раз).

Итак, вы хотите, для каждой итерации этого частотного представления:

числа в: 3 5 6 9 10 12 15

Ваши частоты возникают (я использую вокабу для этого, поэтому, пожалуйста, исправьте меня, если есть лучшие математические слова) при начальных индексах от 0k + 1 до 67k (от 1 до 1005) [технически 66k]

И вы хотите, чтобы числа в позициях 3, 5, 6, 9, 10, 12 и 15 перечислили из индекса.

Таким образом,

for (freq_index = 0; freq_index <66; ++ freq_index) {
    valid.add (15 * freq_index + 3);
    valid.add (15 * freq_index + 5);
    valid.add (15 * freq_index + 6);
    valid.add (15 * freq_index + 9);
    valid.add (15 * freq_index + 10);
    valid.add (15 * freq_index + 12);
    valid.add (15 * freq_index + 15); //также первый член следующего индексированного диапазона
}

и мы исключили избыточность

=)


Упражнение для проницательного /определенного программиста:
Напишите функцию, которая принимает три целых числа в качестве аргументов, xyz и, без избыточности, находит все кратные x и y в диапазоне от 1 до z .
(в основном, обобщение того, что я сделал выше).
ответил sova 20 Jam1000000amThu, 20 Jan 2011 01:23:56 +030011 2011, 01:23:56
7

Использование генератора также возможно:

print sum (n для n в диапазоне (1000), если n% 3 == 0 или n% 5 == 0)

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

def euler001 (лимит):
    return sum (n для n в диапазоне (предел), если n% 3 == 0 или n% 5 == 0)

print euler001 (1000)
ответил 27 Jpm1000000pmThu, 27 Jan 2011 17:37:09 +030011 2011, 17:37:09
5

Общее понимание списка - это удивительное решение, но использование набора выполняется намного быстрее:

из __future__ import print_function

def euler_001 (лимит):
    s1, s2 = set (диапазон (0, предел, 3)), установить (диапазон (0, предел, 5))

    возвращаемая сумма (s1.union (s2))

печать (euler_001 (1000))
ответил Fellipe Castro 27 SatEurope/Moscow2014-12-27T19:42:50+03:00Europe/Moscow12bEurope/MoscowSat, 27 Dec 2014 19:42:50 +0300 2014, 19:42:50
2

Я использовал несколько более простой метод, но по существу сделал то же самое:

total = 0

для n в диапазоне (3,1000):
    если n% 3 == 0:
        total + = n
    elif n% 5 == 0:
        total + = n


распечатать всего

elif позволяет считать только один фактор /делитель один раз.

ответил Zachary T 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 03 Sep 2016 22:15:05 +0300 2016, 22:15:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132