滑动窗口和记忆的计算

Question

我正在研究Project Euler Problem 50,它指出:

素数41可以写成六个连续素数的总和:

41 = 2 + 3 + 5 + 7 + 11 + 13这是连续素数的最长和,它加到低于一百的素数.

低于一千的连续素数的最长和加上一个素数,包含21个项,并且等于953.

哪个素数低于一百万,可以写成最连续素数的总和？

为了确定素数P中的项(如果它可以写成素数的总和),我使用所有素数的滑动窗口(按递增顺序)直到(但不包括)P,并计算所有的总和这些窗口,如果总和等于考虑的素数,我算一下窗口的长度......

这适用于1000以下的所有素数,但是对于高达10**6的素数来说它非常慢,所以我希望备忘录会有所帮助; 在计算滑动窗口的总和时,做了很多双重工作......(对吧？)

所以我在网上找到了标准的memoizaton实现,并将其粘贴在我的代码中,这是正确的吗？(我不知道应该怎么在这里工作......)

primes = tuple(n for n in range(1, 10**6) if is_prime(n)==True)

count_best = 0


##http://docs.python.org/release/2.3.5/lib/itertools-example.html:
## Slightly modified (first for loop)
from itertools import islice
    def window(seq):
    for n in range(2, len(seq) + 1):

        it = iter(seq)
        result = tuple(islice(it, n))
        if len(result) == n:
            yield result    
        for elem in it:
            result = result[1:] + (elem,)
            yield result   

def memoize(function):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            val = function(*args)
            cache[args] = val
            return val
    return decorated_function


@memoize 


def find_lin_comb(prime):
    global count_best

    for windows in window(primes[0 : primes.index(prime)]):
        if sum(windows) == prime and len(windows) > count_best:
            count_best = len(windows)
            print('Prime: ', prime, 'Terms: ', count_best)


##Find them:
for x in primes[::-1]: find_lin_comb(x)

(顺便说一句,素数的元组是"正常"快速生成的)

所有的输入都很受欢迎,我只是一个业余爱好程序员,所以请不要对我有所了解.

谢谢!

编辑:这是一个没有破坏缩进的工作代码粘贴:http: //pastebin.com/R1NpMqgb

Answer 1

\n

这对于 1000 以内的所有素数来说效果很好，但是对于 10**6 以内的素数来说它非常慢，所以我希望记忆会有所帮助；当计算滑动窗口的总和时，做了很多双重工作......（对吗？）

\n

\n\n

是的，没错。当然，对于 10 ⁶以内的素数来说，速度很慢。

\n\n

假设您有n至 的素数N，按递增顺序编号，p_1 = 2, p_2 = 3, ...。当考虑是否素数时。k是连续素数的总和，您考虑所有窗口[p_i, ..., p_j]，对于 与 的(i,j)对i < j < k。有这样(k-1)*(k-2)/2的人。遍历所有k到n，您n\xc2\xb3/6总共检查了有关窗口（计算多重性，您正在检查w(i.j)总n-j时间）。即使忽略创建窗口并将其求和的成本，您也可以看到它的缩放效果如何：

\n\n

\n
• 对于N = 1000，n = 168有素数和大约 790000 个窗口需要检查（计算重数）。
\n
• 对于N = 10**6，有n = 78498质数和约8.3*10**13窗口可供检查。
\n

\n\n

现在考虑创建和求和窗口的工作，将中的素j-i+1数求和估计为低，工作量约为，总工作量大致为。大约 3300 万步，花生米，但接近。j-i+1w(i,j)p_kk\xc2\xb3/6k**4/24N = 10001.6*10**18N = 1000000

\n\n

一年大约包含3.1*10**7几秒，对于大约 3GHz 的 CPU，大约是 10 ^{17 个}时钟周期。因此，我们讨论的是需要大约 100 个 CPU 年的操作（可能是 10 倍左右）。

\n\n

我想你不愿意等那么久；）

\n\n

现在，通过记忆，您仍然可以多次查看每个窗口，但只需对每个窗口进行一次计算。这意味着您需要n\xc2\xb3/6计算窗口，并查看n\xc2\xb3/6任何窗口的时间。

\n\n

\n
• 问题1：你仍然需要查看大约8.3*10**13几次窗口，即使查看只花费一个周期，也要几个小时。
\n
• 问题2：有关于8.3*10**13windows需要记忆。你没有那么多内存，除非你可以使用非常大的硬盘。
\n

\n\n

您可以通过丢弃不再需要的数据并仅在需要时计算窗口数据来规避内存问题，但是一旦您知道何时可以丢弃哪些数据，您应该能够看到更好的方法。

\n\n

\n

1000 以下连续素数的最长和相加为一个素数，包含 21 项，等于 953。

\n

\n\n

关于生成该总和的窗口，这告诉您什么？可以从哪里开始，又可以从哪里停止呢？如何使用这些信息来创建有效的算法来解决问题？

\n