Waarom worden Python-sets en woordenboeken niet standaard geordend?

Het punt is niet dat de overhead bijzonder groot is, meer dat het er is helemaal .

Taalkenmerken moeten altijd een evenwicht vinden tussen kosteneffectiviteit. Woordenboeken zijn absoluut fundamenteel voor het programmeren van Python, dus het zou erg slecht zijn als ze zelfs maar iets langzamer zouden zijn dan alleen om de invoegvolgorde te behouden, terwijl je meestal niet hoeft te bestellen. Het was de juiste beslissing om negeer de invoegvolgorde in ruil voor een iets snellere toegang, en laat de gegevensstructuur met behoud van de volgorde over voor speciale klassen. Als er een andere gegevensstructuur was die alles kon doen wat een dictaat kan, en dictaat was een minder gebruikte rimpel van de taal, dingen kan er anders uitzien.

Opmerkingen

• Mijn tegenargument zou zijn: gebruik een efficiënter ongeordend dict-datatype voor interne woordenboeken (net zoals daar ‘ s deque om de prestaties in bepaalde andere contexten te optimaliseren), maar laat het belangrijkste, naar de gebruiker gerichte datatype dicteren.
• Ook heb ik gelijk als ik begrijp dat de CPython-implementatie van 3.6 inderdaad de invoegvolgorde behoudt voor dicts?

Je hebt gelijk dat items intern worden opgeslagen met een bepaalde bestelling, maar deze interne bestelling is bepaald door de hash-code van de sleutel, waardoor het ophalen zo snel gaat. Dus als een set / dict zou moeten worden besteld, zou het hiervoor een aparte interne datastructuur moeten onderhouden (zeg maar een geordende lijst met sleutels).

Dit zou natuurlijk de grootte vergroten. Maar misschien nog erger, het zal de prestaties beïnvloeden. Het verwijderen van een item uit een set is bijvoorbeeld een O (1) -bewerking, maar als het ook de sleutel uit een intern geordende lijst moet verwijderen, wordt het O (n). Dergelijke kosten zouden voor sommige toepassingen desastreus zijn. Aangezien het vrij zeldzaam is dat je een geordende set nodig hebt, is een dergelijke afweging niet de moeite waard voor de standaard set / dict-typen.

Uw uitgangspunt is onjuist. Vanaf Python 3.6 onthouden dict s hun invoegvolgorde . Dit was een implementatiedetail en werd gepromoveerd tot volledige taalfunctie in 3.7. In 3.6, voor het specifieke geval van **kwargs, is het behoud van de bestelling specifiek gegarandeerd.

Opmerkingen

• Ja, ik was me ‘ niet bewust toen ik de vraag stelde, aangezien het ‘ nog geen taalfunctie is, maar slechts een implementatie detail in één implementatie. Maar het lijkt erop dat woordenboeken in ieder geval op de lange termijn geordend zullen worden, en hopelijk ook sets.
• @oulenz it ‘ is niet langer een implementatiedetail, het ‘ s vereist vanaf Python 3.7

Een besteld set is alleen mogelijk als de elementen die moeten worden opgeslagen een volgorde hebben (dwz een vergelijkingsmethode) in de eerste plaats – maar dat is niet altijd een gegeven.

De standaard set / map-implementatie in de meeste omgevingen is tegenwoordig gebaseerd op een hashtabel met autoresizing, die deze voordelen heeft:

• sneller
• gebruikt minder geheugen
• heeft de elementen niet nodig om een ordening te geven

sets moeten hoe dan ook intern worden opgeslagen met een bepaalde volgorde

Maar deze interne orde heeft niet noodzakelijk enige betekenis, en blijft ook niet hetzelfde. Een eigenschap van hashtabellen die soms onervaren ontwikkelaars in verwarring brengt, is dat de iteratievolgorde, die is is gebaseerd op de interne volgorde, volledig kan veranderen wanneer elementen worden toegevoegd (dwz wanneer een formaatwijziging wordt geactiveerd) of tussen verschillende loopt.

