阿特金超大素数筛的素数硬盘存储

Question

我已经实现了Sieve of Atkin，它在接近100000000的素数下工作得很好。除此之外，它会因为记忆问题而崩溃。在

在算法中，我想用基于硬盘驱动器的数组替换基于内存的数组。Python的“wb”文件函数和Seek函数可以做到这一点。在我开始发明新轮子之前，有人能给我些建议吗？一开始就出现了两个问题：

1. 有没有一种方法可以“大块”Atkin的筛子来处理内存中的段
2. 有没有一种方法可以挂起活动，然后再回来——建议我可以序列化内存变量并恢复它们。

我为什么要这么做？一个老古董，想找点乐子，让面条继续工作。在

Answer 1

您可以尝试使用signal处理程序在应用程序终止时捕获。这样可以在终止前保存当前状态。下面的脚本显示了在重新启动时继续进行的简单的数字计数。在

import signal, os, cPickle

class MyState:
    def __init__(self):
        self.count = 1

def stop_handler(signum, frame):
    global running
    running = False

signal.signal(signal.SIGINT, stop_handler)
running = True
state_filename = "state.txt"

if os.path.isfile(state_filename):
    with open(state_filename, "rb") as f_state:
        my_state = cPickle.load(f_state)
else:
    my_state = MyState()

while running:
    print my_state.count
    my_state.count += 1

with open(state_filename, "wb") as f_state:
    cPickle.dump(my_state, f_state)

至于改进磁盘写入，您可以尝试使用1Mb或更大大小的缓冲区来增加Python自己的文件缓冲区，例如open('output.txt', 'w', 2**20)。使用with处理程序还应确保文件被刷新并关闭。在

Answer 2

用Python实现SoA听起来很有趣，但请注意，实际上它可能比SoE慢。对于一些好的单片SoE实现，请参见RWH's StackOverflow post。这些可以让您了解一些非常基本的实现的速度和内存使用情况。numpy版本将在我的笔记本电脑上过滤到10000米以上。在

你真正想要的是一个分段筛子。这使您可以将内存使用限制在某个合理的限制（例如1M+O（sqrt（n）），如果需要，可以减少后者）。在primesieve.org中显示了C++中的一个很好的讨论和代码。您可以在Python中找到其他各种示例。^{

在我看来，涉及到硬盘驱动器是走错了方向。我们应该能够比从驱动器中读取值更快地进行筛选（至少在良好的C实现中）。一个远程和/或分段筛子应该能满足你的需要。在

有更好的方法来做存储，这将帮助一些人。我的SoE和其他一些SoE一样，使用mod-30轮子，因此每30个整数有8个候选，因此每30个值使用一个字节。看起来Bernstein的SoA也做了类似的事情，每60个值使用2个字节。RWH的python实现并不是很好，但是在每30个值中有10位的情况下已经足够接近了。不幸的是，Python的本机bool数组每位使用10个字节，numpy是每位一个字节。要么使用分段筛选，不必太担心，要么在Python存储中找到一种更高效的方法。在

Answer 3

首先，您应该确保以高效的方式存储数据。通过使用位图，您可以轻松地将多达100000000个素数的数据存储在12.5Mb内存中，通过跳过明显的非素数（偶数等），您可以使表示更加紧凑。这也有助于在硬盘上存储数据。当你在100000000个素数时遇到麻烦，说明你没有有效地存储数据。在

如果你没有得到更好的答案，有些提示。在

1.Is there a way to "chunk" the Sieve of Atkin to work on segment in memory

是的，对于类似eratothenes的部分，您可以做的是在“parallel”（一次一个块）中运行筛选列表中的多个元素，这样就可以最大限度地减少磁盘访问。在

第一部分比较棘手，您需要做的是以更有序的顺序处理4*x**2+y**2、3*x**2+y**2和{}。一种方法是先计算它们，然后对数字进行排序，有一些排序算法在驱动器存储（仍然是O（N logn））上运行良好，但这会降低时间复杂性。一个更好的方法是迭代x和{}，因为一个块是由一个间隔决定的，你可以简单地迭代所有x和{}，这样{}。在

2.is there a way to suspend the activity and come back to it later - suggesting I could serialize the memory variables and restore them

为了实现这一点（无论程序以何种方式和何时终止），您必须首先对磁盘进行日志记录访问（fx使用SQL数据库保存数据，但您可以谨慎地自己执行）。在

第二，由于第一部分中的操作不是独立的，所以必须确保不要重复这些操作。然而，由于您将运行的部分块一个块，您可以简单地检测哪个块是最后一个处理的块，并在那里继续（如果您可以结束部分处理的块，您只需丢弃它并重新执行该块）。对于Erastothenes部分，它是独立的，所以你可以运行所有它，但是为了提高速度，你可以在筛选完它们之后存储一个生成的素数列表（这样你可以在最后一个生成的素数之后继续进行筛选）。在

作为一个副产品，你甚至应该能够以一种方式构造程序，使得即使在第二步运行的情况下也能保留第一步中的数据，从而在以后通过继续第一步，然后再次运行第二步来扩展限制。甚至可能有两个程序，当你厌倦了第一个程序，然后把它的输出输入到Eratosthenes部分（因此不必定义限制）。在