Python generator 和 set(generator) 得到不同的结果

Question

我有如下代码

def yield_multiple():
    for prime in prime_list:
        for multiple in range(prime+prime, end, prime):
            yield multiple

我用它来得到素数

multiple_set = set(yield_multiple())
result = [v for v in candidate_list if v not in multiple_set]

而且我在set很大的时候遇到内存错误，所以我想用这个来节省内存

result = [v for v in candidate_list if v not in yield_multiple()]

但是这样会得到错误的结果。那么，如何避免内存错误以正确获取质数呢？

这是我改进的解决方案，没有太多内存可供使用。

import math
import sys

import time
from mpi4py import MPI

import eratosthenes

comm = MPI.COMM_WORLD
rank = comm.Get_rank()
size = comm.Get_size()

TAG_RESULT = 0

n = sys.argv[1]
if n.isdigit():
    start_time = time.time()
    n = int(n)
    sqrt_n = int(math.sqrt(n))

    task_per_block = int(math.ceil((n - 1) / size))
    begin = 2 + rank * task_per_block
    end = begin + task_per_block if begin + task_per_block <= n + 1 else n + 1
    if rank == 0:
        begin = sqrt_n if sqrt_n < end else begin
    sieve_list = [True] * (end - begin)
    prime_list = eratosthenes.sieve(sqrt_n)

    if rank == 0:
        result = sum(prime_list)
        for prime in prime_list:
            start = begin if begin % prime == 0 else (int(begin / prime) + 1) * prime
            for multiple in range(start, end, prime):
                sieve_list[multiple - begin] = False
        result += sum(i + begin for i, v in enumerate(sieve_list) if v)
        result_received = 0
        while result_received < size - 1:
            data = comm.recv(source=MPI.ANY_SOURCE, tag=TAG_RESULT)
            result += data
            result_received += 1
        print(result)
        print(time.time() - start_time)
    else:
        for prime in prime_list:
            start = begin if begin % prime == 0 else (int(begin / prime) + 1) * prime
            for multiple in range(start, end, prime):
                sieve_list[multiple - begin] = False
        result = sum(i + begin for i, v in enumerate(sieve_list) if v)
        comm.send(result, dest=0, tag=TAG_RESULT)

Answer 1

如果你想继续使用这种方法——它确实有一定的简单性，尽管它肯定非常低效——这是我能看到的最简单的方法，不需要构造一个大的集合或 re-running yield_multiple 对于每个候选人来说，就是要反转你的会员资格检查：

multiples = {c for c in yield_multiple() if c in candidate_list}
result = [c for c in candidate_list if c not in multiples]

但是，除非使用您自己的代码是这里最重要的因素，否则我建议您寻找一种更有效的方法，例如 in this other answer.

中描述的方法

Answer 2

通过切换到按连续素数的正方形之间的线段工作，为每个线段一个接一个地创建这些集合。

对于每个段，您必须计算素数倍数枚举的起点，对于每个不大于该段最高值的已知素数（即下一个 "core"素数的平方).

"core"素数，要得到的平方，你可以分别独立地通过相同算法的递归应用得到。

这种方法的一个例子（即单独的素数供应）是How to implement an efficient infinite generator of prime numbers in Python?

要使其并行，您需要找到在所有枚举之间以共享方式使用集合的方法，每个枚举都会设置其枚举倍数off 在同一共享集中。操作顺序并不重要，只要它们都完成即可。不需要保护访问，因为将相同的位置 off 设置两次（或更多）完全没问题。

这样效率也会很高

Python generator 和 set(generator) 得到不同的结果

Python generator and set(generator) get different results

python

parallel-processing

concurrency

primes

sieve-of-eratosthenes