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

Question

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

8

我正在尝试解决这个编程谜题，虽然下面的代码可以正确工作，但对于成功提交来说太慢了。

有什么指针可以使它运行得更快（从列表中删除每个第n个元素）？
或者有计算相同内容的更好算法的建议；似乎我现在只能想到暴力算法……

基本上，手头的任务是：

给定：
L = [2,3,4,5,6,7,8,9,10,11,........]
1. 在列表L中取第一个剩余项（在一般情况下为'n'）。将其移动到“幸运数字列表”中。然后从列表中删除每个'n-th'项。
2. 重复步骤1
任务：
计算“幸运数字列表”的第n个数字（1 ≤ n ≤ 3000）

我的原始代码（它在我的机器上大约计算了3000个幸运数字需要1秒钟 - 不幸的是太慢了）：

"""
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]

- ChristopheD

问题不就是要求你生成第n个质数吗？ - rz.

@Rex Kerr。你没有注意到一个微妙的变化。“然后从列表中删除每一个第'n'个项目”意味着从当前L中删除，而不是从原始L中删除。http://en.wikipedia.org/wiki/Lucky_number - Steve Jessop

@Steve Jessop：看到 50,000 字节限制，我笑出声了；-) - ChristopheD

1

这些与幸运数字类似，但算法略有不同。Ulam将他的算法应用于自然数；而这个版本从2开始，而不是1。 - Robert Rossney

@gnibbler：啊，我只是有一瞬间的词序障碍。不知怎么地，我把标签读成了“lucid-numbers”，以为它是“lucky-numbers”的拼写错误 :) - Anonym Mus

显示剩余10条评论

5个回答

4

尝试使用以下两行代码进行删除和过滤，而不是您现有的代码; 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倍：

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]

- Mark Dickinson

哇，这两行代码的运行速度比我上面的两行快了大约10倍。非常有见地！让我试一下while循环... - ChristopheD

或者是 for x in xrange(0, len(sieve), item): sieve[x] = 0。 - Steve Jessop

由于需要对多个n的值输出lucky(n)，因此计算一次数组（最多到3000）比为每个所需的值从头开始计算更有意义。因此，可能不值得过多担心提前终止。 - Steve Jessop

嗯。如果仍然失败，那么要么SPOJ机器比我们所有人都慢几倍，要么他们要求输入的数量非常大。后者似乎有点不公平，因为问题肯定是关于幸运数字计算的，而不是关于优化I/O的。个人认为此时应该认真考虑对SPOJ进行基准测试-不输出任何内容，只需执行一些循环多次。二分查找以找出SPOJ在1秒内可以执行多少次。与您的机器进行比较。如果您的速度慢了100倍，那么您只是在浪费时间调整。 - Steve Jessop

1

@ChristopheD：我觉得我不公正地诋毁了Mark的早期终止想法。在循环的第一行后添加if len(sieve) < item: luckynumbers.extend(sieve); break，可以在我的机器上计算前3000个数字时提高3倍的速度。抱歉，Mark。 - Steve Jessop

显示剩余3条评论

2

这个问题的解决方法可以在这里找到。（我链接的问题要求更多，但是那个问题的主要步骤与您正在尝试解决的问题相同。）我链接的网站还包含一个C++的样例解决方案。

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

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

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

要构建树，您可以编写一个自定义程序，从给定的元素数组构建树，或者实现一个插入操作（请确保保持树平衡）。

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

- 指向左右子节点的指针 - 左右子树中有多少项

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

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

上述算法的Java实现在您提供的网站上被接受，用时0.68秒。

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

- Anonym Mus

@stubbscroll：非常感谢您提供这个非常好的答案！我会在这个周末尝试实现它（现在已经很晚了），并告诉您进展如何。 - ChristopheD

1

最好使用数组，并使用该策略将每第N个项目清零；在连续几次执行此操作后，更新开始变得棘手，因此您需要重新组合数组。这应该可以将速度提高至少10倍。您需要比这更好的吗？

- Rex Kerr

有趣的建议，谢谢。我会尝试一下并回报结果！ - ChristopheD

0

为什么不直接创建一个新列表呢？

L = [x for (i, x) in enumerate(L) if i % n]

- dan04

嗨dan04：我刚刚进行了基本测试，但这个解决方案大约比当前的解决方案慢200倍（从gnibbler，Mark Dickinson，Steve Jessop的答案收集而来）... - ChristopheD

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John La Rooy · Accepted Answer

这个系列被称为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秒内运行