2010-01-12 8 views
21

Attualmente sto implementando un complesso microbial food-web in Python usando SciPy.integrate.ode. Ho bisogno della capacità di aggiungere facilmente specie e reazioni al sistema, quindi devo codificare qualcosa di abbastanza generale. Il mio schema simile a questa:L'ordine di un dizionario Python è garantito su iterazioni?

class Reaction(object): 
    def __init__(self): 
     #stuff common to all reactions 
    def __getReactionRate(self, **kwargs): 
     raise NotImplementedError 

... Reaction subclasses that 
... implement specific types of reactions 


class Species(object): 
    def __init__(self, reactionsDict): 
     self.reactionsDict = reactionsDict 
     #reactionsDict looks like {'ReactionName':reactionObject, ...} 
     #stuff common to all species 

    def sumOverAllReactionsForThisSpecies(self, **kwargs): 
     #loop over all the reactions and return the 
     #cumulative change in the concentrations of all solutes 

...Species subclasses where for each species 
... are defined and passed to the superclass constructor 

class FermentationChamber(object): 
    def __init__(self, speciesList, timeToSolve, *args): 
     #do initialization 

    def step(self): 
     #loop over each species, which in turn loops 
     #over each reaction inside it and return a 
     #cumulative dictionary of total change for each 
     #solute in the whole system 


if __name__==__main__: 
    f = FermentationChamber(...) 

    o = ode(...) #initialize ode solver 

    while o.successful() and o.t<timeToSolve: 
     o.integrate() 

    #process o.t and o.y (o.t contains the time points 
    #and o.y contains the solution matrix) 

Quindi, la domanda è, quando ho scorrere i dizionari in Species.sumOverAllReactionsForThisSpecies() e FermentationChamber.step(), è l'ordine di iterazione dei dizionari garantiti per essere lo stesso se vengono aggiunti o rimossi senza elementi dai dizionari tra la prima e l'ultima iterazione? Cioè, posso supporre che l'ordine della matrice numpy creata ad ogni iterazione dal dizionario non varierà? Ad esempio, se un dizionario ha il formato {'Glucose': 10, 'Fructose': 12}, se una matrice creata da questo dizionario sarà sempre nello stesso ordine (non importa quale sia l'ordine, come finché è deterministico).

Scusate per il mega-post, volevo solo farvi sapere da dove vengo.

+0

@ChinmayKanchi ti dispiace se modifico pesantemente questa domanda? Tutti i dettagli sulle reti alimentari e sull'integrazione delle ODE non hanno nulla a che fare con la domanda, che è molto buona e importante. – LondonRob

risposta

4

Python 3.1 ha una classe collections.OrderedDict che può essere utilizzato per questo scopo. È anche molto efficiente: "I tempi di esecuzione di Big-O per tutti i metodi sono gli stessi dei dizionari normali."

Lo code for OrderedDict è compatibile con Python 2.x, sebbene alcuni metodi ereditati (dal modulo _abcoll) utilizzino le funzionalità solo di Python 3. Tuttavia, possono essere modificati in codice 2.x con il minimo sforzo.

+1

Questo in realtà non risponde alla domanda, e l'uso di OrderedDict, mentre garantisce anche l'ordinamento deterministico, aumenta l'utilizzo delle risorse (non è sicuro in che modo esattamente, però). Come indicano altre risposte, un ditt normale ha già questa garanzia, quindi non è necessario utilizzare OrderedDict (per questo particolare caso). –

43

Sì, lo stesso ordine è garantito se non viene modificato.

Vedere i documenti here.

Edit:

Per quanto riguarda se la modifica del valore (ma non l'aggiunta/rimozione di una chiave) interesserà l'ordine, questo è ciò che i commenti nel C-fonte dice:

/* CAUTION: PyDict_SetItem() must guarantee that it won't resize the 
* dictionary if it's merely replacing the value for an existing key. 
* This means that it's safe to loop over a dictionary with PyDict_Next() 
* and occasionally replace a value -- but you can't insert new keys or 
* remove them. 
*/ 

Sembra che non sia un dettaglio di implementazione, ma un requisito della lingua.

+0

Ah, eccellente! Non ero sicuro di averlo interpretato correttamente. Giusto per essere sicuro, non importa se i _values_ sono modificati, giusto, purché i tasti non lo siano? –

+2

Sono abbastanza sicuro che "nessuna modifica" significa * no * modifiche, punto. La modifica dei valori * potrebbe * alterare l'ordine dei dizionari. –

+0

Dannazione! Sembra che dovrò ripensare quell'algoritmo. Esiste un datastructure di tipo map ordinato in scipy/numpy o nella libreria standard python? Preferirei non dover dipendere da più librerie di quanto non sia necessario. –

8

Fornito no modifiche apportate al dizionario, la risposta è sì. See the docs here.

Tuttavia, i dizionari non sono ordinati per natura in Python. In generale, non è consigliabile affidarsi ai dizionari per dati ordinati sensibili.

Un esempio di una soluzione più robusta sarebbe Django's SortedDict data structure.

7

Se si desidera che l'ordine sia coerente, farei qualcosa per forzare un particolare ordine. Anche se potresti essere in grado di convincerti che l'ordine è garantito, e potresti avere ragione, mi sembra fragile e sarà misterioso per altri sviluppatori.

Ad esempio, si sottolinea sempre nella domanda. È importante che sia lo stesso ordine in Python 2.5 e 2.6? 2.6 e 3.1? CPython e Jython? Non conterei su quelli.

+0

Esatto! La fragilità di questo è ciò che mi impedisce di farlo ... –

+1

Buon punto. Non ero sicuro di quanto sarebbe fragile quando ho fatto questa domanda. Un ripensamento di questo algoritmo è sicuramente in ordine. –

5

Inoltre, consiglierei di non fare affidamento sul fatto che l'ordine dei dizionari non è casuale.

Se si desidera una soluzione integrata per l'ordinamento si dizionario leggere http://www.python.org/dev/peps/pep-0265/

Qui è il materiale più rilevante:

Questa PEP viene rifiutato perché la necessità per esso è stato in gran parte soddisfatte da PY2.ordinato() funzione built-4 di:

>>> sorted(d.iteritems(), key=itemgetter(1), reverse=True) 
    [('b', 23), ('d', 17), ('c', 5), ('a', 2), ('e', 1)] 

or for just the keys: 

    >>> sorted(d, key=d.__getitem__, reverse=True) 
    ['b', 'd', 'c', 'a', 'e'] 

Also, Python 2.5's heapq.nlargest() function addresses the common use 
case of finding only a few of the highest valued items: 

    >>> nlargest(2, d.iteritems(), itemgetter(1)) 
    [('b', 23), ('d', 17)] 
Problemi correlati