Set iterabile ordinato da Python, modificabile durante l'iterazione

1

Sto cercando una infrastruttura dati per gestire il ciclo di un gran numero di subroutine ordinate, alcune delle quali sono attive, molte delle quali non lo sono.

Penso che ho bisogno di un'implementazione di un python set come oggetto che rimane ordinato quando modificato, può essere facilmente iterato (non mi interessa se funziona un loop effettivo, purché esista un modo semplice ed efficiente leggere ogni elemento in ordine). E soprattutto può essere modificato mentre viene iterato.

Questo per consentire un'implementazione di una forma molto specifica di programma di subroutine (sfortunatamente non posso usare i moduli di subroutine incorporati dato che il mio programma python sta emulando il comportamento di un sistema legacy proprio così ho bisogno di un controllo più fine.)

Effettivamente ho un elenco di subroutine a cui fa riferimento un numero di indice in un dizionario, le subroutine sono ripetute in ordine ascendente fino a quando non viene raggiunto l'ultimo punto in cui ritorniamo al numero più basso. Tuttavia ci sono un gran numero di subroutine e solo poche in qualsiasi momento saranno 'attive' e quelle che non sono attive vengono saltate nell'ordine per l'esecuzione. Ho considerato semplicemente di dare a ciascuna routine una bandiera attiva che sarebbe stata testata prima di essere eseguita, tuttavia l'enorme numero di routine potenziali rispetto al numero minuscolo di quelle attive rende questo metodo molto lento. Le subroutine vengono attivate o disattivate solo occasionalmente ma eseguendole devono essere molto veloci. Come tale ho cercato di mantenere una lista delle chiavi di quelle attive e scorrere quella, aggiungendole o rimuovendole quando sono attivate o disattivate, ma sto cercando un modo ragionevolmente efficiente di mantenere questo elenco.

I due principali sistemi che mi sembrano fattibili sono blist ordinati set , tuttavia non sono sicuro che supportino modificato mentre è iterato sopra e usando due heapq e spostando gli articoli tra loro in ordine, questo sicuramente supporterà modifica in qualsiasi momento, ma richiederebbe molto più lavoro manuale e probabilmente sarebbe più lento.

Tuttavia, qualcuno potrebbe avere una risposta molto migliore di una di queste, quindi apprezzerò qualsiasi idea su come ottenere ciò con ragionevole efficienza e idealmente in un modo "pitonico", sebbene possa essere un po 'brutto se fa il lavoro.

    
posta Vality 18.02.2014 - 12:30
fonte

2 risposte

3

C'è un nuovo modulo Python chiamato sortedcontainers che soddisferà le tue esigenze. È progettato come sostituto quasi completo per Blist, ma è puro Python e più veloce nella maggior parte dei casi . Il supporto di iterazione integrato è estremamente veloce ma non consente di modificare gli elementi. Invece, vorrei usare l'indicizzazione built-in che è anche veloce.

Qualcosa del genere:

from sortedcontainers import SortedSet
ss = SortedSet(...)
pos = 0
while pos < len(ss):
    item = ss[pos]

    # ... do something with item ...
    # ... possibly insert or delete items ...

    pos += 1

Dovrai decidere cosa succede se inserisci un elemento in modo che pos += 1 si riferisca allo stesso oggetto in iterazioni successive.

Puoi anche accodare gli inserimenti / le eliminazioni fino a dopo aver iterato il set ordinato.

Dichiarazione di non responsabilità: sono l'autore del modulo ordinati-contenitori.

    
risposta data 03.04.2014 - 19:23
fonte
2

Vorrei usare un heapq, dare alle subroutine una chiave di ordinamento e semplicemente aggiungere routine attive all'heap. Le subroutine inattive non hanno bisogno di essere in un heap; possono essere in un dizionario, dato che non si passerà sopra a quelli in ordine.

    
risposta data 20.02.2014 - 20:25
fonte

Leggi altre domande sui tag