Python: velocizzare la rimozione di ogni n-esimo elemento dalla lista

Question

Sto cercando di risolvere e sebbene la soluzione (vedere il codice sottostante) funzioni correttamente, è troppo lenta per l'inoltro riuscito.

• Qualsiasi suggerimento su come eseguire questa corsa più veloce (rimozione di ogni n-esimo elemento da un elenco)?
• Oppure suggerimenti per un algoritmo migliore per calcolare lo stesso; Sembra che io non riesco a pensare a niente altro che forza bruta per ora ...

In sostanza, l'operazione attuale è:

 
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) 

mio codice originale (si calcola il 3000 prima fortunata numeri in circa un secondo sulla mia macchina - purtroppo troppo 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: grazie ai i contributi formidabili di Mark Dickinson, Steve Jessop e gnibbler, io ottenuto al seguente, che è piuttosto un bel po 'più veloce rispetto al mio codice originale (e con successo ma ho presentato al http://www.spoj.pl con 0,58 secondi!) ...

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

Questa serie si chiama ludic numbers

__delslice__ dovrebbe essere più veloce di __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] 

Così il ciclo diventa.

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

che viene eseguito in meno di 0,1 secondi

Answer 2

È meglio utilizzando una matrice e azzeramento di ogni Nth item usando quella strategia; dopo aver eseguito questa operazione alcune volte di seguito, gli aggiornamenti iniziano a diventare complicati, quindi è necessario riformattare l'array. Questo dovrebbe migliorare la velocità di almeno un fattore di 10. Hai bisogno di molto meglio di così?

Answer 3

Provate a usare queste due linee per la cancellazione e il filtraggio, anziché quello che avete; filter(None, ...) viene eseguito in modo considerevolmente più veloce rispetto allo filter(lambda ...).

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

Modifica: molto meglio usare semplicemente del sieve[::item]; vedi la soluzione di gnibbler.

Si potrebbe anche essere in grado di trovare una migliore condizione di terminazione per il ciclo while: ad esempio, se il primo elemento che rimane nel setaccio è i poi i primi i elementi del setaccio diventerà il prossimo i numeri fortunati; quindi se len(luckynumbers) + sieve[0] >= wanted_n dovresti aver già calcolato il numero che ti serve --- devi solo capire dove si trova in sieve in modo da poterlo estrarre.

Sulla mia macchina, la seguente versione del ciclo interno corre circa 15 volte più veloce di vostra originale per trovare il numero fortunato 3000i:

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 spiegazione su come risolvere questo problema si possono trovare here. (Il problema che ho collegato richiede altro, ma il passo principale in questo problema è lo stesso di quello che stai cercando di risolvere.) Il sito che ho collegato contiene anche una soluzione di esempio in C++.

L'insieme dei numeri può essere rappresentato in un albero binario, che supporta le seguenti operazioni:

• ritorno l'elemento n esimo
• cancellare l'elemento esimo n

queste operazioni possono essere implementato per l'esecuzione nel tempo O(log n), dove n è il numero di nodi nell'albero.

Per creare l'albero, è possibile creare una routine personalizzata che costruisca l'albero da una determinata matrice di elementi o implementare un'operazione di inserimento (assicurarsi di mantenere l'albero bilanciato).

Ogni nodo nell'albero bisogno le seguenti informazioni:

• puntatori a sinistra e bambini destro
• Quanti elementi ci sono nel sottostrutture sinistro e destro

Con un tale struttura in atto, risolvere il resto del problema dovrebbe essere abbastanza semplice.

Si consiglia inoltre di calcolare le risposte per tutti i valori di input possibili prima di leggere qualsiasi input, invece di calcolare la risposta per ogni riga di input.

Un'implementazione Java dell'algoritmo sopra riportato viene accettata in 0.68 secondi sul sito Web collegato.

(Ci scusiamo per non fornire alcun aiuto specifico per Python, ma si spera che l'algoritmo descritto sopra sarà abbastanza veloce.)

Answer 5

Perché non solo creare una nuova lista?

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