Более эффективный способ грубого поиска решений (x + y) ^ 2 = str (x) + str (y)?Это может быть векторизация?

Question

Пока что я написал:

n=1000
solutions=[]
for i in range(1,n+1):
    for j in range(1,n+1):
        if str((i+j)**2)==str(i)+str(j):
            solutions.append("("+str(i)+"+"+str(j)+")^2 = "+str((i+j)**2))
for solution in solutions:
    print(solution)

Это занимает 1,03 секунды на моем компьютере.Есть ли более быстрый способ осуществить сравнение?Я нашел страницу на векторизация , но я не уверен, как мне сгенерировать список, который мне понадобится, чтобы затем векторизовать сравнение.

Answer 1

Это может быть достигнуто еще быстрее, если искать пару (x, y), которая удовлетворяет уравнению для данного квадрата в вашем целевом диапазоне.Фактически это уменьшает проблему со O(n^2) до O(nlogn) сложности времени.

def split_root(n):
    div = 10
    while div < n:
        x, y = divmod(n, div)
        div *= 10
        if not y or y < div // 100: continue
        if (x + y) ** 2 == n: yield x, y

Затем просто выполните итерации по возможным квадратам:

def squares(n):
    for i in range(n):
        for sr in split_root(i ** 2):
            yield "({}+{})^2 = {}".format(*sr, sum(sr)**2)

Пример использования:

print("\n".join(squares(100000)))

Вывод:

(8+1)^2 = 81
(20+25)^2 = 2025
(30+25)^2 = 3025
(88+209)^2 = 88209
(494+209)^2 = 494209
(494+1729)^2 = 4941729
(744+1984)^2 = 7441984
(2450+2500)^2 = 24502500
(2550+2500)^2 = 25502500
(5288+1984)^2 = 52881984
(6048+1729)^2 = 60481729
(3008+14336)^2 = 300814336
(4938+17284)^2 = 493817284
(60494+17284)^2 = 6049417284
(68320+14336)^2 = 6832014336

Для сравнения, ваше оригинальное решение -

def op_solver(n):
    solutions = []
    for i in range(1,n+1):
        for j in range(1,n+1):
            if str((i+j)**2)==str(i)+str(j):
                solutions.append("("+str(i)+"+"+str(j)+")^2 = "+str((i+j)**2))
    return solutions


>>> timeit("op_solver(1000)", setup="from __main__ import op_solver", number=5) / 5
0.8715057126013562

Мое решение -

>>> timeit("list(squares(2000))", setup="from __main__ import squares", number=100) / 100
0.006898956680088304

Примерно 125-кратное ускорение дляпример использования, и он будет работать асимптотически быстрее по мере роста n.

Это также дает преимущество, заключающееся в том, что он быстрее и проще, чем решение с numpy, и, конечно, не требует numpy.Если вам нужна более быстрая версия, я уверен, что вы даже можете векторизовать мой код, чтобы получить лучшее из обоих миров.

Answer 2

Вы можете ускорить вычисления, избегая манипуляций со строками.Вместо объединения строк используйте i * 10**(int(math.log10(j))+1) + j для численного «объединения»:

In [457]: i, j = 20, 25; i * 10**(int(math.log10(j))+1) + j
Out[457]: 2025

Вы также можете использовать NumPy для векторизации вычисления:

import numpy as np
n = 1000

def using_numpy(n):
    i = range(1, n+1)
    j = range(1, n+1)
    I, J = np.meshgrid(i, j)

    left = (I+J)**2
    j_digits = np.log10(J).astype(int) + 1
    right = I*10**j_digits + J
    mask = left == right
    solutions = ['({i}+{j})^2 = {k}'.format(i=i, j=j, k=k)
                 for i, j, k in zip(I[mask], J[mask], left[mask])]
    return solutions

def using_str(n):
    solutions=[]
    for i in range(1,n+1):
        for j in range(1,n+1):
            if str((i+j)**2)==str(i)+str(j):
                solutions.append("("+str(i)+"+"+str(j)+")^2 = "+str((i+j)**2))
    return solutions

print('\n'.join(using_numpy(n)))
# print('\n'.join(using_str(n)))

выход

(8+1)^2 = 81
(20+25)^2 = 2025
(30+25)^2 = 3025
(88+209)^2 = 88209
(494+209)^2 = 494209

---

Для n = 1000, using_numpy примерно в 16 раз быстрее, чем using_str:

In [455]: %timeit using_str(n)
500 ms ± 251 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [470]: %timeit using_numpy(n)
31.1 ms ± 98.3 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)