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

Sieve of Eratosthenes是一种相当快速的生成素数的方法,如下所示：

>从集合p =(2,3,4,…,k)开始,i = 2.
>从i ^ 2开始,从p中删除i的所有倍数.
>对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标志的列表进行素数处理,但你仍然需要遍历列表寻找下一个True元素.您不仅可以实际从列表中删除元素,因为这样就无法在步骤2中有效地删除复合数字.

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

集合是无序的,因为它们在内部实现为散列集.找不到这种数据结构中的最小元素是没有效率的方法; min(s)将是最恐怖的方式(但它是O(n)).

您可以将collections.deque与您的集合一起使用.使用deque按排序顺序存储元素列表.每当你需要获得最小值时,可以在双端队列中弹出元素,直到找到集合中的元素.这会在整个输入数组中分摊O(1)成本(因为您只需要弹出n次).

我还应该指出,没有数据结构可以从列表(或O(1)插入)中创建O(n),按值删除O(1)和O(1)最小值查找;这样的数据结构可以用于简单地实现O(n)一般排序,这是(信息理论上)不可能的. hashset非常接近,但必须牺牲有效的最小值.