Самые большие улучшения исходят от использования лучшего алгоритма. Такие вещи, как
Было бы лучше, если вместо определения s(n) в качестве функции я поместил код в основную программу?
или следует ли использовать while петлю вместо for i in xrange(1, MAXM + 1): не имеет большого значения, поэтому не следует рассматривать, прежде чем один достиг состояния, в котором алгоритмические улучшения, по крайней мере очень трудно найти.
Итак, давайте посмотрим на ваш алгоритм и как мы можем радикально улучшить его, не заботясь о мелочных вещах, например, как цикл while, так и итерация for быстрее.
def s(n):
tsum = 0
i = 1
con = n
while i < con:
if n % i == 0:
temp = n/i
tsum += i
if temp != i:
tsum += temp
con = temp
i += 1
return tsum
Это уже содержит хорошую идею, вы знаете, что делители n приходят пары и добавить оба делителей, как только вы обнаружили, что меньше пары. Вы даже правильно обрабатываете квадраты.
Он отлично подходит для чисел типа 120: когда вы находите делитель 2, вы устанавливаете условие остановки на 60, когда вы находите 3, 40, ..., когда вы находите 8, вы устанавливаете его на 15 , когда вы найдете 10, вы установите его на 12, а затем у вас будет только деление на 11 и остановитесь, когда i будет увеличено до 12. Неплохо.
Но это не так хорошо работает, когда n является простым, то con никогда не будет установлен на значение меньше, чем n, и вам нужно перебирать весь путь до n, прежде чем вы нашли сумму делителей. Это не также плохо для чисел вида n = 2*p с премьером p, то петля для n/2 или n = 3*p (n/3, если p = 2) и т.д.
По теореме простого числа, число простых чисел, не превышающие x асимптотический x/log x (где log натуральный логарифм), и у вас есть нижняя граница
Ω(MAXNUM²/log MAXNUM)
только для вычисления суммы делителей простых чисел. Это не хорошо.
Поскольку вы уже считаете делители n в парах d и n/d, обратите внимание, что меньший из двух (без учета регистра d = n/d когда n является квадратом на данный момент) меньше, чем квадратный корень из n, так сразу тестовый делитель достиг квадратного корня, вы знаете, что вы нашли и добавили все делители, и все готово. Любой дальнейший цикл - бесполезная расточительная работа.
Итак, давайте рассмотрим
def s(n):
tsum = 0
root = int(n**0.5) # floor of the square root of n, at least for small enough n
i = 1
while i < root + 1:
if n % i == 0:
tsum += i + n/i
i += 1
# check whether n is a square, if it is, we have added root twice
if root*root == n:
tsum -= root
return tsum
в качестве первого улучшения. Затем вы всегда зацикливаете квадратный корень, а вычисление s(n) для 1 <= n <= MAXNUM - Θ(MAXNUM^1.5). Это уже довольно улучшилось. (Разумеется, вам нужно вычислить итерированные суммы дивизоров, а s(n) может быть больше MAXNUM для некоторого n <= MAXNUM, поэтому вы не можете сделать оценку сложности O(MAXM * MAXNUM^1.5) для всего алгоритма. Но s(n) не может быть намного больше, так что сложность не может быть гораздо хуже, либо.)
Но мы все еще можем улучшить, что с помощью какой twalbergsuggested, используя простые множители n вычислить сумму делителей.
Во-первых, если n = p^k является основная мощность, делители n являются 1, p, p², ..., p^k, а сумма делителем легко вычисляется (замкнутая формула для геометрической суммой является
(p^(k+1) - 1)/(p - 1)
, но использует ли тот, или добавляет k+1 полномочия p деление n не важно).
Далее, если n = p^k * m с премьер p и m такое, что p не делит m, то
s(n) = s(p^k) * s(m)
Простой способ увидеть, что разложение, чтобы написать каждый дивизор d из n в виде d = p^a * g где p не делит g. Затем p^a должен делить p^k, то есть a <= k и g должен делить m. И наоборот, за каждые 0 <= a <= k и каждые g деление m, p^a * g является делителем n. Таким образом, мы можем выложить делители n (где 1 = g_1 < g_2 < ... < g_r = m являются делителями m)
1*g_1 1*g_2 ... 1*g_r
p*g_1 p*g_2 ... p*g_r
: : :
p^k*g_1 p^k*g_2 ... p^k*g_r
и сумма каждой строки p^a * s(m).
Если у нас есть список простых чисел удобно, мы можем написать
def s(n):
tsum = 1
for p in primes:
d = 1
# divide out all factors p of n
while n % p == 0:
n = n//p
d = p*d + 1
tsum *= d
if p*p > n: # n = 1, or n is prime
break
if n > 1: # one last prime factor to account for
tsum *= 1 + n
return tsum
Деление судебный процесс идет на второй по величине простого фактора n [если n составное] или квадратный корень из наибольшего расцвета фактор n, в зависимости от того, что больше. Он имеет худший случай для наибольшего делителя, который пытался получить n**0.5, что достигается для простых чисел, но для большинства композитов разделение останавливается намного раньше.
Если мы не имеем список простых чисел удобный, мы можем заменить строку for p in primes: с for p in xrange(2, n): [верхний предел не важен, так как он никогда не будет достигнуто, если он больше, чем n**0.5] и получить не слишком много медленная факторизация.(Но его можно легко ускорить, избегая даже пробных делителей больше 2, то есть используя список [2] + [3,5,7...] - лучше всего в качестве генератора - для делителей, еще больше, также пропуская кратные 3 (кроме 3), [2,3] + [5,7, 11,13, 17,19, ...] и если вы хотите несколько дополнительных небольших простых чисел.)
Теперь, что помогло, но вычисления делителей суммы для всех n <= MAXNUM еще занимаете Ω(MAXNUM^1.5/log MAXNUM) время (я не проанализировал, что может быть также верхней границей, или MAXNUM^1.5 во всяком случае, может быть нижней границей, во всяком случае, логарифмический фактор редко делает большую разницу [за постоянным фактором]).
И вы вычисляете много сумм дивизоров более одного раза (в вашем примере вы вычисляете s(56) при исследовании 12, снова при исследовании 28, снова при расследовании 56). Чтобы облегчить влияние этого, было бы неплохо запомнить меморандум s(n). Затем вам нужно вычислить каждый s(n) только один раз.
И теперь мы уже торгуем пространством по времени, поэтому мы можем использовать лучший алгоритм для вычисления сумм дивизоров для всех 1 <= n <= MAXNUM за один раз с лучшей временной сложностью (а также меньшими постоянными факторами). Вместо того, чтобы опробовать каждое достаточно маленькое (простое) число, независимо от того, делится ли оно n, мы можем сразу отметить только кратные, таким образом избегая всех делений, которые оставляют остаток, что является подавляющим большинством.
Простой способ сделать это
def divisorSums(n):
dsums = [0] + [1]*n
for k in xrange(2, n+1):
for m in xrange(k, n+1, k):
dsums[m] += k
return dsums
с O(n * log n) временной сложности. Вы можете сделать это немного лучше (O(n * log log n) сложность) с помощью простой факторизации, но этот метод несколько сложнее, я не добавляю его сейчас, может быть, позже.
Затем вы можете использовать список всех делителей сумм смотреть вверх s(n) если n <= MAXNUM, и выше реализации s(n) для вычисления суммы делителей для значений больше, чем MAXNUM [или вы можете memoize значения до большего предел].
dsums = divisorSums(MAXNUM)
def memo_s(n):
if n <= MAXNUM:
return dsums[n]
return s(n)
Это не так уж и плохо,
Found 414 distinct (m-k)-perfect numbers (0.10350 per cent of 400000) in 496 occurrences
Found 4 perfect numbers
Found 8 multiperfect numbers (including perfect numbers)
Found 7 superperfect numbers
12.709428072 seconds
для
import time
start_time = time.time()
def s(n):
tsum = 1
for p in xrange(2,n):
d = 1
# divide out all factors p of n
while n % p == 0:
n = n//p
d = p*d + 1
tsum *= d
if p*p > n: # n = 1, or n is prime
break
if n > 1: # one last prime factor to account for
tsum *= 1 + n
return tsum
def divisorSums(n):
dsums = [0] + [1]*n
for k in xrange(2, n+1):
for m in xrange(k, n+1, k):
dsums[m] += k
return dsums
MAXM = 6
MAXNUM = 400000
dsums = divisorSums(MAXNUM)
def memo_s(n):
if n <= MAXNUM:
return dsums[n]
return s(n)
i = 2
perc = 0
perc1 = 0
perf = 0
multperf = 0
supperf = 0
while i <= MAXNUM:
pert = perc1
num = i
for m in xrange(1, MAXM + 1):
tsum = memo_s(num)
if tsum % i == 0:
perc1 += 1
k = tsum/i
mes = "%d is a (%d-%d)-perfect number" % (i, m, k)
if m == 1:
multperf += 1
if k == 2:
perf += 1
print mes + ", that is a perfect number"
else:
print mes + ", that is a multiperfect number"
elif m == 2 and k == 2:
supperf += 1
print mes + ", that is a superperfect number"
else:
print mes
num = tsum
i += 1
if pert != perc1: perc += 1
print "Found %d distinct (m-k)-perfect numbers (%.5f per cent of %d) in %d occurrences" % (
perc, float(perc)/MAXNUM * 100, MAXNUM, perc1)
print "Found %d perfect numbers" % perf
print "Found %d multiperfect numbers (including perfect numbers)" % multperf
print "Found %d superperfect numbers" % supperf
print time.time() - start_time, "seconds"
К memoizing также необходимых делителей сумм для n > MAXNUM:
d = {}
for i in xrange(1, MAXNUM+1):
d[i] = dsums[i]
def memo_s(n):
if n in d:
return d[n]
else:
t = s(n)
d[n] = t
return t
время падает до
3.33684396744 seconds
Неужели это _really_ slow? Это только совет, но как новичок, вам действительно нужно найти способ запустить ваш код «быстрее»? Прежде всего, вы должны иметь более читаемый и поддерживаемый код. На самом деле, это совет, который я использовал, чтобы дать (много) более опытным программистам тоже ... –
, если бы вы знали C, было бы очень легко конвертировать ... большинство, если это уже код C, вам просто нужно фигурные скобки и точки с запятой :) –
+ Для исполнения, иногда новички сосредотачиваются на вещах, которые не имеют большого значения. [* Вот метод *] (http://stackoverflow.com/a/4299378/23771) Я использую. Он расскажет вам, какие части кода заслуживают внимания. –