滑动窗口和备忘录的计算 - python

我正在研究Euler问题50,该问题指出:

质数41可以写为六个连续质数之和:

41 = 2 + 3 + 5 + 7 + 11 + 13
这是连续质数的最长总和,加成小于一百的质数。

小于一千的连续质数的最长总和加一个质数,包含21个项,等于953。

小于一百万的素数可以写为最连续的素数之和?

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

这对于所有不超过1000的素数都可以正常工作,但是对于不超过10 ** 6的素数,它非常慢,因此我希望记忆可以有所帮助。在计算滑动窗口的总和时,做了很多双重工作...(对吗?)

因此,我在网上找到了标准的记忆实现并将其粘贴到我的代码中,对吗? (我不知道应该如何在这里工作...)

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

参考方案

这对于所有不超过1000的素数都可以正常工作,但是对于不超过10 ** 6的素数,它非常慢,因此我希望记忆可以有所帮助。在计算滑动窗口的总和时,做了很多双重工作...(对吗?)

是的,对。当然,灌注至106的速度很慢。

假设您有n个素数最多为N,并按升序编号p_1 = 2, p_2 = 3, ...。在考虑是否素数时。 k是连续质数的总和,对于[p_i, ..., p_j](i,j)对,您考虑所有窗口i < j < k。其中有(k-1)*(k-2)/2个。从所有kn,您总共检查了大约n³/6个窗口(计数重复性,您总共检查了w(i.j)次)。即使忽略创建窗口并对其求和的成本,您也可以看到它的缩放比例很差:

对于n-j,有N = 1000个质数和大约790000个窗口要检查(计数多重性)。
对于n = 168,有N = 10**6个质数和大约n = 78498个窗口要检查。

现在将创建和求和窗口的工作考虑在内,将8.3*10**13中的j-i+1质数求和的值估计为j-i+1低,w(i,j)的工作大约为p_k,总工作量大致为。花生k³/6大约为3,300万步,而k**4/24几乎为N = 1000

一年大约包含1.6*10**18秒,使用约3GHz的CPU,大约是1017个时钟周期。因此,我们所说的一项操作需要大约100个CPU年(可能会减少10倍左右)。

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

现在,有了备忘录,您仍然可以多次查看每个窗口,但是每个窗口只计算一次。这意味着您需要大约N = 1000000的工作来计算窗口,并在任何窗口中查看3.1*10**7次。

问题1:您仍然需要查看n³/6次窗口,即使仅花费一个周期,也要花费几个小时。
问题2:有大约n³/6个窗口可用于记忆。您没有那么多的内存,除非可以使用非常大的HD。

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

小于一千的连续质数的最长总和加一个质数,包含21个项,等于953。

这对窗口产生该金额有什么启示?它在哪里开始,在哪里停止?您如何使用这些信息来创建有效的算法来解决问题?

Python GPU资源利用 - python

我有一个Python脚本在某些深度学习模型上运行推理。有什么办法可以找出GPU资源的利用率水平?例如,使用着色器,float16乘法器等。我似乎在网上找不到太多有关这些GPU资源的文档。谢谢! 参考方案 您可以尝试在像Renderdoc这样的GPU分析器中运行pyxthon应用程序。它将分析您的跑步情况。您将能够获得有关已使用资源,已用缓冲区,不同渲染状态上…

Python sqlite3数据库已锁定 - python

我在Windows上使用Python 3和sqlite3。我正在开发一个使用数据库存储联系人的小型应用程序。我注意到,如果应用程序被强制关闭(通过错误或通过任务管理器结束),则会收到sqlite3错误(sqlite3.OperationalError:数据库已锁定)。我想这是因为在应用程序关闭之前,我没有正确关闭数据库连接。我已经试过了: connectio…

python-docx应该在空单元格已满时返回空单元格 - python

我试图遍历文档中的所有表并从中提取文本。作为中间步骤,我只是尝试将文本打印到控制台。我在类似的帖子中已经看过scanny提供的其他代码,但是由于某种原因,它并没有提供我正在解析的文档的预期输出可以在https://www.ontario.ca/laws/regulation/140300中找到该文档from docx import Document from…

Python ThreadPoolExecutor抑制异常 - python

from concurrent.futures import ThreadPoolExecutor, wait, ALL_COMPLETED def div_zero(x): print('In div_zero') return x / 0 with ThreadPoolExecutor(max_workers=4) as execut…

Python:集群作业管理 - python

我在具有两个阶段的计算群集(Slurm)上运行python脚本,它们是顺序的。我编写了两个python脚本,一个用于阶段1,另一个用于阶段2。每天早上,我检查所有第1阶段的工作是否都以视觉方式完成。只有这样,我才开始第二阶段。通过在单个python脚本中组合所有阶段和作业管理,是否有一种更优雅/自动化的方法?我如何知道工作是否完成?工作流程类似于以下内容:w…