@MAGistr_MTM
Учусь программировать

Как улучшить скорость функции?

Доброе время суток.
У меня задание состоит в следующем: выбрать все пары чисел (a, b) меньших за n, которые удовлетворяют условию: a * b == (sum(1..n) - a - b). Пары (a, b) и (b, a) - разные.
Я написал код, но он слишком медленный. Что можете посоветовать?
def removNb(n):
    return [(a, b)  for a in range(n+1) for b in range(n+1) if sum(range(n+1)) - a - b == a * b]
  • Вопрос задан
  • 607 просмотров
Решения вопроса 2
Mrrl
@Mrrl
Заводчик кардиганов
Записать условие в виде (a+1)*(b+1) == n*(n+1)/2+1 = N, и для чисел a от (n+1)/2 до n проверить, делится ли N на a+1. Если делится, то b=N/(a+1)-1. На всякий случай, проверить, что b < n+1.
При желании, перебор можно сократить примерно в 12 раз. Но тогда вместо проверки делимости надо будет быстро проверять, является ли число полным квадратом - что может быть не очень просто.
Ответ написан
@throughtheether
human after all
Что можете посоветовать?

sum(range(n+1)) - константа (в дальнейшем, C) для заданного n, можно вынести ее вычисление за цикл.
Далее, ваше уравнение можно переписать: b = (C-a)/(a+1). Можно перейти от квадратичного времени к линейному, итерируя по a и проверяя делимость (C-a) на (а+1)

Навскидку:
def get_ab(n):
	C=sum(xrange(1,n+1))
	return [(a, (C-a)/(a+1)) for a in xrange(1,n+1) if (C-a)%(a+1)==0 and (C-a)/(a+1)<n]


In [10]: % timeit removNb(10)
1000 loops, best of 3: 185 us per loop
In [11]: %timeit get_ab(10)
100000 loops, best of 3: 6.74 us per loop
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы