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

关于如何解决这个问题的解释可以在这里找到。（我链接的这个问题要求更多，但它的主要步骤和你要解决的这个问题是一样的。）我链接的网站上还有一个用C++写的示例解决方案。

这些数字可以用一个二叉树来表示，这个树支持以下操作：

• 返回第 n 个元素
• 删除第 n 个元素

这些操作可以在 O(log n) 的时间内完成，其中 n 是树中节点的数量。

要构建这个树，你可以自己写一个程序，从给定的元素数组中构建树，或者实现一个插入操作（确保树是平衡的）。

树中的每个节点需要以下信息：

• 指向左子节点和右子节点的指针
• 左子树和右子树中有多少个元素

有了这样的结构，解决问题的其余部分应该就比较简单了。

我还建议在读取任何输入之前，先计算所有可能输入值的答案，而不是对每一行输入单独计算答案。

在你链接的网站上，上述算法的Java实现被接受的时间是0.68秒。

（抱歉没有提供任何Python方面的帮助，但希望上面提到的算法足够快。）

Answer 2

试试用这两行代码来删除和过滤，而不是你现在用的那种；filter(None, ...)的运行速度比filter(lambda ...)快很多。

sieve[::item] = [0]*-(-len(sieve)//item)
sieve = filter(None, sieve)

补充：直接用del sieve[::item]会更好；可以看看gnibbler的解决方案。

你可能还可以找到更好的条件来结束while循环：比如，如果筛子里第一个剩下的元素是i，那么筛子里的前i个元素就会变成下一个i个幸运数字；所以如果len(luckynumbers) + sieve[0] >= wanted_n，你应该已经算出你需要的数字了——你只需要找出它在sieve中的位置，这样就能提取出来。

在我的电脑上，你的内循环的这个版本比你原来的版本快了大约15倍，用来找到第3000个幸运数字：

while len(luckynumbers) + sieve[0] < wanted_n:
    item = sieve[0]
    luckynumbers.append(item)
    sieve[::item] = [0]*-(-len(sieve)//item)
    sieve = filter(None, sieve)
print (luckynumbers + sieve)[wanted_n-1]

Answer 3

这个系列被称为乐趣数字

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