8
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 секунду. Как можно его оптимизировать?

4
  • Что значит "описывает работу функции"?
    – dIm0n
    16 окт 2020 в 11:34
  • Для начала циклы обхода y, z, w начинать соответственно с x, y, z, а не с 1. Кубы для x, y, z посчитать один раз на первой итерации цикла.
    – user207200
    16 окт 2020 в 11:36
  • Есть функция x3 + y3 + z3 == w3. Код выбирает все подходящие значения переменных и выводит время, которое ему понадобилось, чтобы это сделать. Но если в вызове поставить не 100, а, например, 10000, то это будет слишком долго. Вот и надо оптимизировать
    – Listopad02
    16 окт 2020 в 11:39
  • Мне тут непонятно только одно: аргументы) Они как-то должны были использоваться?
    – vp_arth
    10 ноя 2020 в 21:45

6 ответов 6

19

Он выполняется за 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 секунд.

1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – Grundy
    24 янв 2021 в 12:37
6
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)
6
  • 1
    Правда подозреваю, там что-то закешировалось, в одиночных прогонах около 200 ms выполняется. 16 окт 2020 в 11:54
  • 2
    Лучше примите ответ другого автора, мне кажется, я не заслужил :) 16 окт 2020 в 12:02
  • эта библиотека для компиляции? а можете проверить, сколько она выдаст на последнем моем коде (9 оптимизация) - у меня ее под рукой нет - питон ругается
    – Zhihar
    16 окт 2020 в 12:36
  • Время выполнения: 0.009000062942504883 секунд. 16 окт 2020 в 12:46
  • 1
    просто главная оптимизация - свести задачу с O(n^4) до O(n^3), поэтому подумалось, что и тут это должно отразиться :)
    – Zhihar
    16 окт 2020 в 12:49
2

Ребят, а что если такой алгоритм?

Временная сложность алгоритма 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
2
  • опередили меня!!! сегодня аналогичный код закодил - посмотрите один из моих комментариев, только чуть-чуть по другому выглядит
    – Zhihar
    11 ноя 2020 в 7:52
  • попробовал ваш код - он находит 20260 вариантов вместо 82, 0.014666557312011719 секунд., так что мысль правильная, а вот реализация подкачала
    – Zhihar
    11 ноя 2020 в 7:55
1

Мой велосипед:

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
0
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 секунд

6
  • э.. есть одно но - проверил свой алгоритм выдает 81 значение против 77 значений у текущего
    – Zhihar
    10 ноя 2020 в 19:52
  • @Zhihar все исправил
    – Danis
    10 ноя 2020 в 20:08
  • 1
    теперь Время выполнения: 0.01367950439453125 секунд. Я добавил в свой код вашу идею - подход поиска в множестве (по сути бинарный поиск) - Время выполнения: 0.012711048126220703 секунд. - думаю чуть побыстрее за счет использования не словаря а множества и прочей мелочи, вопрос - можно ли сделать принципиально существенный скачек теперь
    – Zhihar
    10 ноя 2020 в 20:15
  • добавил тоже свой код в новом ответе - он по сути ровно такой же, но выкинул все if поскольку они уже никак на скорость не влияют, даже наоборот :)
    – Zhihar
    10 ноя 2020 в 20:54
  • 1
    сделал скачек до 0.0029311180114746094 секунд - посмотрите код - добавил во втором своем комментарии, память правда теперь O(n^2) используется, пользователь @belo4ya, ранее тоже предложил тот же подход, правда там некоторые вопросы к коду, но мысль верная!
    – Zhihar
    11 ноя 2020 в 7:57
0

слегка модифицированный код от @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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.