适用于非常大的质数的素数硬盘存储 - 阿特金筛选

Question

我已经实施了Atkin的Sieve,它的工作效果非常接近100,000,000左右.除此之外,它因内存问题而崩溃.

在算法中,我想用基于硬盘的阵列替换基于内存的阵列.Python的"wb"文件函数和Seek函数可以解决问题.在我发明新轮子之前,有人可以提供建议吗？一开始就出现两个问题:

1. 有没有办法将Atkin的Sieve"块"用于处理内存中的段,以及
2. 有没有办法暂停活动并稍后再回来 - 建议我可以序列化内存变量并恢复它们.

我为什么要这样做？寻找娱乐和保持面条工作的老geezer.

Answer 1

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

你真正想要的是分段筛.这允许您将内存使用限制到某个合理的限制(例如1M + O(sqrt(n)),如果需要可以减少后者).在primesieve.org上展示了一个很好的C++讨论和代码.您可以在Python中找到各种其他示例. 伯根斯坦实施SoA的primegen实施为分段筛(问题1:是的,SoA可以分段).这与筛选范围密切相关(但不完全相同).这就是我们如何使用筛子在几分之一秒内找到10 ^ 18和10 ^ 18 + 1e6之间的质数 - 我们当然不会将所有数字筛选到10 ^ 18 + 1e6.

涉及硬盘的是IMO,它的方向是错误的.我们应该能够比从驱动器中读取值更快地筛分(至少在良好的C实现中).远程和/或分段筛子应该做你需要的.

有更好的存储方式,这将有所帮助.我的SoE和其他几个一样,使用mod-30轮,因此每30个整数有8个候选,因此每30个值使用一个字节.看起来伯恩斯坦的SoA做了类似的事情,每60个值使用2个字节.RWH的python实现并不完全存在,但足够接近每30个值10位.不幸的是,看起来Python的本机bool数组每位使用大约10个字节,numpy是每位一个字节.你要么使用分段筛子而不要太担心它,要么找到一种在Python存储中更有效的方法.

Answer 2

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

如果您没有收到更好的答案，请提供一些提示。

1.有没有办法将阿特金筛“分块”以处理内存中的段

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

第一部分有点棘手，您要做的是以更排序的顺序处理4*x**2+y**2,3*x**2+y**2和。3*x**2-y**2一种方法是首先计算它们，然后对数字进行排序，有些排序算法在驱动器存储上运行良好（仍然是 O(N log N)），但这会损害时间复杂度。更好的方法是以一次在一个块上运行的方式迭代x和，因为块是由间隔确定的，例如您可以简单地迭代所有和 ，这样。yxylo <= 4*x**2+y**2 <= hi

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

为了实现这一点（无论程序如何以及何时终止），您必须首先对磁盘访问进行日志记录（fx 使用 SQL 数据库来保存数据，但您可以自己小心地完成）。

其次，由于第一部分中的操作不是幂等的，因此您必须确保不会重复这些操作。然而，由于您将逐块运行该部分，您可以简单地检测哪个是最后处理的块并在那里恢复（如果您最终可以得到部分处理的块，您只需丢弃该块并重做该块）。对于埃拉斯托梯尼部分，它是幂等的，因此您可以遍历所有内容，但为了提高速度，您可以在完成筛选后存储生成的素数列表（这样您就可以在最后生成的素数之后继续筛选）。

作为副产品，您甚至应该能够以某种方式构建程序，即使第二步正在运行，也可以保留第一步中的数据，从而在稍后通过继续第一步来扩展限制然后再次运行第二步。也许甚至有两个程序，当您厌倦了第一个程序时，您可以终止它，然后将其输出提供给埃拉托色尼部分（从而不必定义限制）。