Python: speed up removal of every n-th element from list

algorithm, performance, python

Solution

This series is called ludic numbers

`__delslice__` should be faster than `__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]

So the loop becomes.

while len(luckynumbers) < 3000:
    item = sieve[0]
    luckynumbers.append(item)
    del sieve[::item]

Which runs in less than 0.1 second

Problem

I'm trying to solve this programming riddle and although the solution (see code below) works correctly, 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 than 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 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] ``` EDIT: thanks to the terrific contributions of Mark Dickinson, Steve Jessop and gnibbler, I got at the following, which is quite a whole lot faster than my original code (and succesfully got submitted at http://www.spoj.pl with 0.58 seconds!)... ``` 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] ```

Original source