C# Academy · Oppitunti

Kokoelman valinta

Kompromissit ja suorituskyky.

Oppitunti 4/413 vaihetta

Kokoelman valinta on ilmainen C# Academy-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu C# Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C# Academy-kurssilla on yhteensä 4 oppituntia.

Yksi kysymys ensin

Kokoelman valinta alkaa yhdestä kysymyksestä: miten käsittelette tietoja? Sijainnin, avaimen vai pelkän jäsenyyden perusteella?

List, Dictionary ja HashSet vastaavat kukin erilaiseen käyttötapaan. Kun sovitatte työkalun käyttötapaan, koodinne säilyy nopeana ja selkeänä.

Käyttö sijainnin perusteella: List

Jos järjestyksellä on merkitystä ja käsittelette alkioita indeksin avulla, valitkaa List<T>. Se säilyttää lisäysjärjestyksen ja tarjoaa O(1)-aikaisen indeksoinnin.

Esimerkkejä ovat vaiheiden jono, näyttöjärjestyksessä olevat rivit tai mikä tahansa jakso, jonka käytte läpi alusta loppuun. Kaksoiskappaleet ovat sallittuja.

var steps = new List<string> { "mix", "bake", "cool" };
string first = steps[0]; // O(1) by index

Käyttö avaimen perusteella: Dictionary

Jos haette tietoja yksilöllisen tunnisteen perusteella, valitkaa Dictionary<K,V>. Se yhdistää avaimen arvoon keskimääräisellä O(1)-aikavaativuudella.

Esimerkkejä ovat käyttäjätunnuksen yhdistäminen käyttäjään, maakoodin yhdistäminen nimeen ja sanan yhdistäminen sen lukumäärään. Avain vastaa kysymykseen "mikä", ja arvo sisältää tiedot.

var users = new Dictionary<int, string> {
    [101] = "Ann",
    [102] = "Bob"
};
string name = users[101];

Jäsenyys ja yksilöllisyys: HashSet

Jos teille on tärkeää vain se, onko arvo olemassa, tai jos kaksoiskappaleet on hylättävä, valitkaa HashSet<T>. Contains-metodin keskimääräinen aikavaativuus on O(1).

Esimerkkejä ovat vieraillut URL-osoitteet, sallitut käyttöoikeudet ja yksilölliset tunnisteet. Arvoon ei liity erillistä tietoa, vaan vain alkion olemassaolo.

var visited = new HashSet<string>();
if (visited.Add(url)) {
    // first time seeing this url
}

Kustannustaulukko

Keskimääräiset kustannukset: List-rakenteen indeksoinnin aikavaativuus on O(1), mutta Contains-metodin O(n). Dictionary- ja HashSet-rakenteiden haun aikavaativuus on O(1).

List.Add-metodin aikavaativuus lopussa lisättäessä on jaksotetusti O(1), kun taas keskelle lisääminen tai keskeltä poistaminen on O(n). Dictionary- ja HashSet-rakenteiden lisäys- ja poistotoimintojen keskimääräinen aikavaativuus on O(1).

// List:       index O(1),  Contains O(n)
// Dictionary: by-key O(1), no index
// HashSet:    Contains O(1), no value, no index

List.Contains on varoitusmerkki

list.Contains-metodin toistuva kutsuminen silmukan sisällä on O(n²)-aikavaativuuden sudenkuoppa. Jokainen tarkistus käy läpi koko luettelon.

Jos jäsenyystarkistukset muodostavat suurimman osan työstä, vaihtakaa tilalle HashSet. Tämä yksittäinen muutos voi muuttaa suuren tietomäärän hitaan silmukan hetkessä toimivaksi.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var allow = new HashSet<int> { 2, 4, 6 };
        foreach (int n in new[] { 1, 2, 3, 4 })
            if (allow.Contains(n)) Console.Write(n + " ");
    }
}

Kun tarvitsette sekä avaimen että järjestyksen

Tarvitsetteko avainhaun lisäksi ennustettavan järjestyksen? Tavallinen Dictionary ei takaa järjestystä.

