带线程的python中的Eratosthenes筛选

Question

有没有可能在Python中编写一个包含线程的eratosthene筛选，以实现更快的输出？我见过很多用python编写的Eratosthene，但没有一个有线程。是不是因为GIL的缘故？你知道吗

Answer 1

如果您的sieve要处理大量的素数，这些素数足够大，需要将位图卸载到磁盘上，那么使用线程可能会变得非常重要。由于sieve的性质，线程之间可能会有很多争用，因为它们都希望更新相同的文件（至少最初是这样）。你知道吗

假设您使用位来表示筛子中标记数字的位置，并将其分解为8K文件（65536位），您找到的第一个素数在每个文件中都有更新的内容，因此并行性的好处将因文件访问冲突而丢失。一旦达到了大于65536的素数，冲突就会大大减少，线程也会开始带来一些好处。你知道吗

您仍然需要找到一种方法来防止控制进程（找到下一个符合条件的数字并启动线程）在线程的更新进程之前移动。你知道吗

更好的策略是使块大小等于前几个素数的乘积。这将允许文件的初始创建使用重复的相同位图，并且还将减少进程开始时的文件访问冲突。你知道吗

例如，如果块大小为2*3*5*7（210），则文件将包含210位，并且具有覆盖这4个因子的标记的可重复模式。i、 e.1..210的位与211..420、421..630等的位相同。当然，您可以使用更多的因子来获得有意义的文件大小。你知道吗