我正在尝试解决 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)
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]
最佳答案
这个系列叫做 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 秒
关于Python:加速从列表中删除每个第 n 个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2473710/