python - 滑动窗口和内存的计算

Question

我正在研究 Project Euler Problem 50，其中指出:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

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

这对于 1000 以内的所有素数都可以正常工作，但对于 10**6 以内的素数来说，速度非常慢，所以我希望memozation 会有所帮助；在计算滑动窗口之和时，做了很多双重工作......(对吗？)

所以我在网上找到了标准的 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

This works fine for all primes up to 1000, but for primes up to 10**6 it is very slow, so I was hoping memozation would help; when calculating the sum of sliding windows, a lot of double work is done...(right?)

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

假设你有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³/6总共窗口数(计算多重性，您总共检查 w(i.j) 次 n-j 次)。即使忽略创建窗口并将其求和的成本，您也可以看到它的缩放效果如何:

• 对于N = 1000 ，有n = 168素数和大约 790000 个要检查的窗口(计算重数)。
• 对于N = 10**6 ，有n = 78498素数及约 8.3*10**13要检查的窗口。

现在考虑创建和求和窗口的工作，将其估计为 j-i+1。用于总结 j-i+1 w(i,j) 中的素数， p_k 的工作关于k³/6 ，总工作量大致变为 k**4/24 。 N = 1000 大约 3300 万步，花生，但差不多1.6*10**18对于 N = 1000000 .

一年大约包含3.1*10**7秒，对于 ~3GHz CPU，大约是 10¹⁷ 个时钟周期。因此，我们讨论的是需要大约 100 个 CPU 年的操作(可能是 10 倍左右)。

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

现在，通过内存，您仍然可以多次查看每个窗口，但只需对每个窗口进行一次计算。这意味着您需要大约 n³/6用于窗口的计算，并查看 n³/6任何窗口的时间。

• 问题1:你还需要查看windows 8.3*10**13有时，即使查找只需要一个周期，也要几个小时。
• 问题2:大约有8.3*10**13窗口来内存。您没有那么多内存，除非您可以使用非常的高清硬盘。

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

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

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