De ce seturile și dicționarele Python nu sunt comandate în mod implicit?

Ideea nu este că cheltuielile generale sunt deosebit de mari, mai mult că există la toate .

Funcțiile lingvistice trebuie să găsească întotdeauna un echilibru dintre rentabilitate și cost. Dicționarele sunt absolut fundamentale pentru programarea Python, așa că ar fi foarte rău pentru ele să fie chiar puțin mai lente decât trebuie să fie doar pentru a păstra ordinea de inserare, atunci când de cele mai multe ori nu aveți nevoie de comandă. A fost decizia corectă să renunțați la ordinea de inserare în schimbul accesului ușor mai rapid și lăsați structura de date care păstrează ordinea pentru clasele speciale. Dacă ar exista o altă structură de date care ar putea face tot ce poate un dict, iar dict a fost un rid mai puțin folosit al limbii, lucrurile s-ar putea să arate diferit.

Comentarii

• Contra-argumentul meu în acest sens ar fi: folosiți un tip de date dict mai neordonat pentru dicționare interne (la fel ca acolo ‘ s deque pentru a optimiza performanța în anumite alte contexte), dar lăsați tipul principal de date dict de utilizator să păstreze ordinea.
• De asemenea, am dreptate înțelegând că implementarea CPython a 3.6 păstrează de fapt ordinea de inserare pentru dicte?

Aveți dreptate că articolele sunt stocate intern cu o anumită comandă, dar această ordine internă este determinată de codul hash al cheii, care permite recuperarea să fie atât de rapidă. Deci, dacă un set / dict ar trebui comandat, ar trebui să mențină o structură de date internă separată (să spunem o listă ordonată de chei) pentru aceasta.

Acest lucru ar crește, desigur, dimensiunea. Dar, mai rău, va afecta performanța. De exemplu, eliminarea unui element dintr-un set este o operație O (1), dar dacă trebuie să scoată și cheia dintr-o listă ordonată internă, aceasta va deveni O (n). Un astfel de cost ar fi dezastruos pentru unele aplicații. Având în vedere că este destul de rar, aveți nevoie de un set ordonat, un astfel de compromis nu merită pentru tipurile standard set / dict.

Premisa dvs. este incorectă. Începând cu Python 3.6, dict își amintesc ordinea de inserare a acestora . Acesta a fost un detaliu de implementare și a fost promovat la funcția de limbaj complet în 3.7. În 3.6, pentru cazul specific **kwargs, păstrarea comenzii este garantată în mod special.

Comentarii

• Da, ‘ nu știam acest lucru când am pus întrebarea, deoarece ‘ nu este încă o caracteristică de limbă, ci doar o implementare detalii într-o singură implementare. Dar se pare că cel puțin dicționarele vor deveni ordonate pe termen lung și, sperăm, că se setează și ele.
• @oulenz nu ‘ nu mai este un detaliu de implementare, ci ‘ sunt necesare începând cu Python 3.7

Un ordin set este posibil doar atunci când elementele care trebuie stocate au o comandă (adică o metodă de comparație) în primul rând – dar aceasta nu este întotdeauna o dată.

Implementarea implicită a setului / hărții în majoritatea mediilor din zilele noastre este bazat pe un hashtable de redimensionare automată, care are aceste avantaje:

• mai rapid
• folosește mai puțină memorie
• nu necesită ca elementele să ofere o comandă

seturile trebuie stocate intern cu o anumită comandă oricum

Dar această ordine internă nu are neapărat vreun sens și nici nu rămâne la fel. Într-adevăr, o proprietate a hashtable-urilor care uneori încurcă dezvoltatorii neexperimentați este aceea că ordinea de iterație, care este bazată pe ordonarea internă, se poate schimba complet atunci când sunt adăugate elemente (adică atunci când se declanșează o redimensionare) sau între diferite aleargă.

Comentarii

• Nu ‘ nu înțeleg prima dvs. remarcă. Nu avem ‘ nevoie de o metodă de comparație, ordinea ar putea fi doar moștenită, de ex. dintr-o listă sau dintr-un șir literal {3, 5, 4}.
• @oulenz: dacă nu vă deranjează ‘ fără sens și variază în timp, atunci fiecare set este ordonat, deoarece va exista un anumit tip de ordine de iterație. Dar ” set ordonat ” implică faptul că ordonarea este semantică pentru elemente și acest lucru nu este întotdeauna posibil. ‘ nu înțeleg cu adevărat de ce doriți să fie comandate toate seturile.
• ” Set ordonat ” nu implică faptul că ordonarea este semantică, ci doar că există o anumită ordonare. Desigur, îmi pasă că, odată ce această comandă este stabilită, este păstrată, cu excepția cazului în care conținutul acesteia este modificat.
• Ne pare rău, nu eram ‘ știut că există implicații pentru unii oameni. Pur și simplu aveam în minte un set ordonat liniar din matematică. en.wikipedia.org/wiki/Total_order
• @jameslarge nu există relația de ordine ‘ Nu trebuie să-mi fie necunoscut. Dacă deriv dintr-o listă un set ordonat, știu exact care este ordinea acestuia. Dacă vreau să asigur o anumită comandă, pot sorta setul. Dar dacă ‘ nu aveți nevoie de comandă, puteți doar să o ignorați.

Ideea generală din spatele unui set sau a unui dicționar este că intenționați să efectuați o mulțime de operații de căutare. Este optimizat pentru operațiunile de căutare menționate utilizând un hash care permite căutarea O (1) în majoritatea cazurilor.

Comanda se face folosind tablouri sau liste legate și, de fapt, efectuând operațiuni în care ordinea este importantă, acestea sunt optimizate. pentru asta , cum ar fi adăugarea unei valori la sfârșit sau la început.

Prin natura acestor două structuri de date, niciuna dintre acestea nu este optimizată pentru ambele. Acest lucru nu înseamnă că nu este posibil, dar implică ambele structuri de date dacă doriți să fie optimizate atât operațiunile de căutare, cât și cele bazate pe comenzi.

Deci, aveți acest compromis între:

optimizarea operației de căutare < => operațiuni bazate pe comenzi < => utilizarea memoriei

Consensul general este că, în calitate de programator, doriți în general să optimizați pentru unul sau altul, dar nu pentru ambele și, cu siguranță, nimeni nu susține dublarea utilizării memoriei atunci când aveți nevoie doar de pentru a optimiza unul dintre cele două.

Acestea fiind spuse, există există implementări cu ambele sau cel puțin în Java, în mod specific LinkedHashMap este atât o matrice, cât și un hash- dicționar bazat pe. Uneori este posibil să aveți nevoie de ambele, dar este recomandat să utilizați ArrayList dacă aveți nevoie doar de o listă și un HashMap dacă aveți nevoie doar de un dicționar .

Comentarii

• Huh? Un Java LinkedHashMap nu este ” atât o matrice, cât și un dicționar bazat pe hash „. ‘ este practic un HashMap (adică folosește un tablou intern) suprapus cu o listă legată pentru a permite iterația în ordinea de inserare.
• Structurile de date liniare nu sunt ‘ t singurele structuri de date ordonate; arborii binari pot fi, de asemenea, comandați (cum ar fi copacii roșu-negri și AVL). O altă operațiune care poate fi implicată în compromis este inserarea (matricele sunt destul de eficiente în ceea ce privește căutarea, iterația și utilizarea memoriei, dar cele mai lente când vine vorba de inserare).