代码之家 › 专栏 › 技术社区 › ChristopheD

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

algorithm performance python

ChristopheD · 技术社区 · 16 年前

我想解决这个问题 this programming riddle 尽管解决方案(参见下面的代码) 作品

有没有关于如何运行的指示
或建议一个更好的算法来计算相同的;我好像什么都想不出来除了暴力。。。

基本上,手头的任务是:

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]

编辑:感谢 马克·狄金森、史蒂夫·杰索普和格尼布勒的出色贡献,我在下面得到了,这比我最初的代码快了很多(并且成功地在 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]

5 回复 | 直到 16 年前

John La Rooy 16 年前

这个系列叫做 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秒

Mark Dickinson Alexandru 16 年前

试着用这两行来删除和过滤,而不是你所拥有的; filter(None, ...) 运行速度比 filter(lambda ...)

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

del sieve[::item] ; 参见gnibbler的解决方案。

i 然后是第一个筛子的元素将成为下一个 我 len(luckynumbers) + sieve[0] >= wanted_n sieve 这样你就可以提取出来。

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]

Anonym Mus 16 年前

here . (我链接的问题需要更多,但问题的主要步骤与你试图解决的问题相同。我链接的站点也包含了C++中的一个示例解决方案。

这组数字可以用二叉树表示,二叉树支持以下操作:

归还 n th元素
N th元素

这些操作可以在 O(log n) 时间,地点是树中的节点数。

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

左右子树中有多少项

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

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

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

Rex Kerr 16 年前

dan04 16 年前

为什么不创建一个新的列表呢?

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