Jag förstår skillnaden mellan beställda och oordnade uppsättningar, och jag förstår varför vi för många ändamål inte behöver beställda uppsättningar. Men alla inställda åtgärder är fortfarande möjligt på beställda uppsättningar, och uppsättningar måste lagras internt med någon beställning ändå, så varför är inte uppsättningar ordnade som standard? Är prestandapåverkan av att bevara uppsättningen för uppsättningar för stor?
Kommentarer
- Observera att ” beställa ” av värden i en oordnad samling kan bero mer på insättningsordning och mindre (om alls) på värdena själva, vilket inte är ’ t en ordning i den mening som vanligtvis används (som kommer från den matematiska termen).
- Den här frågan kan betraktas som off-topic, eftersom den inte är ’ t om att utveckla ett visst program utan snarare språkdesign.
- @outis Jag var inte ’ inte säker på rätt underwebbplats, finns det en annan som du skulle föreslå?
Svar
Poängen är inte att omkostnaderna är särskilt stora, mer att den finns där alls .
Språkfunktioner måste alltid skapa en balans mellan kostnadseffektivitet. Ordböcker är helt grundläggande för Python-programmering, så det skulle vara väldigt dåligt för dem att vara ännu lite långsammare än att de måste vara bara för att bevara införingsordningen, när du oftast inte behöver beställa. Det var rätt beslut att kasta insättningsordern i utbyte mot något snabbare åtkomst och lämna orderbevarande datastruktur för specialklasser. Om det fanns en annan datastruktur som kunde göra allt som en dikt kan, och dikt var en mindre använd rynka i språket, saker kan se annorlunda ut.
Kommentarer
- Mitt motargument mot det skulle vara: använd en effektivare oordnad diktatyp för interna ordböcker (precis som där ’ s
dequeför att optimera prestanda i vissa andra sammanhang) men låt den huvudsakliga användarvändande diktdatatypen behålla ordningen. - Har jag också rätt när jag förstår att CPython-implementeringen av 3.6 faktiskt bevarar införingsordningen för diktar?
Svar
Du har rätt att artikeln lagras internt med en viss ordning, men den här interna ordningen är bestäms av nyckelns hashkod, vilket gör det möjligt att hämta så snabbt. Så om en uppsättning / dikt skulle beställas måste den ha en separat intern datastruktur (säg en ordnad lista med nycklar) för detta.
Detta skulle naturligtvis öka storleken. Men kanske värre, det kommer att påverka prestanda. Att ta bort ett objekt från en uppsättning är till exempel en O (1) -operation, men om den också måste ta bort nyckeln från en intern ordnad lista skulle den bli O (n). En sådan kostnad skulle vara katastrofal för vissa applikationer. Med tanke på att det är ganska sällsynt behöver du en beställd uppsättning, en sådan avvägning är inte värt det för standarduppsättningen / dicttyperna.
Svar
Din förutsättning är felaktig. Från och med Python 3.6 kommer dict ihåg deras införingsordning . Detta var en implementeringsdetalj och marknadsfördes till fullständig språkfunktion i 3.7. I 3.6, för det specifika fallet med **kwargs, är orderbevarande specifikt garanterat.
Kommentarer
- Ja, jag var inte ’ inte medveten om detta när jag ställde frågan, eftersom den ’ ännu inte är en språkfunktion, bara en implementering detalj i en implementering. Men det verkar som om ordböcker åtminstone kommer att ordnas långsiktigt och förhoppningsvis också sätter.
- @oulenz det ’ är inte längre en implementeringsdetalj, det ’ krävs per Python 3.7
Svar
En beställd set är endast möjligt när elementen som ska sparas har en ordning (dvs. en jämförelsemetod) i första hand – men det är inte alltid givet.
Standarduppsättningen / kartimplementeringen i de flesta miljöer idag är baserat på en autostorlekstabell som har dessa fördelar:
- snabbare
- använder mindre minne
- kräver inte att elementen ger en beställning
uppsättningar måste lagras internt med någon ordning ändå
Men den här interna ordningen har inte nödvändigtvis någon betydelse, och den förblir inte densamma. En egenskap hos hashtables som ibland förväxlar oerfarna utvecklare är faktiskt att iterationsordningen, som är baserad på den interna ordningen, kan förändras fullständigt när element läggs till (dvs. när en storlek ändras utlöses) eller mellan olika kör.
Kommentarer
- Jag förstår inte ’ din första kommentar. Vi behöver inte ’ för en jämförelsemetod, beställningen kan bara ärvas, t.ex. från en lista eller en sträng bokstavlig
{3, 5, 4}. - @oulenz: om du inte ’ tänker att beställningen är meningslöst och varierande över tid, då beställs varje uppsättning, för det kommer att finnas någon typ av iteringsordning. Men ” beställd uppsättning ” innebär att ordningen är semantisk för elementen, och det är inte alltid möjligt. Jag förstår inte ’ varför du vill att alla uppsättningar ska beställas.
- ” Beställd uppsättning ” innebär inte att beställningen är semantisk, bara att det finns viss ordning. Självklart bryr jag mig om att när denna beställning har upprättats behålls den, såvida inte innehållet ändras.
- Tyvärr var jag inte ’ inte medveten om att implikationen fanns för en del människor. Jag tänkte helt enkelt en linjärt ordnad uppsättning från matematik. en.wikipedia.org/wiki/Total_order
- @jameslarge orderrelationen inte ’ Jag måste vara okänd. Om jag hämtar en beställd uppsättning från en lista vet jag exakt vilken ordning den har. Om jag vill säkerställa en viss ordning kan jag sortera uppsättningen. Men om du inte behöver ’ du inte behöver beställningen kan du bara ignorera den.
Svar
Den allmänna idén bakom en uppsättning eller en ordbok är att du planerar att utföra många uppslagsåtgärder. Det är optimerat för nämnda uppslagsoperationer med hjälp av en hash som tillåter O (1) uppslag i de flesta fall.
Beställning görs med hjälp av arrays eller länkade listor och faktiskt utför operationer där ordning är viktig, de är optimerade för det som att lägga till ett värde i slutet eller början.
Av dessa två datastrukturer är ingen av dem optimerad för båda. Detta är inte för att säga att det inte är möjligt, men det involverar båda datastrukturerna om du vill att både uppslag och orderbaserade operationer ska optimeras.
Så du har denna kompromiss mellan:
optimering av uppslagsoperationer < => orderbaserade operationer < => minnesanvändning
Det allmänna samförståndet är att du som programmerare i allmänhet vill optimera för den ena eller den andra men inte båda, och absolut förespråkar ingen att fördubbla din minnesanvändning när du bara behöver för att optimera en av de två.
Som sagt, det finns implementeringar med båda, eller åtminstone i Java, särskilt LinkedHashMap är både en matris och en hash- baserad ordbok. Ibland kan du behöva båda, men det rekommenderas att använda ArrayList om du bara behöver en lista och HashMap om du bara behöver en ordlista .
Kommentarer
- va? En Java LinkedHashMap är inte ” både en matris och en hashbaserad ordbok ”. Det ’ är i grunden en HashMap (dvs. använder en array internt) överlagrad med en länkad lista för att möjliggöra iteration i införingsordning.
- Linjära datastrukturer är inte ’ t de enda beställda datastrukturerna; binära träd kan också beställas (som röda-svarta och AVL-träd,). En annan åtgärd som kan vara involverad i avvägningen är insättning (matriser är ganska effektiva när det gäller uppslag, iteration och minnesanvändning, men långsammast när det gäller insättning).