Megértem a különbséget a rendezett és a rendezetlen halmazok között, és megértem, hogy sok célból miért nincs szükségünk rendezett halmazokra. De az összes halmazművelet még mindig rendelhető halmazokon lehetséges, és a készleteket egyébként belső rendben kell tárolni, bizonyos sorrenddel, akkor miért nem rendezik a t készleteket alapértelmezés szerint? Túl nagy a halmazok sorrendjének megőrzése a teljesítményre nézve?
Megjegyzések
- Ne feledje, hogy a ” az értékek rendezése ” egy rendezetlen gyűjteményben inkább függhet a beszúrási sorrendtől, és kevésbé (ha egyáltalán) magától az értékektől, ami nem ‘ t a szokásos értelemben vett sorrend (amely a matematikai kifejezésből származik).
- Ez a kérdés témán kívülinek tekinthető, mivel nem ‘ t egy adott program fejlesztéséről, inkább nyelvtervezésről.
- @outis Nem voltam biztos abban, hogy ‘ a megfelelő alwebhelyről van-e szó, van-e még egy javasolná?
Válasz
A lényeg nem az, hogy a rezsi különösen nagy, inkább az, hogy ott van egyáltalán .
A nyelvi jellemzőknek mindig meg kell találniuk a költséghatékonyság egyensúlyát. A szótárak alapvető fontosságúak a Python programozás szempontjából, ezért nagyon rossz lenne, ha a beillesztési sorrend megőrzése érdekében még kissé lassabbak lennének, mint amekkorák, amikor legtöbbször nem kell rendelni. Helyes döntés volt a kissé gyorsabb hozzáférés fejében dobja el a beillesztési sorrendet, és hagyja a sorrendmegőrző adatstruktúrát a speciális osztályok számára. Ha létezne más adatstruktúra, amely megteheti mindazt, amit egy dikt képes, és a dict a nyelv kevésbé használt ránca, másképp nézhet ki.
Megjegyzések
- Ellenérvem a következő lenne: hatékonyabb rendezetlen diktált adattípust használj a belső szótárakhoz (akárcsak ott ‘ s
dequea teljesítmény optimalizálása érdekében bizonyos más kontextusokban), de hagyja, hogy a fő felhasználó felé fordított dict adattípus megőrizze a sorrendet. - Azt is jól értem, hogy a 3.6 CPython-implementációja valóban megőrzi-e a beillesztési sorrendet dict?
Válasz
Igazad van, hogy az elemet belső sorrendben tárolják, de ez a belső sorrend a kulcs hash-kódja határozza meg, ami lehetővé teszi a visszakeresés ilyen gyors elvégzését. Tehát ha egy készletet / diktumot kellene rendelni, akkor ehhez külön belső adatstruktúrát (mondjuk egy sorrendben szereplő kulcslistát) kell fenntartania.
Ez természetesen növelné a méretet. De talán még rosszabb, hogy ez hatással lesz a teljesítményre. Például egy elem eltávolítása egy halmazból O (1) művelet, de ha el kell távolítania a kulcsot egy belső rendezett listáról is, akkor O (n) lesz. Ez a költség egyes alkalmazásoknál katasztrofális lenne. Tekintettel arra, hogy elég ritkán van szükség megrendelt készletre, ilyen kompromisszumot nem érdemes megtenni a szokásos set / dict típusoknál.
Válasz
A feltevése helytelen. A Python 3.6 verziójától kezdve dict s emlékeznek a beillesztési sorrendjükre . Ez egy megvalósítási részlet volt, és a 3.7-ben teljes nyelvűvé emelték. A 3.6-os szakaszban a **kwargs konkrét esetre a megrendelések megőrzése kifejezetten garantált.
Megjegyzések
- Igen, nem voltam ‘ tudomásom erről, amikor feltettem a kérdést, mivel ‘ még nem nyelvi funkció, csak megvalósítás részleteket egy megvalósításban. De úgy tűnik, hogy legalább a szótárak hosszú távra rendezetté válnak, és remélhetőleg beállítódnak is.
- @oulenz it ‘ s már nem a megvalósítás részlete, hanem ‘ szükséges a Python 3.7-től kezdődően
Válasz
Rendelt A set csak akkor lehetséges, ha a tárolásra kerülő elemek eleve sorrenddel (azaz összehasonlítási módszerrel) rendelkeznek – de ez nem mindig adott.
Az alapértelmezett set / map megvalósítás manapság a legtöbb környezetben egy autoresizing hashtable alapján, amelynek ezek az előnyei vannak:
- gyorsabban
- kevesebb memóriát használ
- nem szükséges, hogy az elemek rendelést adjanak
a készleteket különben is belső sorrendben kell tárolni.
De ennek a belső rendnek nincs feltétlenül jelentése, és nem is marad ugyanaz. A hashtable-ek egyik tulajdonsága, amely néha megzavarja a tapasztalatlan fejlesztőket, az az, hogy az iterációs sorrend, amely a belső rendezésen alapul , teljesen megváltozhat, amikor elemeket adnak hozzá (azaz amikor átméretezést indítanak), vagy különböző fut.
Megjegyzések
- Nem értem ‘ az első megjegyzésedet. Nincs szükségünk összehasonlítási módszerre, a rendelés csak öröklődhet, pl. listából vagy egy karakterláncból literál
{3, 5, 4}. - @oulenz: ha nem ‘ nem bánja a rendező lényt értelmetlen és változó az idő múlásával, akkor minden készlet rendeződik, mert valamilyen fajta iterációs sorrend lesz. De a ” rendezett set ” azt jelenti, hogy a sorrend szemantikus az elemek számára, és ez nem mindig lehetséges. Nem igazán értem ‘, hogy miért akarod az összes készletet rendezni.
- ” Rendezett készlet ” nem jelenti azt, hogy a sorrend szemantikai, csak hogy van némi sorrend. Természetesen érdekel, hogy ha ez a sorrend létrejött, akkor megmarad, hacsak nem módosítják a tartalmát.
- Sajnálom, nem voltam ‘ tudatában annak, hogy implikáció létezik néhány embernek. Egyszerűen a matematikából lineárisan rendezett halmazra gondoltam. hu.wikipedia.org/wiki/Total_order
- @jameslarge a sorrend relációja nem ‘ nekem ismeretlennek kell lennie. Ha egy rendezett készletet levezetem egy listából, pontosan tudom, hogy mi annak a sorrendje. Ha biztosítani akarok egy bizonyos sorrendet, rendezhetem a készletet. De ha nincs ‘ szüksége a sorrendre, akkor egyszerűen figyelmen kívül hagyhatja.
Válasz
Egy készlet vagy egy szótár mögött az az általános elképzelés áll, hogy sok keresési műveletet tervez végrehajtani. Az említett keresési műveletekhez egy hash segítségével optimalizálták, amely lehetővé teszi az O (1) keresést a legtöbb esetben.
A sorrend tömbök vagy összekapcsolt listák segítségével történik, és valójában olyan műveleteket hajtanak végre, ahol a sorrend fontos, optimalizálják őket ahhoz , például egy érték hozzáadásához a végén vagy az elején.
E két adatstruktúra jellege miatt egyik sem optimális mindkettőre. Ez nem azt jelenti, hogy ez nem lehetséges, de mindkét adatstruktúrát magában foglalja, ha a keresési és a rendelésalapú műveleteket egyaránt optimalizálni szeretné.
Tehát ez a kompromisszum a következők között van:
keresési műveletek optimalizálása < => rendelésalapú műveletek < => memóriahasználat
Az általános konszenzus az, hogy programozóként általában egyikre vagy másikra akar optimalizálni, de nem mindkettőre, és természetesen senki sem javasolja a memóriahasználat megkétszerezését, amikor csak szüksége van hogy optimalizálja a kettő egyikét.
Ennek ellenére vannak megvalósítások mindkettővel, vagy legalábbis a Java-ban, konkrétan a LinkedHashMap egyben tömb és hash- alapú szótár. Néha szükség lehet mindkettőre, de tanácsos használni az ArrayList szolgáltatást, ha csak listára van szüksége, és egy HashMap -re, ha csak szótárra van szüksége .
Megjegyzések
- Huh? A Java LinkedHashMap nem ” mind tömb, mind hash-alapú szótár “. ‘ alapvetően egy HashMap (azaz egy tömböt használ belsőleg), összekapcsolva egy összekapcsolt listával, lehetővé téve az iterációt beszúrási sorrendben.
- A lineáris adatstruktúrák ‘ t az egyetlen rendezett adatstruktúra; bináris fák is rendelhetők (például vörös-fekete és AVL fák,). Egy másik művelet, amely részt vehet a kompromisszumban, a beillesztés (a tömbök elég hatékonyak a keresés, az iteráció és a memóriahasználat szempontjából, de a leglassabbak, ha a beillesztésről van szó).