Проект Эйлера задача 1 в Python - кратные 3 и 5


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

'''
If we list all the natural numbers below 10 that are multiples of 3 or 5, 
we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
'''

end = 1000

def Solution01():
    '''
        Solved by brute force
        #OPTIMIZE
    '''
    sum = 0
    for i in range(3, end):
        if isMultiple(i):
            sum += i 
    print(sum)

def isMultiple(i):
    return (i % 3 == 0) or (i % 5 == 0)


Комментарии
4 ответа

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

valid = set([])

for i in range(3, end, 3):
valid.add(i)

for i in range(5, end, 5):
valid.add(i)

total = sum(valid)

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

27
ответ дан 19 января 2011 в 09:01 Источник Поделиться

Я хотел избавиться от для петель и использовать сумму на генератор выражений.

def solution_01(n):
partialsum = sum(xrange(3, n, 3))
return partialsum + sum(x for x in xrange(5, n, 5) if x % 3)

Обратите внимание, что мы используем xrange вместо диапазона для Python 2. Я никогда не видел случай, когда это не быстрее для для петли или генератор выражение. Также потребляя генератор выражение сумма должна быть быстрее, чем добавлять их вручную В для петли.

Если вы хотели сделать это с комплекта, то тут все еще нет необходимости для петли

def solution_01(n):
values = set(range(3, n, 3)) | set(range(5, n, 5))
return sum(values)

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

17
ответ дан 20 января 2011 в 06:01 Источник Поделиться

Я бы сделал это так:

total = 0

for i in range(3, end, 3):
total += i

for i in range(5, end, 5):
if i % 3 != 0: # Only add the number if it hasn't already
total += i # been added as a multiple of 3

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


  1. Проверка делимости является менее дорогостоящим, чем добавление к набору.

  2. Мы строим общий постепенно, так что нам не нужен отдельный вызов суммой в конце.

  3. Мы избавились от набора, так что нам нужно только постоянное место.

12
ответ дан 20 января 2011 в 04:01 Источник Поделиться

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

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

Порядок, в котором вы добавляете их:

 add 3-multiples first
add 5 multiples second

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

То есть, если ваш алгоритм-это что-то вроде

add 3-multiples to the list

add 5-multiples to the list if they don't collide

он будет выполнять несколько хуже, чем

add 5-multiples to the list

add 3-multiples to the list if they don't collide

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

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


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

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

Один способ-это видеть частоты кратные. То есть, обратите внимание, что НОК (наименьшего общего кратного) 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

Свои частоты возникающие (я вроде как составляя словарь для этого, поэтому, пожалуйста, поправьте меня, если есть лучше математику-у слов), в Начиная показателях от 0К + 1 до 67к (от 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); //also the first term of the next indexed range
}

и мы устранили избыточность

=)



Упражнения для проницательный / определяется программистом:
Написать функцию, которая принимает три числа в качестве аргументов х, у, Z и, без избыточности, обнаруживает все кратные х и г в диапазоне от 1 до з.
(в основном это обобщение того, что я сделал выше).

8
ответ дан 19 января 2011 в 10:01 Источник Поделиться