Python：加速从lis中删除第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 1

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

我的原始代码（它在我的机器上大约一秒钟内计算出3000个第一个幸运数字-可惜太慢了）：

^{pr2}$

编辑：感谢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]

所以循环变成了。在

^{pr2}$

不到0.1秒

Answer 2

关于如何解决这个问题的解释可以在here找到。（我链接的问题需要更多，但问题的主要步骤与你试图解决的问题相同））我连接的站点也包含了C++中的一个示例解决方案。在

数字集可以用二叉树表示，它支持以下操作：

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

这些操作可以实现为在O(log n)时间内运行，其中n是树中的节点数。在

要构建树，可以创建一个从给定元素数组构建树的自定义例程，也可以实现插入操作（确保树保持平衡）。在

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

• 指向左、右子对象的指针
• 左右子树中有多少项

有了这样的结构，解决剩下的问题应该相当简单。在

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

在您链接的网站上，上述算法的Java实现将在0.68秒内被接受。在

（很抱歉没有提供任何特定于Python的帮助，但希望上面概述的算法足够快。）

Answer 3

尝试使用这两行来删除和过滤，而不是使用现有的；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中，这样就可以提取它。在

在我的机器上，以下版本的内循环比原来的查找第3000个幸运数字的速度快15倍：

^{pr2}$