Ymmärrän eron järjestettyjen ja järjestämättömien sarjojen välillä ja ymmärrän, miksi moniin tarkoituksiin emme tarvitse järjestettyjä sarjoja. Mutta kaikki joukkooperaatiot ovat silti mahdollista järjestetyissä sarjoissa, ja sarjat on joka tapauksessa säilytettävä sisäisesti jonkin verran, joten miksi t-sarjoja ei ole järjestetty oletuksena? Onko sarjajärjestyksen säilyttämisen suorituskyky liian suuri?
Kommentit
- Huomaa, että ” ” -järjestys järjestämättömässä kokoelmassa voi riippua enemmän lisäysjärjestyksestä ja vähemmän (jos ollenkaan) itse arvoista, mikä ei ole ’ t järjestys tavallisessa mielessä (joka tulee matemaattisesta termistä).
- Tätä kysymystä voidaan pitää aiheen ulkopuolella, koska se ei ole ’ t tietyn ohjelman kehittämisestä vaan pikemminkin kielen suunnittelusta.
- @outis En ollut ’ varma oikeasta alisivustosta, onko joku toinen ehdottaako?
Vastaa
Tarkoitus ei ole, että yleiskustannukset ovat erityisen suuret, enemmän kuin että ne ovat siellä lainkaan .
Kielitoimintojen on aina oltava tasapainossa kustannustehokkuuden kanssa. Sanakirjat ovat ehdottoman välttämättömiä Python-ohjelmoinnille, joten olisi erittäin huono, että ne olisivat jopa hieman hitaampia kuin niiden on oltava vain lisäysjärjestyksen säilyttämiseksi, kun suurimman osan ajasta et tarvitse tilaamista. Se oli oikea päätös Hylkää lisäysjärjestys vastineeksi nopeammalle pääsylle ja jätä tilauksia säilyttävä tietorakenne erityisluokille.Jos olisi olemassa jokin toinen tietorakenne, joka voisi tehdä kaiken, mitä sanelu voi, ja sanelu olisi kielen vähemmän käytetty ryppy, asiat saattaa näyttää erilaiselta.
Kommentit
- Vastaväitteeni olisi: Käytä sisäisissä sanakirjoissa tehokkaampaa järjestämätöntä dikttatyyppiä (aivan kuten sielläkin) ’ s
dequesuorituskyvyn optimoimiseksi tietyissä muissa yhteyksissä), mutta anna pääkäyttäjälle suunnatun dict-tietotyypin säilyttää järjestys. - Olen myös oikeassa ymmärtäessäni, että 3.6: n CPython-toteutus tosiasiallisesti säilyttää lisäysjärjestyksen diktejä?
Vastaa
Oletko oikeassa, että kohde on varastossa sisäisesti jonkin verran, mutta tämä sisäinen järjestys on määritetään avaimen tiivistekoodilla, mikä sallii haun niin nopeasti. Joten jos sarja / dict pitäisi tilata, sen on ylläpidettävä erillistä sisäistä tietorakennetta (esimerkiksi järjestetty avainluettelo).
Tämä tietysti lisäisi kokoa. Mutta ehkä pahempaa, se vaikuttaa suorituskykyyn. Esimerkiksi kohteen poistaminen joukosta on O (1) -operaatio, mutta jos sen on myös poistettava avain sisäisestä järjestyslistasta, siitä tulee O (n). Tällaiset kustannukset olisivat katastrofaalisia joissakin sovelluksissa. Koska tarvitset tilattua sarjaa melko harvoin, tällainen kompromissi ei ole sen arvoista tavallisille set / dict-tyypeille.
Vastaa
Oletuksesi on väärä. Python 3.6: sta alkaen dict s muistaa lisäysjärjestyksensä . Tämä oli toteutuksen yksityiskohtia, ja se ylennettiin täydellisen kielen ominaisuudeksi 3.7. Kohdassa 3.6 tilauksen säilyminen on erityisesti taattu **kwargs -tapauksessa.
Kommentit
- Kyllä, en ollut ’ tiennyt tätä, kun esitin kysymyksen, koska se ’ ei ole vielä kieliominaisuus, vain toteutus yksityiskohtaisesti yhdessä toteutuksessa. Näyttää kuitenkin siltä, että ainakin sanakirjoista tulee pitkäaikaisia ja toivottavasti myös asetettavia.
- @oulenz it ’ ei ole enää toteutuksen yksityiskohtia, se ’ vaaditaan Python 3.7: stä lähtien
vastaus
tilattu set on mahdollista vain, kun tallennettavilla elementeillä on ensin järjestys (ts. vertailumenetelmä) – mutta se ei ole aina annettu.
Oletusarvoinen set / map-toteutus useimmissa ympäristöissä on nykyään perustuu autoresizing hashtable -ohjelmaan, jolla on seuraavat edut:
- nopeampi
- käyttää vähemmän muistia
- ei vaadi elementtejä järjestämään
sarjat on silti tallennettava sisäisesti jokaisessa järjestyksessä.
Mutta tällä sisäisellä järjestyksellä ei ole välttämättä mitään merkitystä, eikä se pysy ennallaan. Yksi hashtable-ominaisuus, joka joskus hämmentää kokematonta kehittäjää, on se, että iterointijärjestys, joka perustuu sisäiseen järjestykseen, voi muuttua kokonaan, kun elementtejä lisätään (ts. Kun koon muutos käynnistetään) tai eri välillä kulkee.
kommentit
- En ymmärrä ensimmäistä huomautustasi ’. Emme tarvitse ’ vertailumenetelmää, tilaus voidaan vain periä, esim. luettelosta tai merkkijonosta kirjaimellinen
{3, 5, 4}. - @oulenz: jos et ’ pidä mielessä, että tilaus on merkityksetön ja vaihteleva ajan myötä, jokainen sarja järjestetään, koska siellä on jonkinlainen iteraatiojärjestys. Mutta ” järjestetty joukko ” tarkoittaa, että järjestys on elementtien kannalta semanttinen, eikä se ole aina mahdollista. En todellakaan ymmärrä ’, miksi haluat kaikkien sarjojen järjestämisen.
- ” Järjestetty sarja ” ei tarkoita, että järjestys on semanttinen, vaan että järjestystä on jonkin verran. Tietysti välitän siitä, että kun tämä järjestys on muodostettu, se säilyy, ellei sen sisältöä muuteta.
- Valitettavasti en ollut ’ tietoinen siitä, että implikaatio oli olemassa joillekin ihmisille. Minulla oli yksinkertaisesti mielessä lineaarisesti järjestetty sarja matematiikasta. fi.wikipedia.org/wiki/Total_order
- @jameslarge tilaussuhde ei ole ’ Minun ei tarvitse olla tuntematon. Jos johdan järjestetyn joukon luettelosta, tiedän tarkalleen, mikä on sen järjestys. Jos haluan varmistaa tietyn järjestyksen, voin lajitella sarjan. Mutta jos et ’ ei tarvitse järjestystä, voit vain ohittaa sen.
Vastaa
Joukon tai sanakirjan takana on, että aiot suorittaa paljon hakutoimintoja. Se on optimoitu mainituille hakutoiminnoille käyttämällä hashia, joka sallii O (1) -haun useimmissa tapauksissa.
Tilaus tehdään matriisien tai linkitettyjen luetteloiden avulla ja itse asiassa suoritetaan toimintoja, joissa järjestys on tärkeää, ne optimoidaan että kuten arvon lisääminen loppuun tai alkuun.
Näiden kahden tietorakenteen luonteen vuoksi kumpikaan ei ole optimoitu molemmille. Tämä ei tarkoita, että se ei ole mahdollista, mutta siihen liittyy molemmat tietorakenteet, jos haluat, että sekä haku- että tilauspohjaiset toiminnot optimoidaan.
Joten sinulla on tämä kompromissi:
hakutoiminnon optimointi < => tilauspohjaiset toiminnot < => muistin käyttö
Yleinen yksimielisyys on, että ohjelmoijana haluat yleensä optimoida jommankumman, mutta et molempia, eikä kukaan ehdottomasti suosittele muistin käytön kaksinkertaistamista, kun tarvitset vain optimoida toinen näistä kahdesta.
Siitä huolimatta on toteutuksia, joissa molemmat tai ainakin Java, erityisesti LinkedHashMap on sekä taulukko että hash- sanakirja. Joskus tarvitset molempia, mutta on suositeltavaa käyttää ArrayList, jos tarvitset vain luetteloa ja HashMap, jos tarvitset vain sanakirjaa .
Kommentit
- Huh? Java LinkedHashMap ei ole ” sekä taulukko että hash-pohjainen sanakirja ”. Se ’ on pohjimmiltaan HashMap (eli käyttää sisäisesti taulukkoa), joka on asetettu linkitetyllä luettelolla iteroinnin sallimiseksi lisäysjärjestyksessä.
- Lineaariset tietorakenteet eivät ole ’ t ainoat tilatut tietorakenteet; binaarisia puita voidaan myös tilata (kuten punamusta ja AVL-puut). Toinen operaatio, joka voi olla mukana kompromississa, on lisäys (taulukot ovat varsin tehokkaita etsinnässä, iteroinnissa ja muistin käytössä, mutta hitaimmin lisäyksessä).