Jeg forstår forskellen mellem ordnede og ikke-ordnede sæt, og jeg forstår, hvorfor vi til mange formål ikke har brug for bestilte sæt. Men alle indstillede operationer er stadig muligt på bestilte sæt, og sæt skal alligevel gemmes internt med en rækkefølge, så hvorfor er ikke sæt bestilt som standard? Er præstationseffekten af at bevare rækkefølgen af sæt for stor?
Kommentarer
- Bemærk, at ” bestilling af ” af værdier i en uordnet samling kan afhænge mere af indsættelsesrækkefølgen og mindre (overhovedet) af selve værdierne, hvilket ikke er ‘ t en rækkefølge i den forstand, der normalt bruges (som kommer fra det matematiske udtryk).
- Dette spørgsmål kan betragtes som uden for emnet, da det ikke er ‘ t om at udvikle et bestemt program, men snarere sprogdesign.
- @outis Jeg var ikke ‘ ikke sikker på, at det rigtige underwebsted er, er der en anden, som du vil foreslå?
Svar
Pointen er ikke, at omkostningerne er særlig store, mere at det er der overhovedet .
Sprogfunktioner skal altid finde en balance mellem omkostningseffektivitet. Ordbøger er helt grundlæggende for Python-programmering, så det ville være meget dårligt for dem at være endnu lidt langsommere, end de skulle være bare for at bevare indsættelsesrækkefølgen, når det meste af tiden ikke behøver at bestilles. Det var den rigtige beslutning at kassér indsættelsesrækkefølgen til gengæld for lidt hurtigere adgang, og efterlad ordrestyrende datastruktur for specielle klasser. Hvis der var en anden datastruktur, der kunne gøre alt, hvad en dikt kan, og dikt var en mindre anvendt rynke på sproget, ting kan se anderledes ud.
Kommentarer
- Mit modargument til det ville være: Brug en mere effektiv, ikke-ordnet dict-datatype til interne ordbøger (ligesom der ‘ s
dequefor at optimere ydeevnen i visse andre sammenhænge) men lad den primære bruger-vendende diktatype bevare rækkefølgen. - Har jeg også ret i at forstå, at CPython-implementeringen af 3.6 faktisk bevarer indsættelsesrækkefølgen for dikter?
Svar
Du er korrekt, at varen gemmes internt med en vis rækkefølge, men denne interne ordre er bestemt af hash-koden på nøglen, hvilket er det, der gør det muligt at hente så hurtigt. Så hvis et sæt / dikt skal bestilles, skal det opretholde en separat intern datastruktur (f.eks. En ordnet nøgleliste) til dette.
Dette vil selvfølgelig øge størrelsen. Men måske værre, det vil påvirke ydeevnen. For eksempel er fjernelse af et element fra et sæt en O (1) -operation, men hvis det også skal fjerne nøglen fra en intern ordnet liste, bliver det O (n). En sådan pris ville være katastrofal for nogle applikationer. I betragtning af at det er ret sjældent, har du brug for et ordnet sæt, en sådan kompromis er ikke det værd for standard sæt / dict-typerne.
Svar
Din forudsætning er forkert. Fra og med Python 3.6 husker dict deres indsætningsrækkefølge . Dette var en implementeringsdetalje og blev forfremmet til fuld sprogfunktion i 3.7. I 3.6, for det specifikke tilfælde af **kwargs, er bevarelse af ordre specifikt garanteret.
Kommentarer
- Ja, jeg var ikke ‘ ikke klar over dette, da jeg stillede spørgsmålet, da det ‘ endnu ikke er en sprogfunktion, bare en implementering detaljer i en implementering. Men det ser ud til, at i det mindste ordbøger bliver ordnet på lang sigt og forhåbentlig også sætter.
- @oulenz det ‘ er ikke længere en implementeringsdetalje, det ‘ er påkrævet fra Python 3.7
Svar
En bestilt sæt er kun muligt, når elementerne, der skal gemmes, har en ordre (dvs. en sammenligningsmetode) i første omgang – men det er ikke altid givet.
Standardsætt / kortimplementering i de fleste miljøer i dag er baseret på en autostørrelses-hashtable, som har disse fordele:
- hurtigere
- bruger mindre hukommelse
- behøver ikke elementerne at give en ordre
sæt skal alligevel gemmes internt med en rækkefølge
Men denne interne orden har ikke nødvendigvis nogen betydning, og den forbliver heller ikke den samme. Faktisk er en egenskab ved hashtables, der undertiden forveksler uerfarne udviklere, at iterationsrækkefølgen, som er baseret på den interne rækkefølge, kan ændre sig fuldstændigt, når elementer tilføjes (dvs. når en størrelse ændres) eller mellem forskellige kører.
Kommentarer
- Jeg forstår ikke ‘ forstår ikke din første bemærkning. Vi behøver ikke ‘ en sammenligningsmetode, bestillingen kunne bare arves, f.eks. fra en liste eller en streng bogstavelig
{3, 5, 4}. - @oulenz: hvis du ikke ‘ ikke har noget imod ordren meningsløs og varierende over tid, så bestilles hvert sæt, fordi der vil være en slags slags iterationsrækkefølge. Men ” bestilt sæt ” indebærer, at ordren er semantisk for elementerne, og det er ikke altid muligt. Jeg forstår ikke ‘ hvorfor du ønsker, at alle sæt skal bestilles.
- ” Bestilt sæt ” betyder ikke, at bestillingen er semantisk, bare at der er en rækkefølge. Selvfølgelig er jeg opmærksom på, at når denne ordre er oprettet, bevares den, medmindre dens indhold ændres.
- Beklager, jeg var ikke ‘ t klar over, at der var implikationer for nogle mennesker. Jeg havde simpelthen et lineært ordnet sæt fra tankerne i tankerne. da.wikipedia.org/wiki/Total_order
- @jameslarge rækkefølgen ikke ‘ Jeg behøver ikke at være ukendt. Hvis jeg udleder et bestilt sæt fra en liste, ved jeg nøjagtigt, hvad ordren er. Hvis jeg vil sikre en bestemt rækkefølge, kan jeg sortere sættet. Men hvis du ikke ‘ ikke har brug for ordren, kan du bare ignorere den.
Svar
Den generelle idé bag et sæt eller en ordbog er, at du planlægger at udføre mange opslag. Det er optimeret til nævnte opslagsoperationer ved hjælp af en hash, der tillader O (1) opslag i de fleste tilfælde.
Bestilling foretages ved hjælp af arrays eller sammenkædede lister og udfører faktisk operationer, hvor rækkefølge er vigtig, de er optimeret til at såsom at tilføje en værdi i slutningen eller begyndelsen.
Af karakteren af disse to datastrukturer er ingen af dem optimeret til begge. Dette er ikke for at sige, at det ikke er muligt, men det involverer begge datastrukturer, hvis du vil optimere både opslags- og ordrebaserede operationer.
Så du har denne kompromis mellem:
optimering af opslagsoperationer < => ordrebaserede operationer < => hukommelsesforbrug
Den generelle enighed er, at du som programmør generelt vil optimere til den ene eller den anden, men ikke begge dele, og bestemt ingen går ind for at fordoble dit hukommelsesforbrug, når du kun har brug for for at optimere en af de to.
Når det er sagt, er der implementeringer med begge eller i det mindste i Java, specifikt LinkedHashMap er både en matrix og en hash- baseret ordbog. Nogle gange har du muligvis brug for begge dele, men det anbefales at bruge ArrayList hvis du kun har brug for en liste og HashMap hvis du kun har brug for en ordbog .
Kommentarer
- Hvad? En Java LinkedHashMap er ikke ” både en matrix og en hashbaseret ordbog “. Det ‘ er grundlæggende en HashMap (dvs. bruger et array internt) overlejret med en sammenkædet liste for at tillade iteration i indsættelsesrækkefølge.
- Lineære datastrukturer er ikke ‘ t de eneste bestilte datastrukturer; binære træer kan også bestilles (såsom rød-sort og AVL træer). En anden operation, der kan være involveret i afvejningen, er indsættelse (arrays er ret effektive med hensyn til opslag, iteration og hukommelsesforbrug, men langsomst når det kommer til indsættelse).