Opmerkingen

• Ik begrijp uw eerste opmerking niet ‘. We hebben ‘ geen vergelijkingsmethode nodig, de volgorde kan gewoon worden overgenomen, bijv. uit een lijst of een letterlijke tekenreeks {3, 5, 4}.
• @oulenz: als je ‘ niet let op de volgorde zinloos en variërend in de tijd, dan is elke set geordend, omdat er een soort iteratie-volgorde zal zijn. Maar ” geordende set ” impliceert dat de ordening semantisch is voor de elementen, en dat is niet altijd mogelijk. Ik begrijp ‘ niet echt waarom u wilt dat alle sets worden besteld.
• ” Bestelde set ” impliceert niet dat de ordening semantisch is, alleen dat er enige ordening is. Het kan me natuurlijk schelen dat zodra deze ordening tot stand is gebracht, deze behouden blijft, tenzij de inhoud ervan wordt gewijzigd.
• Sorry, ik was me niet ‘ ervan bewust dat er implicaties waren voor sommige mensen. Ik had gewoon een lineair geordende set uit de wiskunde in gedachten. en.wikipedia.org/wiki/Total_order
• @jameslarge de orderrelatie doet niet ‘ t moet mij onbekend zijn. Als ik een geordende set afleid uit een lijst, weet ik precies wat de volgorde is. Als ik voor een bepaalde volgorde wil zorgen, kan ik de set sorteren. Maar als je de ‘ de bestelling niet nodig hebt, kun je deze gewoon negeren.

Het algemene idee achter een set of een woordenboek is dat u van plan bent veel opzoekbewerkingen uit te voeren. Het is geoptimaliseerd voor genoemde opzoekbewerkingen door een hash te gebruiken die O (1) opzoeken in de meeste gevallen mogelijk maakt.

Bestelling wordt gedaan met behulp van arrays of gekoppelde lijsten en in feite bewerkingen uitvoeren waarbij volgorde belangrijk is, ze worden geoptimaliseerd voor dat zoals het toevoegen van een waarde aan het einde of begin.

Door de aard van deze twee gegevensstructuren is geen van beide geoptimaliseerd voor beide. Dit wil niet zeggen dat het niet mogelijk is, maar het betreft beide datastructuren als u zowel opzoek- als ordergebaseerde bewerkingen wilt optimaliseren.

Dus je hebt deze afweging tussen:

optimalisatie van opzoekbewerkingen < => ordergebaseerde bewerkingen < => geheugengebruik

De algemene consensus is dat je als programmeur over het algemeen voor het een of het ander wilt optimaliseren, maar niet voor beide, en zeker niemand pleit voor een verdubbeling van je geheugengebruik als je alleen om een van de twee te optimaliseren.

Dat gezegd hebbende, er zijn zijn implementaties met beide, of in ieder geval in Java, specifiek LinkedHashMap is zowel een array als een hash- gebaseerd woordenboek. Soms heb je beide nodig, maar het is raadzaam om ArrayList te gebruiken als je alleen een lijst nodig hebt en een HashMap als je alleen een woordenboek nodig hebt .

Reacties

• Huh? Een Java LinkedHashMap is niet ” zowel een array als een hash-gebaseerd woordenboek “. Het ‘ is in feite een HashMap (dwz gebruikt intern een array) bovenop een gekoppelde lijst om iteratie in invoegvolgorde mogelijk te maken.
• Lineaire gegevensstructuren zijn ‘ t de enige geordende datastructuren; binaire bomen kunnen ook worden besteld (zoals rood-zwart en AVL-bomen,). Een andere bewerking die bij de afweging kan worden betrokken, is het invoegen (arrays zijn behoorlijk efficiënt in termen van opzoeken, itereren en geheugengebruik, maar het langzaamst als het gaat om invoegen).