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

Filed under:
|
|

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

Related posts about python

Related posts about Performance