如何避免在暴力搜查中重复检查？

Question

我在reddit上看到一个post关于Euler猜想的反例。我决定自己试试蛮力计算法。你知道吗

我的密码是

import numpy as np

fifths1  = np.arange(1,151)

fifths = fifths1**5

for x in fifths1:
    for y in fifths1:
        for z in fifths1:
            for w in fifths1:

                lambdas=[x,y,z,w]

                if sum(np.array(lambdas)**5) in fifths:


                    print((x,y,z,w))

但是，代码需要很长时间，因为它会对案例进行三重检查。你知道吗

从我链接的论文来看，反例是

27^5 + 84^5 + 110^5 + 113^5 = 144^5

我的代码返回

(27, 84, 110, 133)
(27, 84, 133, 110)
(27, 110, 84, 133)
(27, 110, 133, 84)
(27, 133, 84, 110)
(27, 133, 110, 84)

如何优化暴力搜索，使其不会多次检查同一案例。你知道吗

Answer 1

我认为NumPy是错误的图书馆在这里使用。你知道吗

这不是一个可以很容易地以当前形式矢量化的问题（使用该库的最大原因），而且，在NumPy数组上循环比在Python列表上循环要慢得多。你知道吗

每次在内部循环中构造一个新的NumPy数组并使用in检查和（复杂性为O(n)），也会导致性能下降。你知道吗

正如其他人所指出的，itertools允许您测试四个五次方的每一个组合一次。使用集合成员身份（O(1)复杂性）检查这些幂的和是否也是第五个幂也将提高性能：

import itertools

fifths = [x**5 for x in range(1, 151)]
f_set = set(fifths)

[x for x in itertools.combinations(fifths, 4) if sum(x) in f_set]

很快就会回来：

[(14348907, 4182119424, 16105100000, 41615795893)]

然后你可以从那里恢复第五根。你知道吗

Answer 2

通过计算每个循环中的当前位置，并在以后的循环中仅从该位置开始，可以避免多次执行该操作：

import numpy as np

fifths1  = np.arange(1,151)

fifths = fifths1**5

for i, x in enumerate(fifths1):
    for j, y in enumerate(fifths1[i:]):
        for k, z in enumerate(fifths1[i+j:]):
            for w in fifths1[i+j+k:]:

                lambdas=[x,y,z,w]

                if sum(np.array(lambdas)**5) in fifths:


                    print((x,y,z,w))

通过使用预先计算的**5值，可以进一步加快速度：

import numpy as np

fifths1  = np.arange(1,151)

fifths = fifths1**5

fifthsall = np.vstack([fifths1, fifths]).T

for i, (x1, x) in enumerate(fifthsall):
    for j, (y1, y) in enumerate(fifthsall[i:, :]):
        for k, (z1, z) in enumerate(fifthsall[i+j:, :]):
            for w1, w in fifthsall[i+j+k:, :]):
                if x+y+z+w in fifths:
                    print((x1,y1,z1,w1))

Answer 3

只需使用itertools.combinations而不是手动循环：

import itertools 
for x, y, z, w in itertools.combinations(fifths, 4):
    #etc.