задачка по python
import time
def time_passed(func):
def wrap(*args, **kwargs):
start = time.time()
func(*args, **kwargs)
end = time.time()
print('Время выполнения: {} секунд.'.format(end-start))
return wrap
@time_passed
def second_task(n, x, y, z, w):
for x in range(1, n + 1):
for y in range(1, n + 1):
if y >= x:
for z in range(1, n + 1):
if z >= y:
for w in range(1, n + 1):
if w >= z:
if (x**3 + y**3 + z**3) == w**3:
print(x, y, z, w)
second_task(100, 0, 0, 0, 0)
Этот код описывает работу функции x**3 + y**3 + z**3. Он выполняется за 21 секунду. Как можно его оптимизировать?
Ответы (6 шт):
Он выполняется за 21 секунду. Как можно его оптимизировать?
компьютер помощнее взять :)
у вас же задача O(n^4) - это очень плохо :)
Оптимизации:
Время выполнения: 4.597451210021973 секунд.
оптимизация 1:
убрать все if, а сразу устанавливать range в нужном диапазоне
def second_task(n, x, y, z, w):
for x in range(1, n + 1):
for y in range(x + 1, n + 1):
for z in range(y + 1, n + 1):
for w in range(z + 1, n + 1):
if x**3 + y**3 + z**3 == w**3:
print(x, y, z, w)
Время выполнения: 3.6760168075561523 секунд.
оптимизация 2:
не вычислять постоянно кубы, а только там где нужно:
def second_task(n, x, y, z, w):
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
for z in range(y + 1, n + 1):
z1 = z**3
for w in range(z + 1, n + 1):
if x1 + y1 + z1 == w**3:
print(x, y, z, w)
Время выполнения: 1.3132777214050293 секунд.
оптимизация 3:
если сумма кубов превышает максимальный куб - то ничего считать не надо
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
if x1 + y1 > n1:
break
for z in range(y + 1, n + 1):
z1 = z**3
if x1 + y1 + z1 > n1:
break
for w in range(z + 1, n + 1):
w1 = w**3
if x1 + y1 + z1 == w1:
print(x, y, z, w)
Время выполнения: 1.2497732639312744 секунд.
оптимизация 4:
сумму кубов считаем заранее (спасибо @mkkik):
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
if x1 + y1 > n1:
break
for z in range(y + 1, n + 1):
z1 = z**3
if x1 + y1 + z1 > n1:
break
sum = x1 + y1 + z1
for w in range(z + 1, n + 1):
w1 = w**3
if sum == w1:
print(x, y, z, w)
Время выполнения: 0.9751875400543213 секунд.
чуть-чуть скорректированный код, чтобы рассчёты в условиях тоже были выполнены заранее:
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
sum_xy = x1 + y1
if sum_xy > n1:
break
for z in range(y + 1, n + 1):
z1 = z**3
sum_xyz = sum_xy + z1
if sum_xyz > n1:
break
for w in range(z + 1, n + 1):
w1 = w**3
if sum_xyz == w1:
print(x, y, z, w)
Время выполнения: 0.9624927043914795 секунд.
оптимизация 5:
последний цикл не выполняем, а сразу ищем w исходя из кубического корня от суммы кубов
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
sum_xy = x1 + y1
if sum_xy > n1:
break
for z in range(y + 1, n + 1):
z1 = z**3
sum_xyz = sum_xy + z1
if sum_xyz > n1:
break
w = int(sum_xyz ** (1 / 3)) + 1
if sum_xyz == w**3:
print(x, y, z, w)
Время выполнения: 0.10163164138793945 секунд.
оптимизация 6 (чисто техническая)
свести к минимуму промежуточные вычисления (в промежуточные переменные)
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
sum_x = x**3
for y in range(x + 1, n + 1):
sum_xy = sum_x + y**3
if sum_xy > n1:
break
for z in range(y + 1, n + 1):
sum_xyz = sum_xy + z**3
if sum_xyz > n1:
break
w = int(sum_xyz ** (1 / 3)) + 1
if sum_xyz == w**3:
print(x, y, z, w)
Время выполнения: 0.09478282928466797 секунд.
оптимизация 7 (спасибо mkkik)
куб value***3 надо заменить на произведение value * value * value
def second_task(n, x, y, z, w):
n1 = (n+1)**3
for x in range(1, n + 1):
sum_x = x * x * x
for y in range(x + 1, n + 1):
sum_xy = sum_x + y * y * y
if sum_xy > n1:
break
for z in range(y + 1, n + 1):
sum_xyz = sum_xy + z * z * z
if sum_xyz > n1:
break
w = int(sum_xyz ** (1 / 3)) + 1
if sum_xyz == w * w * w:
print(x, y, z, w)
Время выполнения: 0.06644511222839355 секунд.
оптимизация 8 (маленькая)
если сумма кубов равна кубу - сразу выйти из цикла по z - это немного сэкономит времени, поскольку и так проверка работает
if sum_xyz == w * w * w:
print(x, y, z, w)
break
Время выполнения: 0.06352448463439941 секунд.
оптимизация 9 (техническая)
на самом деле выход за диапазон разрешенных значений можно сделать жестче и вместо n1 = (n + 1)**3 смело можно писать n1 = n**3
Время выполнения: 0.06155967712402344 секунд.
import numba
@numba.jit
def second_task(n, x, y, z, w):
for x in range(1, n + 1):
x1 = x**3
for y in range(x + 1, n + 1):
y1 = y**3
for z in range(y + 1, n + 1):
z1 = z**3
for w in range(z + 1, n + 1):
if x1 + y1 + z1 == w**3:
pass
#print(x, y, z, w)
%%timeit
second_task(100, 0, 0, 0, 0) # 493 ns ± 46.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
def second_task(n, x, y, z, w):
dict_ = {x * x * x: x for x in range(1, n + 1)}
list_ = list(dict_.items())
max_n = list_[-1][0]
for sum_x, x in list_:
for sum_y, y in list_[x:]:
sum_xy = sum_x + sum_y
if sum_xy > max_n:
break
for sum_z, z in list_[y:]:
sum_xyz = sum_xy + sum_z
if sum_xyz > max_n:
break
if sum_xyz in dict_:
print(x, y, z, dict_[sum_xyz])
Вариант @Zhihar на моем телефоне выполнялся в среднем за 0.48 секунд, а мой за 0.11 секунд
слегка модифицированный код от @Danis:
def second_task(n, x, y, z, w):
# сформировать таблицу кубов
table = [i**3 for i in range(n + 1)]
table2 = frozenset(table)
res = []
for x in range(1, n + 1):
sum_x = table[x]
for y in range(x, n + 1):
sum_xy = sum_x + table[y]
for z in range(y, n + 1):
sum_xyz = sum_xy + table[z]
if sum_xyz in table2:
res.append((x, y, z, sum_xyz))
вспомогательные условия уже никак не влияют на скорость
в результата:
Время выполнения: 0.011726140975952148 секунд.
Новый код:
подход - сначала считаем сумму двух кубов, потом разницу двух кубов и ищем соответствия
def second_task(n, x, y, z, w):
# сформировать таблицу кубов
table = [i**3 for i in range(n + 1)]
# сформировать таблицу суммы кубов
table_sums = dict()
for x in range(1, n + 1):
for y in range(x, n + 1):
sum_xy = table[x] + table[y]
if sum_xy not in table_sums:
table_sums[sum_xy] = [(x, y)]
else:
table_sums[sum_xy].append((x, y))
# пройтись по разности кубов и найти совпадение с суммой кубов
res = []
for z in range(1, n + 1):
for w in range(z, n + 1):
dif_wz = table[w] - table[z]
if dif_wz in table_sums:
for sum_xy in table_sums[dif_wz]:
(x_res, y_res), z_res, w_res = sum_xy, z, w
if x_res <= y_res <= z_res <= w_res:
res.append((x_res, y_res, z_res, w_res))
print(len(res))
В результате:
Время выполнения: 0.0029311180114746094 секунд.
P.S.
только что увидел, что аналогичный подход сделал @belo4ya
Мой велосипед:
def second_task(n, x, y, z, w):
solutions = []
cubes = [(x, x*x*x) for x in range(1, n+1)]
m3 = cubes[-1][1]
for x, x3 in cubes:
for y, y3 in cubes[x:]:
for z, z3 in cubes[y:]:
x3y3z3 = x3+y3+z3
w = ceil(x3y3z3 ** (1/3))
if m3 >= x3y3z3 == cubes[w-1][1]:
solutions.append((x, y, z, w))
return solutions
Ребят, а что если такой алгоритм?
Временная сложность алгоритма O(n^2)
def solution(n=1000):
"""
Вместо того чтобы вычислять все пары (с, d) для каждой пары (а, b), список
пар (c, d) достаточно построить всего один раз. Тогда для каждой пары (а,b) поиск
будет вестись по списку (с , d).
Но если мы построили хеш со всеми парами (с, d), генерировать пары (а, b)
не нужно - каждая пара (а, b) уже присутствует в хеше.
"""
result = []
map_ = {}
for c in range(1, n + 1):
for d in range(1, n + 1):
res = c ** 3 + d ** 3
if map_.get(res) is None:
map_[res] = []
map_[res].append((c, d))
for pairs in map_.values():
for pair_ab in pairs:
for pair_cd in pairs:
# print(pair_ab[0], pair_ab[1], pair_cd[0], pair_cd[1])
result.append((pair_ab[0], pair_ab[1], pair_cd[0], pair_cd[1]))
return result