Harkitkaa List-rakenteen pitämistä järjestystä varten Dictionary-rakenteen rinnalla hakua varten tai käyttäkää SortedDictionary<K,V>-rakennetta, joka pitää avaimet lajitellussa järjestyksessä O(log n)-kustannuksella.

var sorted = new SortedDictionary<string, int>();
sorted["b"] = 2;
sorted["a"] = 1;
// enumerates a then b, in key order

Muistin ja suorituskyvyn kompromissit

Hajautukseen perustuvat kokoelmat vaihtavat muistia nopeuteen. Dictionary- ja HashSet-rakenteet ylläpitävät sisäisiä lokeroita ja käyttävät enemmän muistia kuin tiivis List tai taulukko.

Pienissä, muutaman alkion kokoelmissa List-rakenteen läpikäynti voi itse asiassa olla riittävä ja käyttää vähemmän muistia. Hajautuksesta on hyötyä suurissa tietomäärissä.

Ohjelmoikaa rajapintoja vasten

Metodien allekirjoitusten tulisi pyytää vähiten rajoittavaa toimivaa tyyppiä. Hyväksykää lukemista varten IEnumerable<T>, indeksoitua lukemista varten IReadOnlyList<T> ja avainkäyttöä varten IDictionary<K,V>.

Näin kutsujat irrotetaan konkreettisesta valinnastanne, joten voitte vaihtaa toteutusta myöhemmin rikkomatta allekirjoituksia.

int Sum(IEnumerable<int> values) {
    int total = 0;
    foreach (int v in values) total += v;
    return total;
}

Käytännön esimerkki

Tekstin yksilöllisten sanojen laskeminen käyttää kahta kokoelmaa yhdessä. HashSet seuraa jo nähtyjä sanoja ja Dictionary laskee esiintymät.

Kumpikin tekee yhden tehtävänsä hyvin: joukko varmistaa yksilöllisyyden ja sanakirja yhdistää sanan esiintymistiheyteen. Molempien yksittäisten operaatioiden keskimääräinen aikavaativuus on O(1).

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var counts = new Dictionary<string, int>();
        foreach (var w in "a b a c b a".Split(' '))
            counts[w] = counts.GetValueOrDefault(w) + 1;
        Console.WriteLine(counts["a"]); // 3
    }
}

Valinnan tarkistuslista

Kysykää seuraavat kysymykset järjestyksessä: Tarvitsenko avaimen ja arvon yhdistävän mapin? Käyttäkää Dictionary-rakennetta. Tarvitsenko vain yksilöllisyyttä tai jäsenyyden tarkistamista? Käyttäkää HashSet-rakennetta.

Muussa tapauksessa tarvitsetteko järjestystä ja indeksin mukaista käyttöä, mahdollisesti kaksoiskappaleineen? Käyttäkää List-rakennetta. Tämä lyhyt tarkistuslista kattaa useimmat arkipäiväiset tilanteet.

Pikatarkistus

Soveltakaa valinnan tarkistuslistaa konkreettiseen tarpeeseen.

Vastaa interaktiivisessa oppitunnissa

Kertaus

Valitkaa rakenne käyttötavan perusteella: List järjestettyihin ja indeksoituihin jaksoihin, Dictionary avain–arvo-hakuun ja HashSet yksilöllisyyteen sekä jäsenyyden tarkistamiseen.

Huomioikaa Big-O: välttäkää List.Contains-metodia suorituskyvyn kannalta kriittisissä silmukoissa, hyödyntäkää O(1)-aikaisia hajautushakuja ja ohjelmoikaa rajapintoja vasten, jotta valintanne pysyy joustavana.

Aloita maksutta

Opi C# tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 93
Oppitunnit: 346

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Kokoelman valinta” ilmainen?

Kyllä – oppitunnin ”Kokoelman valinta” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko C# Academy-kurssin, päivitä CoddyKit PROhon. C# Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Kokoelman valinta”?

Kompromissit ja suorituskyky. Harjoittelet C# Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni C# Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin C# Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Kokoelman valinta”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä C# Academy-oppitunnilla?

Kyllä. Jokainen C# Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: C# Academy