Perché i set e i dizionari Python non sono ordinati per impostazione predefinita?

Il punto non è che loverhead è particolarmente grande, più che è lì affatto .

Le funzionalità del linguaggio devono sempre trovare un equilibrio tra rapporto costo-efficacia. I dizionari sono assolutamente fondamentali per la programmazione Python, quindi sarebbe molto brutto che fossero anche leggermente più lenti di quanto dovrebbero essere solo per preservare lordine di inserimento, quando la maggior parte delle volte non è necessario ordinare. Era la decisione corretta di scartare lordine di inserzione in cambio di un accesso leggermente più veloce e lasciare la struttura dei dati che preserva lordine per classi speciali. Se cera unaltra struttura di dati che poteva fare tutto ciò che un dict può, e dict era una piega meno usata del linguaggio, le cose potrebbe avere un aspetto diverso.

Commenti

• Il mio controargomento sarebbe: usa un tipo di dati dict non ordinato più efficiente per i dizionari interni (proprio come lì ‘ s deque per ottimizzare le prestazioni in determinati altri contesti) ma lascia che il tipo di dati Dict rivolto allutente principale mantenga lordine.
• Inoltre, ho ragione nel capire che limplementazione di CPython 3.6 in effetti preserva lordine di inserimento per dicts?

Hai ragione che gli articoli sono immagazzinati internamente con un certo ordine, ma questo ordine interno è determinato dal codice hash della chiave, che è ciò che consente il recupero così veloce. Quindi, se un set / dict dovesse essere ordinato, dovrebbe mantenere una struttura dati interna separata (diciamo un elenco ordinato di chiavi) per questo.

Ciò ovviamente aumenterebbe le dimensioni. Ma forse peggio, influenzerà le prestazioni. Ad esempio, la rimozione di un elemento da un set è unoperazione O (1), ma se deve anche rimuovere la chiave da un elenco ordinato interno diventerebbe O (n). Un tale costo sarebbe disastroso per alcune applicazioni. Dato che è piuttosto raro che tu abbia bisogno di un set ordinato, un tale compromesso non vale la pena per i tipi standard set / dict.

Un set è possibile solo quando gli elementi da memorizzare hanno un ordine (cioè un metodo di confronto) in primo luogo, ma non è sempre un dato.

Limplementazione di set / map predefinita nella maggior parte degli ambienti oggigiorno è basato su una tabella hash a ridimensionamento automatico, che presenta questi vantaggi:

• più veloce
• utilizza meno memoria
• non richiede che gli elementi forniscano un ordine

i set devono essere comunque memorizzati internamente con un certo ordine

Ma questo ordine interno non ha necessariamente alcun significato, né rimane lo stesso. In effetti, una proprietà degli hashtable che a volte confonde gli sviluppatori inesperti è che lordine di iterazione, che è basato sullordinamento interno, può cambiare completamente quando vengono aggiunti elementi (cioè quando viene attivato un ridimensionamento) o tra diversi corre.

Commenti

• Non ‘ capisco la tua prima osservazione. Non ‘ non abbiamo bisogno di un metodo di confronto, lordine potrebbe essere semplicemente ereditato, ad es. da un elenco o da una stringa letterale {3, 5, 4}.
• @oulenz: se ‘ non ti dispiace lordine privo di significato e variabile nel tempo, quindi ogni set viene ordinato, perché ci sarà qualche tipo di ordine di iterazione. Ma ” set ordinato ” implica che lordinamento è semantico per gli elementi e ciò non è sempre possibile. Non ‘ davvero capisco perché vuoi che tutti i set vengano ordinati.
• ” Set ordinato ” non implica che lordinamento sia semantico, ma solo che ci sia un ordinamento. Ovviamente mi interessa che una volta stabilito questo ordine, venga preservato, a meno che il suo contenuto non venga modificato.
• Mi dispiace, ‘ non ero a conoscenza dellesistenza di implicazioni per alcune persone. Avevo semplicemente in mente un insieme ordinato linearmente dalla matematica. en.wikipedia.org/wiki/Total_order
• @jameslarge la relazione dellordine non ‘ non deve essere sconosciuto a me. Se ricavo un insieme ordinato da un elenco, so esattamente qual è il suo ordine. Se voglio garantire un certo ordine, posso ordinare il set. Ma se ‘ non ti serve lordine, puoi semplicemente ignorarlo.

Lidea generale alla base di un set o di un dizionario è che prevedi di eseguire molte operazioni di ricerca. È ottimizzato per tali operazioni di ricerca utilizzando un hash che consente la ricerca O (1) nella maggior parte dei casi.

Lordine viene eseguito utilizzando array o elenchi concatenati e infatti eseguendo operazioni in cui lordine è importante, vengono ottimizzati per quello come laggiunta di un valore alla fine o allinizio.

Per la natura di queste due strutture di dati, nessuna delle due è ottimizzata per entrambe. Questo non vuol dire che non sia possibile, ma coinvolge entrambe le strutture dati se si desidera ottimizzare sia le operazioni di ricerca che quelle basate sugli ordini.

Quindi hai questo compromesso tra:

ottimizzazione delle operazioni di ricerca < => operazioni basate sugli ordini < => utilizzo della memoria

Il consenso generale è che come programmatore, in genere si desidera ottimizzare per luno o per laltro ma non per entrambi, e certamente nessuno sostiene di raddoppiare lutilizzo della memoria quando è necessario solo per ottimizzare uno dei due.

Detto questo, sono implementazioni con entrambi, o almeno in Java, in particolare LinkedHashMap è sia un array che un hash- dizionario basato. A volte potresti aver bisogno di entrambi, ma è consigliabile utilizzare ArrayList se ti serve solo un elenco e un HashMap se hai solo bisogno di un dizionario .

Commenti

• Eh? Una LinkedHashMap Java non è ” sia un array che un dizionario basato su hash “. ‘ è fondamentalmente una HashMap (ovvero utilizza un array internamente) sovrapposta a un elenco collegato per consentire literazione nellordine di inserimento.
• Strutture dati lineari aren ‘ t le sole strutture dati ordinate; È inoltre possibile ordinare alberi binari (come alberi rosso-nero e AVL). Unaltra operazione che può essere coinvolta nel compromesso è linserimento (gli array sono abbastanza efficienti in termini di ricerca, iterazione e utilizzo della memoria, ma più lenti quando si tratta di inserimento).