2

Имеется задание, найти количество решений, нужно оптимизировать , чтобы этот код выполнялся используя не 4 цикла , а 3 (но лучше 2 цикла). Нужно понизить сложность кода.

Формула:

xa^2 + yb^2 = xc^2 + yd^2
n , x , y = map(int,input().split())

counter = 0
for a in range(n+1):
    for b in range(n+1):
        for c in range(n+1):
            for d in range(n+1):
                if (x*(a**2))+(y*(b**2)) == (x*(c**2)) +(y*(d**2)):
                    counter += 1
print(counter)
2
  • 3
    а слабо было формулу привести в вопросе, а не через кривой код
    – Zhihar
    29 ноя 2020 в 19:28
  • 1
    xa^2 + yb^2 = xc^2 + yd^2 в чём проблема?
    – Michaelan
    29 ноя 2020 в 20:22

6 ответов 6

5

У @Danis получилось очень хорошее и очень быстрое решение, но его можно сделать еще быстрее (ориентировочно где-то в 5-10 раз - проверял на n = 200, x = 10, y = 20):

list_ = [x * a * a + y * b * b
          for a in range(n + 1)
          for b in range(n + 1)]

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
local = 1
for i in range(1, len(list_)):
    if list_[i - 1] == list_[i]:
        local += 1
    else:
        counter += local**2
        local = 1

print(counter)

Вот еще более быстрый (где-то на 5%) вариант:

list_ = [x * a * a + y * b * b
          for a in range(n + 1)
          for b in range(n + 1)]

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
for i in range(1, len(list_)):
    if list_[i - 1] != list_[i]:
        counter += (i - pos)**2
        pos = i

print(counter)

Проверял на x = 10, y = 20, n = 2000, время выполнения 1,92сек

Вот этот код работает еще на 5% быстрее:

list_ = [x * a * a + y * b * b
          for a in range(n + 1)
          for b in range(n + 1)]

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
value = list_[0]
for i in range(1, len(list_)):
    if list_[i] != value:
        counter += (i - pos)**2
        pos = i
        value = list_[i]

print(counter)

Вот этот код работает еще на 18% быстрее:

list_ = []

for a in range(n + 1):
    value = x * a * a
    for b in range(n + 1):
        list_.append(value + y * b * b)

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
value = list_[0]

for i in range(1, len(list_)):
    if list_[i] != value:
        counter += (i - pos)**2
        pos = i
        value = list_[i]

print(counter)

Вот этот код работает еще на 13% быстрее:

abx = []
aby = []

for i in range(n + 1):
    abx.append(x * i * i)
    aby.append(y * i * i)

list_ = []

for a in abx:
    for b in aby:
        list_.append(a + b)

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
value = list_[0]

for i in range(1, len(list_)):
    if list_[i] != value:
        counter += (i - pos)**2
        pos = i
        value = list_[i]

print(counter)

Вот этот код работает ещё на 22% быстрее (спасибо @Danis за идею уйти от степеней):

abx = []
aby = []

for i in range(n + 1):
    abx.append(x * i * i)
    aby.append(y * i * i)

list_ = []

for a in abx:
    for b in aby:
        list_.append(a + b)

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
value = list_[0]

for i in range(1, len(list_)):
    if list_[i] != value:
        counter += (i - pos) * (i - pos)
        pos = i
        value = list_[i]

print(counter)

Вот этот код работает еще на 9% быстрее:

abx = []
aby = []

for i in range(n + 1):
    abx.append(x * i * i)
    aby.append(y * i * i)

list_ = [a + b for a in abx for b in aby]

list_.sort()
list_.append(list_[-1] + 1)

counter = 0
pos = 0
value = list_[0]

for i in range(1, len(list_)):
    if list_[i] != value:
        counter += (i - pos) * (i - pos)
        pos = i
        value = list_[i]

print(counter)
3
  • 1
    протестируйте ваш и мой код на этих данных n = 1000, x = 0, y = 0
    – Danis
    29 ноя 2020 в 22:20
  • 2
    @Danis, на 1000, 0, 0 ваш код быстрее в 1.4 раза - 0.152сек против 0.208сек, на 100, 10, 10 мой код быстрее в 110 раз (!) - 0.00365 сек против 0.4 сек, при 2000, 10, 20 мой код дает 1.92 сек, ваш работал несколько минут и я его вырубил
    – Zhihar
    29 ноя 2020 в 22:27
  • 2
    @Danis, последняя версия кода стала обгонять ваш на 45-50% для 1000, 0, 0 - 0.15сек против 0.10сек, а для 100, 10, 10 в 158 раз, однако если в ваш код поставить мой код формирования list_, то для 1000, 0, 0 ваш код работает на 28% быстрее - 0.078сек против 0.10сек, правда для 100, 10, 10 все равно в 156 раз медленнее
    – Zhihar
    29 ноя 2020 в 23:03
5
list_ = [x * a * a + y * b * b
          for a in range(n + 1)
          for b in range(n + 1)]


counter = 0
for a in set(list_):
    counter += list_.count(a) ** 2
print(counter)

Правую и левую часть можно вычислять заранее

