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

Question

我正在尝试解决这个编程问题,虽然解决方案(见下面的代码)工作正常,但成功提交的速度太慢了.

• 有关如何使其运行更快的任何指针(从列表中删除每个第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 1

TASK:
Calculate the n-th number from the 'lucky number list' ( 1 <= n <= 3000)

我的原始代码(它在我的机器上计算了大约一秒钟内的3000个第一个幸运数字 - 不幸的是太慢了):

"""
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数字

__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秒