Python:加速从列表中删除每个第 n 个元素

Question

我正在尝试解决 this programming riddle，虽然解决方案(参见下面的代码)工作正确，但它对于成功提交来说太慢了。

• 关于如何运行的任何指示更快(从列表中删除每个第 n 个元素)？
• 或有关计算相同算法的更好算法的建议；似乎我想不出什么除了现在的蛮力...

基本上，手头的任务是:

GIVEN:L = [2,3,4,5,6,7,8,9,10,11,........]1. Take the first remaining item in list L (in the general case 'n'). Move it to    the 'lucky number list'. Then drop every 'n-th' item from the list.2. Repeat 1TASK:Calculate the n-th number from the 'lucky number list' ( 1 <= n <= 3000)

My original code (it calculated the 3000 first lucky numbers in about a second on my machine - unfortunately too slow):

"""
SPOJ Problem Set (classical) 1798. Assistance Required
URL: http://www.spoj.pl/problems/ASSIST/
"""

sieve = range(3, 33900, 2)
luckynumbers = [2]

while True:
    wanted_n = input()
    if wanted_n == 0:
        break

    while len(luckynumbers) < wanted_n:
        item = sieve[0]
        luckynumbers.append(item)
        items_to_delete = set(sieve[::item])
        sieve = filter(lambda x: x not in items_to_delete, sieve)
    print luckynumbers[wanted_n-1]

编辑:感谢 Mark Dickinson、Steve Jessop 和 gnibbler 的出色贡献，我得到了以下结果，这比我的原始代码快了很多(并在 http://www.spoj.pl 成功提交)用了 0.58 秒!)...

sieve = range(3, 33810, 2)
luckynumbers = [2]

while len(luckynumbers) < 3000:
    if len(sieve) < sieve[0]:
        luckynumbers.extend(sieve)
        break
    luckynumbers.append(sieve[0])
    del sieve[::sieve[0]]

while True:
    wanted_n = input()
    if wanted_n == 0:
        break
    else:
        print luckynumbers[wanted_n-1]

Answer 1

这个系列叫做 ludic numbers

__delslice__ 应该比 __setslice__+filter

更快

>>> L=[2,3,4,5,6,7,8,9,10,11,12]
>>> lucky=[]
>>> lucky.append(L[0])
>>> del L[::L[0]]
>>> L
[3, 5, 7, 9, 11]
>>> lucky.append(L[0])
>>> del L[::L[0]]
>>> L
[5, 7, 11]

这样循环就变成了。

while len(luckynumbers) < 3000:
    item = sieve[0]
    luckynumbers.append(item)
    del sieve[::item] 

运行不到 0.1 秒