left  = [x * i * i for i in range(n + 1)]
right = [y * i * i for i in range(n + 1)]
list_ = [a + b
         for a in left
         for b in right]

counter = 0
for a in set(list_):
    counter += list_.count(a) ** 2
print(counter)

list.count очень не эффективен, быстрее будет пройтись по всему списку и добавлять значения в словарь

left  = [x * i * i for i in range(n + 1)]
right = [y * i * i for i in range(n + 1)]
list_ = [a + b
         for a in left
         for b in right]

dict_ = {el: 0 for el in set(list_)}

for el in dict_:
    dict_[el] += 1
   
print(sum(el * el for el in dict_.values()))
3
  • 4
    красивое решение
    – Zhihar
    29 ноя 2020 в 21:55
  • 1
    Посмотрите мой ответ - я чуть подкрутил ваш алгоритм :) - отказался от set и count
    – Zhihar
    29 ноя 2020 в 22:03
  • Очень красивое решение. Я только слегка изменил ваш заключительный подсчет в моем ответе.
    – MarianD
    3 дек 2020 в 10:51
2

вариант 1 (быстрее исходного):

counter = 0

arr = []
for a in range(n + 1):
    for b in range(n + 1):
        arr.append(a**2 - b**2)

for value1 in arr:
    for value2 in arr:
        if x * value1 == y * value2:
            counter += 1

print(counter)

вариант 2 (еще быстрее):

counter = 0

arr = []
for a in range(n + 1):
    for b in range(n + 1):
        arr.append(a**2 - b**2)

for value1 in arr:
    value2 = x * value1 // y
    counter += arr.count(value2)

print(counter)

вариант 3 (возможно чуть медленнее, чем вариант 2):

arr = [(a**2 - b**2) for a in range(n + 1) for b in range(n + 1)]

counter = sum(arr.count(x * value // y) for value in arr)

print(counter)
2
  • 1
    Не подходит, слишком медленно работает.
    – Michaelan
    29 ноя 2020 в 21:01
  • 1
    Все 3 варианта медленно работают? А можно все таки тогда задачу текстом
    – Zhihar
    29 ноя 2020 в 21:05
2

Оптимизированный вариант вашей программы — около 5 раз быстрее:

n, x, y = map(int, input().split())

counter = 0
for a in range(n+1):
    a = x * a * a
    for b in range(n+1):
        b = y * b * b
        left = a + b
        for c in range(n+1):
            c = x * c * c
            for d in range(n+1):
                d = y * d * d
                if left == c + d:
                    counter += 1
print(counter)

Объяснение:

Выражения x*a^2, y*b^2 (и их сумма), x*c^2, y*d^2 вычисляются только один раз.

6
  • 1
    проверил своим для n = 100, x = 5, y = 5, мой в 6095 раз быстрее :))))
    – Zhihar
    29 ноя 2020 в 23:18
  • 1
    @Zhihar, я тоже проверил, тоже для n = 100, x = 5, y = 5. Мой в 12 раз быстрее. Проверите еще один раз - ваш результат не возможный, т. к. мой вариант делает те же самые инструкции, что ваш, но в очень меньшем количестве.
    – MarianD
    29 ноя 2020 в 23:34
  • 1
    counter = 34449, ваш код работает 11.22сек, последняя версия моего 0.002сек, использую PyCharm
    – Zhihar
    29 ноя 2020 в 23:41
  • 1
    @Zhihar, что это «последняя версия моего»?
    – MarianD
    30 ноя 2020 в 0:24
  • 1
    В посте же есть - я там несколько итераций приводил: abx = [] aby = [] for i in range(n + 1): abx.append(x * i * i) aby.append(y * i * i) list_ = [a + b for a in abx for b in aby] list_.sort() list_.append(list_[-1] + 1) counter = 0 pos = 0 value = list_[0] for i in range(1, len(list_)): if list_[i] != value: counter += (i - pos) * (i - pos) pos = i value = list_[i] print(counter)
    – Zhihar
    30 ноя 2020 в 0:27
2

Вы также можете использовать библиотеку numba, которая использует just in time компилятор(дает ускорение примерно в 40 раз), в ней можно отключать GIL и использовать мультипоточность, также есть поддержка cuda. Использование очень простое, накидываем декоратор njit на функцию и добавляем параметры какие захотим и prange есть для распаралеливания.

from numba import njit

@njit(nogil=True,parallel=True)   
def foo():
    pass
1
  • 1
    Нельзя использовать библиотеки
    – Michaelan
    2 дек 2020 в 12:06
1

Слегка улучшен конец красивого решения Danis-а — применением класса Counter:

from collections import Counter

n, x, y = map(int, input().split())

list_ = [x * a * a + y * b * b
          for a in range(n + 1)
          for b in range(n + 1)]

counter = sum(val * val for val in Counter(list_).values())
print(counter)
2
  • можно левую и правую часть вычесть заранее left = [x * i * i for i in range(n + 1)] right = [y * i * i for i in range(n + 1)] list_ = [a + b for a in left for b in right]
    – Danis
    3 дек 2020 в 11:16
  • @Danis, да, вы тем улучшили ваше собственное решение. :-)
    – MarianD
    3 дек 2020 в 11:42

Ваш ответ

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

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