滑动窗口计算和备忘录技术

Question

滑动窗口计算和备忘录技术

pythonprimesmemoization

5

我正在解决欧拉计划（Project Euler）第50个问题，它陈述如下：

质数41可以表示为6个连续质数之和: 41 = 2 + 3 + 5 + 7 + 11 + 13 这是在小于100的质数中，加起来是质数且连续的质数之和最长的。

小于1000的质数中，加起来是质数且连续的质数之和最长的包含21个质数的和，并等于953。

在小于一百万的质数中，哪个质数能够被表示成连续质数之和的形式，而且能表示出的连续质数个数最多？

为了确定质数P是否可以表示为质数之和，我使用从第一个质数开始到（但不包括）P的所有质数的滑动窗口，计算所有这些窗口的总和，如果总和等于所考虑的质数，则计算窗口长度...

这对于小于1000的所有质数都很好用，但对于小于10 ** 6的质数来说速度非常慢，因此我希望使用“记忆化（memozation）”，当计算滑动窗口的总和时，会有很多重复的工作...(对吗?)

因此，我在网上找到了标准的记忆化实现方法，只是把它粘贴到我的代码中，这样做正确吗？（我不知道它在这里应该如何工作...）

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

- luffe

抱歉，它可以工作，缩进错误是由于Stackoverflow的“代码”输入模式造成的。我现在会修复它。 - luffe

抱歉，代码输入过程完全让我困惑，这里提供了带有正确缩进的代码链接： http://pastebin.com/R1NpMqgb - luffe

2个回答

1

memoize装饰器为函数添加了一个包装器，以缓存每个参数值的返回值（多个参数的情况下是每个值组合）。当使用相同参数多次调用函数时，它非常有用。您只能将其与纯函数一起使用，即：

该函数没有副作用。更改全局变量和进行输出是副作用的示例。
返回值仅取决于参数的值，而不是某些可能在调用之间更改值的全局变量。

您的find_lin_comb函数不满足上述标准。首先，它每次都使用不同的参数调用，另外，该函数不返回任何值。

- Janne Karila

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

这对于所有小于1000的质数都很好，但是对于小于10^6的质数来说非常慢，所以我希望使用记忆化可以帮助; 在计算滑动窗口的总和时，会进行大量的重复工作...(对吗？)

是的，没错。当然对于小于10^6的质数它是慢的。

假设你有n个小于N的质数，按递增顺序编号，p1=2，p2=3，……。在考虑第k个质数是否为连续质数之和时，你要考虑所有窗口[p_i, ..., p_j]，对于i < j < k的一对(i,j)。共有(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个窗口。

现在加上创建和求和窗口的工作量，低估w(i.j)求和j-i+1的成本，p_k的工作量约为k³/6，则总工作量大致为k^4/24。对于N = 1000，约需要3300万步，微不足道，但对于N = 1000000，几乎需要1.6*10^18步。

一年包含约3.1*10^7秒，使用~3GHz的CPU，大约需要10^17个时钟周期。因此，我们正在谈论需要大约100个CPU年的操作（可能会偏差10倍左右）。

我想你不愿意等那么长时间吧;)

现在，通过记忆化，您仍然多次查看每个窗口，但是只计算每个窗口一次。这意味着您需要约n³/6的计算窗口的工作量，并且每个窗口需要查看约n³/6次。

问题1：你仍然需要查看大约8.3*10**13次窗口，即使每次查看只花费一个周期，也需要几个小时。
问题2：需要存储约8.3*10**13个窗口的数据。除非使用一块真正大的硬盘，否则内存不足。

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

最长的一千以下连续素数之和为质数的总和包含21项，等于953。

这告诉您有关生成该总和的窗口的信息。它可以从哪里开始，可以停止在哪里？您如何使用此信息创建有效的算法以解决问题？