python - 检索 Python 集合的下一个最小元素

Question

Sieve of Eratosthenes是一种相当快的生成素数的方法，它可以达到 k 的极限，如下所示:

1. 从集合 p = (2, 3, 4, ..., k) 和 i = 2 开始。
2. 从i^2开始，从p中移除所有i的倍数。
3. 重复 p 中下一个最小的 i，直到 i >= sqrt(k)。

我当前的实现看起来像这样(具有明显的预过滤所有偶数的优化):

# Compute all prime numbers less than k using the Sieve of Eratosthenes
def sieve(k):
    s = set(range(3, k, 2))
    s.add(2)

    for i in range(3, int(sqrt(k)), 2):
        if i in s:
            for j in range(i ** 2, k, i * 2):
                s.discard(j)

    return sorted(s)

编辑:这是等效的基于列表的代码:

def sieve_list(k):
    s = [True] * k
    s[0] = s[1] = False
    for i in range(4, k, 2):
        s[i] = False

    for i in range(3, int(sqrt(k)) + 2, 2):
        if s[i]:            
            for j in range(i ** 2, k, i * 2):
                s[j] = False

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

这行得通，但并不完全正确。行:

for i in range(3, int(sqrt(k)), 2):
    if i in s:
        [...]

通过测试每个奇数的集合成员资格来找到 s 的下一个最小元素。理想情况下，实现实际上应该是:

while i < sqrt(k):
    [...]
    i = next smallest element in s

但是，由于 set 是无序的，我不知道如何(或者即使可能)以更有效的方式获取下一个最小元素。我考虑过使用带有 True/False 标记的 list 素数，但您仍然必须遍历 list寻找下一个 True 元素。您也不能直接从 list 中删除元素，因为这使得在第 2 步中有效删除合数变得不可能。

有没有办法更有效地找到下一个最小的元素？如果不是，是否有其他数据结构允许按值删除 O(1) 以及找到下一个最小元素的有效方法？

Answer 1

集合是无序的，因为它们在内部实现为哈希集。没有找到这种数据结构中最小元素的有效方法； min(s) 将是最 Pythonic 的方式来做到这一点(但它是 O(n))。

您可以使用collections.deque 连同您的集合。使用 deque 以排序的顺序存储元素列表。每次您需要获取最小值时，从 deque 中弹出元素，直到找到集合中的元素。这在整个输入数组中分摊了 O(1) 成本(因为您只需要弹出 n 次)。

我还应该指出，没有数据结构可以从列表创建 O(n)(或 O(1) 插入)，O(1) 按值删除和 O (1) 最小值查找；这样的数据结构可用于简单地实现 O(n) 通用排序，这是(信息论)不可能的。哈希集非常接近，但必须牺牲高效的最小值查找。