Proč nejsou sady Python a slovníky standardně seřazeny?

Nejde o to, že režie je obzvláště velká, spíše o to, že je tam vůbec .

Jazykové funkce musí vždy dosáhnout rovnováhy mezi efektivitou nákladů. Slovníky jsou pro programování v Pythonu naprosto zásadní, takže by bylo velmi špatné, aby byly ještě o něco pomalejší, než by musely být jen pro zachování pořadí vkládání, když většinu času objednávání nepotřebujete. Bylo správné rozhodnutí zahodit pořadí vložení na oplátku pro mírně rychlejší přístup a ponechat datovou strukturu zachovávající pořadí pro speciální třídy. Pokud by existovala jiná datová struktura, která by dokázala vše, co dikt umí, a dikt byl méně používanou vráskou jazyka, věci může vypadat jinak.

Komentáře

• Můj protiargument k tomu by byl: použít účinnější neuspořádaný datový typ dict pro interní slovníky (stejně jako tam ‚ s deque k optimalizaci výkonu v určitých dalších kontextech), ale nechte hlavní datový typ, který je zaměřen na uživatele, zachovat pořádek.
• Mám také pravdu, když chápu, že implementace 3.6 CPython ve skutečnosti zachovává pořadí vložení dicts?

Máte pravdu, že položky jsou interně ukládány s nějakou objednávkou, ale tato interní objednávka je určeno hashovacím kódem klíče, což umožňuje rychlé vyhledávání. Pokud by měl být set / dict objednán, bylo by pro to nutné udržovat samostatnou vnitřní datovou strukturu (řekněme uspořádaný seznam klíčů).

To by samozřejmě zvětšilo velikost. Ale možná horší bude mít vliv na výkon. Například odebrání položky ze sady je operace O (1), ale pokud musí také odebrat klíč z interního seřazeného seznamu, stane se z ní O (n). Taková cena by byla pro některé aplikace katastrofální. Vzhledem k tomu, že je poměrně vzácné, že potřebujete objednanou sadu, takové kompromisní řešení pro standardní typy set / dict nestojí za to.

Vaše předpoklad je nesprávná. Od verze Python 3.6 si dict pamatují jejich pořadí vkládání . Jednalo se o implementační detail a v 3.7 byl povýšen na funkci celého jazyka. V 3.6 je pro konkrétní případ **kwargs výslovně zaručeno zachování pořadí.

Komentáře

• Ano, nevěděl jsem o tom ‚, když jsem se zeptal na otázku, protože ‚ ještě není jazyková funkce, pouze implementace detail v jedné implementaci. Ale zdá se, že přinejmenším slovníky budou objednány dlouhodobě a doufejme, že také nastaví.
• @oulenz it ‚ již není detail implementace, ‚ s požadováno od verze Pythonu 3.7

objednaný sada je možná pouze v případě, že prvky, které mají být uloženy, mají na prvním místě uspořádání (tj. metodu porovnání) – ale to není vždy dané.

Výchozí implementace sady / mapy ve většině prostředí je dnes na základě hashtable s autoresizingem, který má tyto výhody:

• rychlejší
• využívá méně paměti
• nevyžaduje elementy k zajištění objednávání

sady musí být stejně uloženy interně v určitém pořadí

Ale tento vnitřní řád nemusí nutně mít žádný význam, ani nezůstává stejný. Jednou z vlastností hashtable, která někdy nezkušeným vývojářům dělá starosti, je to, že pořadí iterací, které je založeno na interním uspořádání, se může úplně změnit, když jsou přidány prvky (tj. Když je spuštěna změna velikosti) nebo mezi různými běží.

Komentáře

• Nerozumím vaší první poznámce ‚. ‚ nepotřebujeme srovnávací metodu, objednávání lze jednoduše zdědit, např. ze seznamu nebo řetězcového literálu {3, 5, 4}.
• @oulenz: pokud vám ‚ nevadí objednávání nesmyslné a měnící se v čase, pak je každá sada uspořádána, protože bude existovat nějaký druh iteračního pořadí. “ objednaná sada “ však naznačuje, že uspořádání je pro prvky sémantické, a to není vždy možné. Nerozumím ‚ tomu, proč chcete objednávat všechny sady.
• “ Objednaná sada “ neznamená, že objednávka je sémantická, pouze že existuje nějaká objednávka. Samozřejmě mi záleží na tom, aby jakmile je toto uspořádání vytvořeno, bylo zachováno, pokud nebude změněn jeho obsah.
• Je nám líto, nebyl jsem si ‚ vědom toho, že implikace existuje pro některé lidi. Jednoduše jsem měl na mysli lineárně uspořádanou množinu z matematiky. en.wikipedia.org/wiki/Total_order
• @jameslarge vztah objednávky ‚ Nemusím být pro mě neznámý. Pokud odvozím uspořádanou množinu ze seznamu, vím přesně, jaké je její pořadí. Pokud chci zajistit určitou objednávku, mohu setřídit sadu. Pokud ale ‚ objednávku nepotřebujete, můžete ji jednoduše ignorovat.

Obecná myšlenka za sadou nebo slovníkem je, že plánujete provádět mnoho vyhledávacích operací. Je optimalizován pro uvedené vyhledávací operace pomocí hash, který ve většině případů umožňuje vyhledávání O (1).

Objednávka se provádí pomocí polí nebo propojených seznamů a ve skutečnosti provádění operací, kde je důležité pořadí, jsou optimalizovány pro to například přidání hodnoty na konec nebo na začátek.

Podle povahy těchto dvou datových struktur není ani jedna optimalizována pro obě. Není možné říci, že to není možné, ale pokud chcete optimalizovat operace vyhledávání i objednávek, zahrnuje obě datové struktury.

Takže máte tento kompromis mezi:

optimalizací vyhledávací operace < => objednávkovými operacemi < => využití paměti

Obecná shoda je v tom, že jako programátor obecně chcete optimalizovat pro jeden nebo druhý, ale ne pro oba, a rozhodně nikdo neobhajuje zdvojnásobení využití paměti, když potřebujete pouze optimalizovat jednu ze dvou.

To znamená, že existují implementace s oběma, nebo alespoň v Javě, konkrétně LinkedHashMap je pole i hash- založený slovník. Někdy možná budete potřebovat obojí, ale doporučuje se použít ArrayList, pokud potřebujete pouze seznam, a HashMap, pokud potřebujete pouze slovník .

Komentáře

• Co? Java LinkedHashMap není “ pole ani hashový slovník „. Je to ‚ s v podstatě HashMap (tj. Interně používá pole) navrstvený na propojený seznam, který umožňuje iteraci v pořadí vložení.
• Lineární datové struktury nejsou = „006cf49e55“>