非常大的素数存储的质数硬盘驱动器 - Atkin筛法

Question

我已经实现了 Atkin筛法，在接近100,000,000的素数以内它表现良好。但超过此范围就会因为内存问题而出错。

我想用硬盘替换基于内存的数组。Python的"wb"文件函数和Seek函数可能可以解决这个问题。在重新发明轮子之前，有人能提供建议吗？首先出现了两个问题:

1. 是否有一种方法将Atkin筛法分成内存中的段并运行，
2. 是否有一种方法可以暂停活动并稍后回来 - 这意味着我可以序列化内存变量并恢复它们。

为什么要这样做？一个为了娱乐和保持头脑活跃的老人。

- WyomingGeezer

---

无论存储问题如何，您都在“重新发明轮子”。顺便说一句，我不确定您是如何实现的，因为您没有提供代码，但是考虑到您想要检查所有小于max的数字，使用一个大小为(max-1)/24+1字节的数组就足够了。所以对于100,000,000来说，大约需要4MB的内存。 - barak manos

100M并不是很大，甚至不算“大”——9位数字根本算不了什么，例如常用的rsa密钥有100到1000位数字。这里有一个讨论100M位数字的问题的帖子。筛法算法在内存中的复杂度为O(sqrt(N))，即大约10KB足矣。问题在于你的具体实现。展示代码并询问如何改进其内存使用情况。 - jfs

一个快速搜索显示这个问题已经在SO上被问过（并得到了回答）。我是指关于分段的部分。 - Will Ness

我的问题已经得到了几个答案和一些好的评论，这足以让我在提出更多问题之前再回去剖析一下。由于每个答案似乎都涉及到我最初模糊的问题集的不同方面，因此很难选择任何一个答案作为“最佳答案”。作为一个新手，我要感谢所有回答我的人，并发布自己的答案，以关闭问题并让大家继续为更好的付费客户服务。 - WyomingGeezer

Answer 1

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

你真正需要的是分段筛法。这使得您可以将内存使用限制在合理的范围内（例如1M + O(sqrt(n))，如果需要，后者可以减小）。在primesieve.org中展示了C++中很好的讨论和代码。您可以在Python中找到各种其他示例。SoA的Bernstein实现primegen被实现为分段筛法（您的问题1：是的，SoA可以被分割）。这与筛选范围密切相关（但并非完全相同）。这就是我们如何使用筛法在一秒钟内找到10^18到10^18+1e6之间的质数 - 我们肯定不会筛选所有数字到10^18+1e6。

涉及硬盘，我认为，是走错了方向。我们应该能够比从驱动器读取值更快地筛选（至少使用良好的C实现）。范围和/或分段筛法应该可以满足您的需求。

有更好的存储方式可用，这将对一些人有所帮助。我的SoE和其他一些人一样，使用模30轮盘，因此每30个整数有8个候选项，因此每30个值使用一个字节。看起来Bernstein的SoA做了类似的事情，每60个值使用2个字节。RWH的Python实现还不够完美，但每30个值使用10位。不幸的是，Python的原生布尔数组每位使用约10个字节，而numpy每位使用1个字节。要么使用分段筛法并不过于担心，要么找到一种更有效的Python存储方式。

- DanaJ

Answer 2

首先，您应该确保以高效的方式存储数据。通过使用位图，您可以轻松地将数据存储在12.5Mb的内存中，可存储多达100,000,000个素数，通过跳过明显的非素数（偶数等），您可以使表示更加紧凑。这在将数据存储在硬盘上时也会有所帮助。当100,000,000个素数出现问题时，说明您没有有效地存储数据。

如果您没有得到更好的答案，则以下是一些提示。

引用：

1.有没有一种方法可以将Atkin筛法“分块”以在内存中工作

是的，对于类似于Eratosthenes部分，您可以运行筛选列表中的多个元素“并行”（一次一个块），从而最小化磁盘访问。

第一部分稍微麻烦一些，您想要做的是按更有序的方式处理4*x**2+y**2、3*x**2+y**2和3*x**2-y**2。一种方法是先计算它们，然后对数字进行排序，有一些在驱动器存储上效果很好的排序算法（仍然是O（N log N）），但这会降低时间复杂度。更好的方法是以一段为单位遍历 x 和 y，因为一个块由一个区间确定，所以您可以简单地遍历所有 lo <= 4*x**2+y**2 <= hi 的x和y。

2.有没有一种暂停活动并稍后回来的方法-建议我可以序列化内存变量并恢复它们

为了实现这一点（无论程序何时何地被终止），您首先必须记录磁盘访问（例如使用SQL数据库来保留数据，但是请小心，您也可以自己做到这一点）。

其次，由于第一部分中的操作不是不变的，因此您必须确保不要重复执行这些操作。然而，由于您将逐块运行该部分，因此您只需检测最后处理的块即可恢复工作（如果最终出现部分处理的块，则会丢弃该块并重新进行处理）。对于Eratosthenes部分，它是不变的，因此您可以全部运行，但是为了提高速度，您可以在筛选完它们之后存储已生成的素数列表（因此您将在最后产生的素数之后继续筛选）。

作为副产品，您甚至应该能够以一种方式构建程序，使得在第二步运行时仍然可以保留第一步的数据，并因此在稍后的时间通过继续第一步然后再次运行第二步来扩展限制。也许甚至有两个程序，当您对第一个程序感到厌倦时终止它，然后将其输出馈送到Eratosthenes部分（从而无需定义限制）。

- skyking

Answer 3

你可以尝试使用一个信号处理程序来捕获应用程序终止的时刻。这样可以在终止之前保存当前状态。下面的脚本展示了当重新启动时简单数字计数器的继续计数。

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处理器也应确保您的文件被刷新和关闭。

- Martin Evans

---

请注意，这种解决方案及类似解决方案无法处理程序以软件无法拦截的方式终止的情况，例如停电将无法处理。 - skyking

Answer 4

有一种方法可以压缩数组。根据Python解释器的效率，它可能会花费一些效率，但您将能够在不必使用磁盘的情况下在内存中存储更多内容。如果您搜索在线，您可能会发现其他使用压缩的筛法实现。

虽然可以忽略压缩，但将内存持久化到磁盘的较简单的方法之一是通过内存映射文件。 Python具有提供此功能的mmap模块。 您需要对原始字节进行编码和解码，但是使用struct模块相当简单。

>>> import struct
>>> struct.pack('H', 0xcafe)
b'\xfe\xca'
>>> struct.unpack('H', b'\xfe\xca')
(51966,)

- Jason