Dizionari ordinato in Python 3.6+?

Dizionari sono ordinati in Python 3.6 (sotto il CPython attuazione almeno) a differenza delle precedenti incarnazioni. Questo mi sembra un cambiamento sostanziale, ma è solo un breve paragrafo in documentazione. Esso è descritto come un CPython dettaglio di implementazione piuttosto che una caratteristica del linguaggio, ma implica anche questo può diventare standard per il futuro.

Come funziona il nuovo dizionario di attuazione esegue meglio di quello precedente, mantenendo ordine degli elementi?

Ecco il testo dalla documentazione:

dict() utilizza ora una “compatta” rappresentazione introdotta da PyPy. L’utilizzo della memoria del nuovo dict() è tra il 20% e il 25% più piccolo rispetto a Python 3.5. PEP 468 (Mantenendo l’ordine di **kwargs in una funzione.) è implementato da questa. L’ordine di preservare l’aspetto di questa nuova implementazione è considerato un dettaglio di implementazione e non dovrebbe essere invocata (questo potrebbe cambiare in futuro, ma si è voluto con questo nuovo dict implementazione in un linguaggio per poche uscite, prima di cambiare la lingua specifica di mandato ordine-conservazione semantica per tutti gli attuali e futuri Python implementazioni; questo aiuta anche a mantenere la retrocompatibilità con le precedenti versioni del linguaggio, dove casuale iterazione ordine è ancora in vigore, ad esempio, Python 3.5). (Ha contribuito da INADA Naoki in problema 27350. Idea originariamente suggerito da Raymond Hettinger.)

Aggiornamento dicembre 2017: dicts mantenendo ordine di inserimento dei dati garantito per Python 3.7

  • In questo thread su Python-Dev mailing-list : mail.python.org/pipermail/python-dev/2016-September/146327.html se non avete visto ; è fondamentalmente una discussione intorno a questi temi.
  • Si noti che tempo fa (2003), Perl implementatori deciso di fare delle tabelle di hash (equivalente a Python dizionari) e non solo in modo esplicito non ordinato, ma randomizzati per motivi di sicurezza (perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks). Quindi certamente non contare su questa “caratteristica”, perché se l’esperienza degli altri può essere una guida, probabilmente è ritenuto essere invertito a un certo punto…
  • Informazioni qui da Raymon Hettinger compreso il codice originale ricetta per il nuovo dict. È interessante notare che dice: “Al momento è stato presentato, l’umore era opposto dicts di essere ordinato, in modo che questo [originale] ricetta intenzionalmente riempie valori eliminati con l’ultima voce nell’elenco.”
  • Se kwargs ora sono supposti per essere ordinato (che è bella l’idea) e kwargs sono dict, non OrderedDict, quindi credo che si potrebbe supporre che dict tasti soggiorno ordinato in futuro la versione di Python, nonostante la documentazione dice il contrario.
  • No, non fare quella ipotesi. Questo è stato un problema in corso la stesura del PEP che definisce l’ordinamento funzione di **kwargs e come tale formulazione è diplomatico: **kwargs in una funzione di firma è ora garantito per essere un inserimento-ordine-conservazione mappa. Hanno usato il termine mappatura in modo da non costringere gli altri implementazioni per rendere il dict ordinato (e uso un OrderedDict internamente) e come un modo per segnalare che questo non dovrebbe dipendere dal fatto che il dict non è ordinato.
  • Un buon video spiegazione da Raymond Hettinger
  • l’ordine e la complessità della hashmap non è cambiato. La modifica rende l’hashmap più piccolo di sprecare meno spazio, e lo spazio risparmiato è (di solito?) più di ausiliario di array prende. Più veloce, più piccolo, ordinato – si arriva a scegliere tutti e 3.
  • Un modo per avere OrderedDicts automaticamente convertite in ordinarie dicts in Python 3.7, o deve passare manualmente dai test che versione di Python è in esecuzione?
  • Potrebbe essere la pena di una questione a parte, ma non che io sappia. Il beneficio di prestazioni di commutazione credo che sarebbe più mite. In più si potrebbe desiderare un OrderedDict ancora, anche in Python 3.7 stackoverflow.com/questions/50872498/…
  • Chris: Bene i punti collegati risposta. Penso che ci sia un gran numero di OrderedDict i casi d’uso che non uso quelli “caratteristiche avanzate”—che è il motivo per cui ho chiesto, ma è abbastanza facile per verificare quale versione di Python è utilizzato e scegliere quale si desidera che possono essere utilizzati in modo intercambiabile.

 

