10

我已经实施了阿特金筛法，它在质数接近 100,000,000 左右时效果很好。除此之外，它会因为内存问题而崩溃。

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

  1. 有没有办法“分块”阿特金的筛子来处理内存中的片段，以及
  2. 有没有办法暂停活动并稍后再回来 - 建议我可以序列化内存变量并恢复它们。

我为什么要这样做？一个寻找娱乐和保持面条工作的老家伙。

4

4 回答 4

5

用 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 个值使用一个字节。看起来 Bernstein 的 SoA 做了类似的事情，每 60 个值使用 2 个字节。RWH 的 python 实现并不完全存在，但在每 30 个值 10 位时足够接近。不幸的是，看起来 Python 的原生 bool 数组每比特使用大约 10 个字节，而 numpy 是每比特一个字节。要么你使用分段筛，不要太担心它，要么找到一种在 Python 存储中更高效的方法。

于 2015-08-21T12:10:37.427 回答
3

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

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

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

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

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

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

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

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

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

于 2015-08-21T05:40:29.673 回答
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处理程序还应确保您的文件被刷新和关闭。

于 2015-08-21T06:42:40.220 回答
0

有一种方法可以压缩数组。根据 python 解释器的不同，它可能会花费一些效率，但是在不得不求助于磁盘之前，您可以在内存中保留更多。如果您在线搜索，您可能会发现其他使用压缩的筛子实现。

尽管忽略压缩，将内存持久保存到磁盘的更简单方法之一是通过内存映射文件。Python 有一个提供该功能的mmap模块。您必须对原始字节进行编码，但使用struct模块相当简单。

>>> import struct
>>> struct.pack('H', 0xcafe)
b'\xfe\xca'
>>> struct.unpack('H', b'\xfe\xca')
(51966,)
于 2015-08-21T07:08:30.043 回答