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

Question

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

1. 与设定开始p = (2, 3, 4, ..., k)和i = 2.
2. 从开始i^2,删除的倍数i从p.
3. 重复下一个最小i的p,直到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)

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

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无序,我不知道如何(或者甚至可能)以更有效的方式获得下一个最小元素.我考虑过使用listwith True/ Falseflags作为素数,但你仍然需要list寻找下一个True元素.您不能只是实际从中删除元素list,因为这样就无法在步骤2中有效地删除复合数字.

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

Answer 1

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

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

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