4 Replies
  1. 419

    Dizionari ordinato in Python 3.6+?

    Sono inserimento ordinato[1]. Come di Python 3.6, per il CPython implementazione di Python, dizionari ricordare l’ordine di elementi inseriti. Questo è considerato un dettaglio di implementazione in Python 3.6; è necessario utilizzare OrderedDict se si desidera che l’inserimento di ordinazione che garantito in altre implementazioni di Python (e altre ordinato comportamento[1]).

    Di Python 3.7, questo non è più un dettaglio di implementazione e invece diventa una caratteristica del linguaggio. Da un python-dev messaggio da GvR:

    Fare così. “Dict mantiene inserimento dell’ordine” è la sentenza. Grazie!

    Questo significa semplicemente che si può fare affidamento su di esso. Altre implementazioni di Python deve anche offrire un inserimento ordinato dizionario, se vogliono essere conforme implementazione di Python 3.7.


    Come il Python 3.6 dizionario attuazione eseguire meglio[2] di quello precedente, mantenendo ordine degli elementi?

    Essenzialmente, da talmente semplice mantenere aggiornati i due array.

    • Il primo array, dk_entries, contiene le voci (del tipo PyDictKeyEntry) per il dizionario, nell’ordine in cui sono stati inseriti. Preservare l’ordine viene raggiunto da questa essere un’aggiunta solo array in cui i nuovi elementi sono inseriti sempre alla fine (inserimento dell’ordine).

    • Il secondo, dk_indices, contiene gli indici per la dk_entries array (che è, valori che indicano la posizione della voce corrispondente in dk_entries). Questo array agisce come una tabella hash. Quando un tasto viene eseguito l’hashing conduce ad uno degli indici memorizzati in dk_indices e la voce corrispondente viene recuperata dall’indicizzazione dk_entries. Dal momento che solo gli indici sono tenuti, il tipo della matrice dipende dalla dimensione complessiva del dizionario (che vanno dal tipo di int8_t(1 byte) per int32_t/int64_t (4/8 byte) su 32/64 po ‘ di build)

    Nel precedente implementazione di una matrice sparsa di tipo PyDictKeyEntry e dimensioni dk_size dovuto essere assegnati; tuttavia, esso ha anche portato un sacco di spazio vuoto dal momento che la matrice non è stato permesso di essere più di 2/3 * dk_size pieno per motivi di prestazioni. (e lo spazio vuoto ancora aveva PyDictKeyEntry dimensioni!).

    Questo non è il caso ora, dal momento che solo il richiesto voci vengono memorizzati (quelli che sono stati inseriti) e una matrice sparsa di tipo intX_t (X a seconda dict dimensioni) 2/3 * dk_sizes full è mantenuta. Lo spazio vuoto è cambiato dal tipo di PyDictKeyEntry per intX_t.

    Così, ovviamente, la creazione di una matrice sparsa di tipo PyDictKeyEntry è più impegnativa di una matrice sparsa per la memorizzazione di ints.

    Si può vedere la conversazione su Python-Dev su questa funzione, se interessati, è una buona lettura.


    Nella proposta originaria, realizzata da Raymond Hettinger, per una visualizzazione di strutture di dati utilizzato può essere visto, che cattura l’essenza dell’idea.

    Per esempio, il dizionario:

    d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

    è attualmente memorizzati come [keyhash, chiave, valore]:

    entries = [['--', '--', '--'],
               [-8522787127447073495, 'barry', 'green'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               [-9092791511155847987, 'timmy', 'red'],
               ['--', '--', '--'],
               [-6480567542315338377, 'guido', 'blue']]

    Invece, i dati devono essere organizzati come segue:

    indices =  [None, 1, None, None, None, 0, None, 2]
    entries =  [[-9092791511155847987, 'timmy', 'red'],
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue']]

    Come si può visivamente vediamo ora, nella proposta originale, un sacco di spazio è essenzialmente vuoto per ridurre le collisioni e rendere il look-up più veloce. Con il nuovo approccio, è possibile ridurre la quantità di memoria richiesta spostando la frammentarietà in cui è davvero necessario, degli indici.



    [1]: io dico “inserimento ordinato” e non “ordinate” in quanto, con l’esistenza di OrderedDict, “ordinato”, suggerisce ulteriormente il comportamento che il dict oggetto non fornisce. OrderedDicts sono reversibili, fornire un ordine di metodi sensibili e, soprattutto, di fornire un ordine-sensive i test di uguaglianza (==, !=). dicts, che attualmente non offrono alcuna di tali comportamenti e metodi.



    [2]: Il nuovo dizionario implementazioni esegue meglio memoria saggio essendo stato progettato in modo compatto; questo è il vantaggio principale qui. Velocità saggio, la differenza non è così drastico, ci posti dove il nuovo dict potrebbe introdurre lieve regressioni ( chiave-le ricerche, per esempio ), mentre in altri (iterazione e il ridimensionamento vengono in mente) un incremento delle prestazioni dovrebbe essere presente.


    In generale, le prestazioni del dizionario, soprattutto in situazioni di vita reale, migliora grazie alla compattezza introdotto.

    • Allora, cosa succede quando un elemento viene rimosso? è il entries elenco ridimensionata? o è uno spazio vuoto mantenuto? o è compressa di volta in volta?
    • Quando un elemento viene rimosso, il corrispondente indice è sostituito da DKIX_DUMMY con un valore di -2 e con l’ingresso nel entry array sostituito da NULL, quando l’inserimento è effettuato con i nuovi valori vengono aggiunte le voci di matrice, non sono stati in grado di discernere, di sicurezza, ma abbastanza sicuro, quando gli indici si riempie oltre la 2/3 soglia di ridimensionamento viene eseguita. Questo può portare alla riduzione invece di crescere se molti DUMMY voci di esistere.
    • Hai notato qualche differenza di velocità saggio, con il nuovo dict attuazione?
    • No, l’unica effettiva regressione io ho visto sia sul tracker in un messaggio di Victor. Più che altro microbenchmark, ho visto nessun altro problema/messaggio che indica una grave differenza di velocità nella vita reale carichi di lavoro. Esistono luoghi in cui il nuovo dict potrebbe introdurre lieve regressioni (key-le ricerche, per esempio), mentre in altri (iterazione e il ridimensionamento vengono in mente) un incremento di prestazioni sarebbe presente.
    • Correzione sul ridimensionamento parte: Dizionari non ridimensiona quando si eliminano gli elementi, si ri-calcolare quando si reinserisce. Così, se un dict è creato con d = {i:i for i in range(100)} e si .pop tutti gli elementi di w/o l’inserimento, la dimensione non cambia. Quando si aggiunge di nuovo, d[1] = 1, la dimensione appropriata è calcolato e il dict ridimensiona.
    • quali sono i valori in indices lista? come 0, 1, 2 è tradotto in oggetto? è solo per chiarezza, o che è il valore effettivo all’interno di quella lista? Ho pensato che sarebbe tenere il hash valore della chiave
    • Ogni pensiero su ciò che accadrà a OrderedDict in futuro, credo che sarà mantenuto per compatibilità? Attualmente OrderedDict supporta reversed() iterazione e la OrderedDict.move_to_end() metodo, ma forse questi saranno aggiunti al normale dict troppo?
    • Sono abbastanza sicuro che è in soggiorno. La cosa è, e il motivo per cui ho modificato la mia risposta per rimuovere dichiarazioni coperta di circa ‘dict essere ordinato, dicts non sono ordinati in senso OrderedDicts sono. Il notevole problema è l’uguaglianza. dicts ordine insensibile ==, OrderedDicts ordine sensibili. Dumping OrderedDicts e modifica dicts di ordine sensibile confronti potrebbe portare a un sacco di rottura del vecchio codice. Sto cercando di indovinare l’unica cosa che potrebbe cambiare OrderedDicts è la sua attuazione.
    • Correlato S. O discussione può essere trovato here.
    • Grazie per la tua risposta dettaglio. Ho tradotto in coreano e distribuito a Facebook gruppi di Python Corea. blog.sinwoobang.mi/post/176050610602/pythondictorder. Molti di Pythonista in Corea è stato aiutato dal tuo post. Grazie ancora.
    • Cordiali saluti, reversed supporto è venuta in Python 3.8. Non mi aspetto di vedere move_to_end; il compatto e ordinato dict design non il supporto che così (sarebbe lasciare una voce fittizia dietro, e di trovare e aggiornare l’indice associato voce ogni volta che finiscono per risultare inutilmente ampliare le voci di matrice, o forzare un completo rimaneggiamento per cancellare i manichini. In confronto, OrderedDict solo modifiche che un paio di puntatori. Qualsiasi algoritmo che si basa su move_to_end dovrebbe utilizzare OrderedDict; aggiunta del supporto per dict incoraggiare il codice cattivo.
    • Cosa -9092791511155847987, -8522787127447073495 e -6480567542315338377 dire?
    • È la creazione ordine non ancora garantito in 3.7? ad esempio,a = {'one': 1, 'two': 2}?
    • quelli sono i valori hash per le chiavi del dizionario.

  2. 63

    Di seguito è la risposta originale prima domanda:

    Devo usare dict o OrderedDict in Python 3.6?

    Penso che questa frase la documentazione è in realtà abbastanza per rispondere alla tua domanda

    Ordine, conservando l’aspetto di questa nuova implementazione è considerato un dettaglio di implementazione e non dovrebbe essere invocata

    dict non è esplicitamente pensato per essere una raccolta ordinata, quindi, se si vuole rimanere coerenti e non fare affidamento su un effetto collaterale di nuova realizzazione si deve attaccare con OrderedDict.

    Rendere il vostro codice a prova di futuro 🙂

    C’è un dibattito su che qui.

    EDIT: Python 3.7 manterrà questa funzione vedere

    • Sembra che se non vuole essere una funzione reale, ma solo un dettaglio di implementazione allora non dovrebbero nemmeno mettere nella documentazione, allora.
    • Io non sono sicuro circa il vostro modifica avvertimento; dal momento che la garanzia si applica solo per Python 3.7, presumo che i consigli per Python 3.6 è invariato, ovvero dicts sono ordinati in CPython, ma non contare su di esso
  3. 21

    Aggiornamento:
    Guido van Rossum annunciato sulla mailing list che Python 3.7 dicts in tutte Python implementazioni deve conservare inserimento dell’ordine.

    • Ora che la chiave di ordinamento è lo standard ufficiale, qual è lo scopo della OrderedDict? O è ridondante?
    • Credo che OrderedDict non essere ridondante, perché ha il move_to_end metodo e la sua uguaglianza è un ordine sensibili: docs.python.org/3/library/…. Vedere la nota a Jim Fasarakis Hilliard risposta.
    • vedere Jim risposta e questo Q&A stackoverflow.com/questions/50872498/…
    • Se si desidera che il codice per eseguire la stessa su 2.7 e 3.6/3.7+, è necessario utilizzare OrderedDict
    • Probabilmente ci sarà un “UnorderedDict” presto per gente che, come per il fastidio il loro dicts per motivi di sicurezza ;p
  4. 5

    Volevo aggiungere alla discussione di cui sopra, ma non hanno la reputazione di commento.

    Python 3.8 non è ancora uscito, ma include anche il reversed() funzione di dizionari (rimozione altra differenza OrderedDict.

    Dict e dictviews sono ora iterable in rovesciata di inserimento ordine utilizzando invertito(). (Ha contribuito da Rémi Lapeyre in bpo-33462.)
    Vedere cosa c’è di nuovo in python 3.8

    Non vedo alcuna menzione dell’operatore di uguaglianza o di altre caratteristiche di OrderedDict quindi non sono ancora del tutto uguali.

Lascia un commento