Jeg forstår forskjellen mellom ordnede og ikke-ordnede sett, og jeg forstår hvorfor vi for mange formål ikke trenger bestilte sett. Men alle angitte operasjoner er fortsatt mulig på bestilte sett, og sett må lagres internt med noen ordre uansett, så hvorfor er ikke sett bestilt som standard? Er ytelsespåvirkningen av å bevare rekkefølgen for sett for stor?
Kommentarer
- Merk at » bestilling av » av verdier i en uordnet samling kan avhenge mer av innsettingsrekkefølgen og mindre (om i det hele tatt) av selve verdiene, som ikke er ‘ t en ordning i den forstand som vanligvis brukes (som kommer fra det matematiske begrepet).
- Dette spørsmålet kan betraktes som utenfor emnet, da det ikke er ‘ t om å utvikle et bestemt program, men snarere språkdesign.
- @outis Jeg var ikke ‘ ikke sikker på riktig understed, er det en annen du vil foreslå?
Svar
Poenget er ikke at overhead er spesielt stort, mer at det er der i det hele tatt .
Språkfunksjoner må alltid finne en balanse mellom kostnadseffektivitet. Ordbøker er helt grunnleggende for Python-programmering, så det ville være veldig ille for dem å være litt tregere enn de måtte være bare for å bevare innsettingsrekkefølgen, når det meste av tiden du ikke trenger å bestille. Det var den riktige avgjørelsen å Kast innsettingsrekkefølgen mot litt raskere tilgang, og la ordrestørrende datastruktur være i spesielle klasser. Hvis det var en annen datastruktur som kunne gjøre alt som en dikt kan, og dikt var en mindre brukt rynke på språket, ting kan se annerledes ut.
Kommentarer
- Mitt motargument mot det ville være: bruk en mer effektiv, ikke-ordnet dict-datatype for interne ordbøker (akkurat som der ‘ s
dequefor å optimalisere ytelsen i visse andre sammenhenger) men la den viktigste brukervendte dikteringsdatatypen beholde orden. - Har jeg også rett i å forstå at CPython-implementeringen av 3.6 faktisk bevarer innsettingsrekkefølgen for dikt?
Svar
Du har rett i at varen er lagret internt med en viss ordre, men denne interne ordren er bestemt av nøkkelens hash-kode, som gjør det mulig å hente så raskt. Så hvis et sett / dikt skal bestilles, må det opprettholde en egen intern datastruktur (si en ordnet nøkkeliste) for dette.
Dette vil selvfølgelig øke størrelsen. Men kanskje verre, det vil påvirke ytelsen. For eksempel er å fjerne et element fra et sett en O (1) -operasjon, men hvis den også må fjerne nøkkelen fra en intern ordnet liste, vil den bli O (n). En slik kostnad vil være katastrofal for noen applikasjoner. Gitt at det er ganske sjeldent at du trenger et bestilt sett, er en slik avveining ikke verdt det for standard sett / dict-typer.
Svar
Forutsetningen din er feil. Fra og med Python 3.6 husker dict innsettingsrekkefølgen . Dette var en implementeringsdetalj, og ble promotert til full språkfunksjon i 3.7. I 3.6, for det spesifikke tilfellet av **kwargs, er ordrebevaring spesifikt garantert.
Kommentarer
- Ja, jeg var ikke ‘ ikke klar over dette da jeg stilte spørsmålet, siden det ‘ ennå ikke er en språkfunksjon, bare en implementering detalj i en implementering. Men det ser ut til at i det minste ordbøker blir ordnet langsiktig, og forhåpentligvis også setter.
- @oulenz det ‘ er ikke lenger en implementeringsdetalj, det ‘ er påkrevd fra og med Python 3.7
Svar
En bestilt sett er bare mulig når elementene som skal lagres har en bestilling (dvs. en sammenligningsmetode) i utgangspunktet – men det er ikke alltid gitt.
Standardsettet / kartimplementering i de fleste miljøer i dag er basert på en autoresizing hashtable, som har disse fordelene:
- raskere
- bruker mindre minne
- krever ikke elementene for å gi en ordre
sett må uansett lagres internt med en eller annen rekkefølge
Men denne interne ordenen har ikke nødvendigvis noen betydning, og den forblir heller ikke den samme. Faktisk er en egenskap av hashtables som noen ganger forvirrer uerfarne utviklere at iterasjonsrekkefølgen, som er basert på den interne ordren, kan endres fullstendig når elementer legges til (dvs. når en størrelse endres utløst) eller mellom forskjellige kjører.
Kommentarer
- Jeg forstår ikke ‘ jeg forstår ikke din første kommentar. Vi trenger ikke ‘ t en sammenligningsmetode, bestillingen kan bare arves, f.eks. fra en liste eller en streng bokstavelig
{3, 5, 4}. - @oulenz: hvis du ikke ‘ ikke har noe imot bestillingen meningsløst og varierende over tid, så bestilles hvert sett, fordi det vil være noen slags iterasjonsrekkefølge. Men » ordnet sett » innebærer at bestillingen er semantisk for elementene, og det er ikke alltid mulig. Jeg forstår ikke ‘ hvorfor du vil at alle sett skal bestilles.
- » Bestilt sett » innebærer ikke at bestillingen er semantisk, bare at det er noe bestilling. Selvfølgelig bryr jeg meg om at når denne bestillingen er etablert, blir den bevart, med mindre innholdet blir endret.
- Beklager, jeg var ikke ‘ t klar over at implikasjonen eksisterte for noen mennesker. Jeg hadde rett og slett i tankene et lineært ordnet sett fra matematikk. no.wikipedia.org/wiki/Total_order
- @jameslarge ordren forholdet ‘ Jeg må være ukjent. Hvis jeg henter et bestilt sett fra en liste, vet jeg nøyaktig hva ordren er. Hvis jeg vil sikre en bestemt rekkefølge, kan jeg sortere settet. Men hvis du ikke trenger ‘ ikke trenger bestillingen, kan du bare ignorere den.
Svar
Den generelle ideen bak et sett eller en ordbok er at du planlegger å utføre mange oppslagsoperasjoner. Den er optimalisert for nevnte oppslagsoperasjoner ved å bruke en hash som tillater O (1) oppslag i de fleste tilfeller.
Bestilling gjøres ved hjelp av arrays eller koblede lister og faktisk utfører operasjoner der rekkefølge er viktig, de er optimalisert for det slik som å legge til en verdi på slutten eller begynnelsen.
Av karakteren til disse to datastrukturene er ingen av dem optimalisert for begge deler. Dette er ikke å si at det ikke er mulig, men det involverer begge datastrukturer hvis du vil at både oppslag og ordrebaserte operasjoner skal optimaliseres.
Så du har denne kompromissen mellom:
optimalisering av oppslagsoperasjoner < => ordrebaserte operasjoner < => minnebruk
Den generelle konsensusen er at du som programmerer generelt vil optimalisere for den ene eller den andre, men ikke begge deler, og absolutt ingen fortaler for å doble minnebruk når du bare trenger for å optimalisere en av de to.
Når det er sagt, er implementeringer med begge deler, eller i det minste i Java, spesielt LinkedHashMap er både en matrise og en hash- basert ordbok. Noen ganger kan det hende du trenger begge deler, men det anbefales at du bruker ArrayList hvis du bare trenger en liste og HashMap hvis du bare trenger en ordbok .
Kommentarer
- Hva? En Java LinkedHashMap er ikke » både en matrise og en hash-basert ordbok «. Det ‘ er i utgangspunktet en HashMap (dvs. bruker en matrise internt) overlagret med en koblet liste for å tillate iterasjon i innsettingsrekkefølge. = «006cf49e55»>
t de eneste bestilte datastrukturene; binære trær kan også bestilles (for eksempel rød-svarte og AVL-trær,). En annen operasjon som kan være involvert i kompromisset er innsetting (matriser er ganske effektive når det gjelder oppslag, iterasjon og minnebruk, men tregest når det gjelder innsetting).