Python: speed up removal of every n-th element from list.
Posted
by ChristopheD
on Stack Overflow
See other posts from Stack Overflow
or by ChristopheD
Published on 2010-03-18T22:14:01Z
Indexed on
2010/03/18
22:31 UTC
Read the original article
Hit count: 550
I'm trying to solve this programming riddle and althought the solution (see code below) works correct, it is too slow for succesful submission.
- Any pointers as how to make this run faster? (removal of every n-th element from a list)?
- Or suggestions for a better algorithm to calculate the same; seems I can't think of anything else then brute-force for now...
Basically the task at hand is:
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 current code (it calculates the 3000 first lucky numbers in about a second on my machine - but 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]
© Stack Overflow or respective owner