Python: acelerar la eliminación de cada elemento n-ésimo de la lista

Question

Estoy tratando de resolver y aunque la solución (ver código a continuación) funciona correctamente, es demasiado lento para la presentación exitosa.

• Cualquier punteros como la forma de hacer esta carrera más rápido (eliminación de todos los elementos de orden n de una lista)?
• O sugerencias para un mejor algoritmo para calcular el mismo; Parece que no puedo pensar en nada más que de fuerza bruta por ahora ...

Básicamente, la tarea actual es:

 
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) 

Mi código original (se calcula la primera suerte 3000 números en alrededor de un segundo en mi máquina - por desgracia demasiado lento):

""" 
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: gracias a las contribuciones terribles de Mark Dickinson, Steve Jessop y gnibbler, me conseguido en el siguiente, lo cual es bastante mucho más rápido que mi código original (y con éxito consiguió presentado en http://www.spoj.pl con 0.58 segundos!) ...

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] 

Answer 1

Esta serie se llama ludic numbers

__delslice__ debe ser más rápido que __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] 

Así se convierte en el bucle.

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

que se ejecuta en menos de 0,1 segundos

Answer 2

Es mejor utilizar una matriz y poniendo a cero todos Enésimo elemento usando esa estrategia; después de hacer esto varias veces seguidas, las actualizaciones comienzan a complicarse, por lo que querrá volver a formar la matriz. Esto debería mejorar la velocidad por al menos un factor de 10. ¿Necesita mucho más que eso?

Answer 3

Intente utilizar estas dos líneas para eliminar y filtrar, en lugar de lo que tiene; filter(None, ...) se ejecuta considerablemente más rápido que el filter(lambda ...).

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

Editar: mucho mejor simplemente use del sieve[::item]; ver la solución de gnibbler.

También podría ser capaz de encontrar una condición de terminación mejor para el bucle while: por ejemplo, si el primer elemento que queda en el tamiz es i entonces los primeros i elementos del tamiz se convertirán en los próximos i números de la suerte; así que si len(luckynumbers) + sieve[0] >= wanted_n ya debe haber calculado el número que necesita --- solo necesita averiguar dónde en sieve es para que pueda extraerlo.

En mi máquina, la siguiente versión de su bucle interno corre alrededor de 15 veces más rápido que el original para encontrar el número de la suerte 3000a:

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] 

Answer 4

Una explicación sobre cómo resolver este problema se puede encontrar here. (El problema al que me he vinculado solicita más, pero el paso principal en ese problema es el mismo que está tratando de resolver). El sitio al que me he vinculado también contiene una solución de muestra en C++.

El conjunto de números se puede representar en un árbol binario, que es compatible con las siguientes operaciones:

• devolver el n ésimo elemento
• borrar la ésimo elemento n

Estas operaciones pueden implementarse para ejecutarse en el tiempo O(log n), donde n es la cantidad de nodos en el árbol.

Para construir el árbol, puede crear una rutina personalizada que construya el árbol a partir de una matriz determinada de elementos o implementar una operación de inserción (asegúrese de mantener el árbol equilibrado).

Cada nodo en el árbol necesita la siguiente información:

• Punteros a la izquierda y los niños correctas
• ¿Cuántos elementos hay en la izquierda y subárboles derecho

Con tal estructura en su lugar, resolver el resto del problema debería ser bastante sencillo.

También recomiendo calcular las respuestas para todos los posibles valores de entrada antes de leer cualquier entrada, en lugar de calcular la respuesta para cada línea de entrada.

Se acepta una implementación de Java del algoritmo anterior en 0,68 segundos en el sitio web que se ha vinculado.

(Lo siento por no proporcionar ningún tipo de ayuda específico de Python, pero es de esperar que el algoritmo descrito anteriormente será lo suficientemente rápido.)

Answer 5

¿Por qué no crear una nueva lista?

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