Uudelleenmitoitus ja kuormituskerroin
Suorituskyvyn säätö.
Uudelleenmitoitus ja kuormituskerroin 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.
Mikä on täyttöaste
Täyttöaste on tallennettujen alkioiden suhde ämpäreiden määrään: alpha = size / capacity. Se ilmaisee, kuinka täynnä taulu on, ja vaikuttaa suoraan suorituskykyyn.
Miksi täyttöasteella on merkitystä
Täyttöasteen kasvaessa ämpäreihin muodostuu pidempiä ketjuja (tai koettelut kasautuvat), joten operaatiot hidastuvat.
- Pieni alpha: nopea, mutta tuhlaa muistia
- Suuri alpha: tiivis, mutta hidas
Ketjutuksessa yleinen tavoite on 0.75.
Täyttöasteen laskeminen
Laske täyttöaste liukulukusuhteena, jotta voit verrata sitä kynnysarvoon.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Milloin kokoa muutetaan
Tarkista jokaisen lisäyksen jälkeen, ylittääkö täyttöaste kynnysarvon. Jos ylittää, kasvata taulua (yleensä kaksinkertaista kapasiteetti) ja hajauta alkiot uudelleen.
#include <stdio.h>
int should_grow(unsigned size, unsigned cap) {
return (double)size / cap > 0.75;
}
int main(void) {
printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
printf("%d\n", should_grow(10, 16)); /* 0.625 -> 0 */
return 0;
}Uudelleenhajautus selitettynä
Ämpäreitä ei voi kopioida suoraan, koska kunkin avaimen indeksi riippuu kapasiteetista. Uudelleenhajautuksessa jokaisen avaimen ämpäri lasketaan uudelleen uuden kapasiteetin perusteella, minkä jälkeen alkio lisätään uudelleen.
Koon muuttava funktio
Varaa uusi, suurempi ämpäritaulukko; käy kaikki vanhat solmut läpi ja siirrä ne uuteen taulukkoon käyttäen uutta kapasiteettia; vaihda sitten taulukot keskenään. Tässä on indeksin uudelleenlaskennan ydin.
#include <stdio.h>
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
const char *key = "session";
unsigned old_cap = 8, new_cap = 16;
printf("old slot = %lu\n", djb2(key) % old_cap);
printf("new slot = %lu\n", djb2(key) % new_cap);
return 0;
}Solmujen siirtäminen ilman uudelleenvarausta
Ketjutuksessa voit siirtää olemassa olevat solmut uuteen taulukkoon sen sijaan, että varaisit uusia. Irrota kukin solmu, laske sen ämpäri uudelleen ja lisää se listan alkuun.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}
int main(void) {
Node *old[2] = {0};
Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
Node *new_b[4] = {0};
/* move node a */
unsigned i = djb2(a->key) % 4;
a->next = new_b[i]; new_b[i] = a;
printf("moved to slot %u\n", i);
return 0;
}Kasvustrategia
Kapasiteetin kaksinkertaistaminen pitää lisäyksen jaksotetun aikavaativuuden arvossa O(1): vaikka koon muuttaminen on O(n), sitä tehdään niin harvoin, että yhden lisäyksen keskimääräinen kustannus pysyy vakiona.
Kahden potenssit mahdollistavat myös nopean AND-maskin käytön.
#include <stdio.h>
int main(void) {
unsigned cap = 8;
for (int i = 0; i < 4; i++) {
printf("capacity = %u\n", cap);
cap *= 2;
}
return 0;
}Pienentäminen
Voit halutessasi pienentää taulua, kun täyttöaste laskee liian pieneksi (esimerkiksi alle arvon 0.1) useiden poistojen jälkeen. Pienentäminen vapauttaa muistia, mutta aiheuttaa uudelleenhajautuskustannuksen, joten tee se harkiten jatkuvan koon muuttamisen välttämiseksi.
Avoin hajautus ja täyttöaste
Avoimeen hajautukseen perustuvat taulut ovat paljon herkempiä täyttöasteelle. Suorituskyky romahtaa alfan lähestyessä arvoa 1, joten niiden kokoa muutetaan yleensä täyttöasteen ollessa 0.5–0.7, eli pienempi kuin ketjutuksen 0.75.
Jaksotetun kustannuksen esimerkki
Simuloi lisäyksiä, joissa kapasiteetti kaksinkertaistetaan täyttöasteen ollessa 0.75, ja laske työn kokonaismäärä. Näin näet keskimääräisen kustannuksen pysyvän pienenä.
#include <stdio.h>
int main(void) {
unsigned cap = 4, size = 0;
long work = 0;
for (int i = 0; i < 100; i++) {
size++; work++; /* the insert */
if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
}
printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
return 0;
}Pikatarkistus
Testaa ymmärryksesi koon muuttamisesta.
Kertaus
Opit säätämään hajautustaulun suorituskykyä.
- Täyttöaste = koko / kapasiteetti
- Muuta kokoa, kun täyttöaste ylittää kynnysarvon (ketjutuksessa noin 0.75)
- Hajauta alkiot uudelleen, koska indeksit riippuvat kapasiteetista
- Kapasiteetin kaksinkertaistaminen antaa lisäyksille jaksotetun aikavaativuuden O(1)
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
- 39
- Oppitunnit
- 144
Usein kysytyt kysymykset
Onko oppitunti ”Uudelleenmitoitus ja kuormituskerroin” ilmainen?
Kyllä – oppitunnin ”Uudelleenmitoitus ja kuormituskerroin” 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 ”Uudelleenmitoitus ja kuormituskerroin”?
Suorituskyvyn säätö. 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 ”Uudelleenmitoitus ja kuormituskerroin”-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
- Hajautusfunktiot
- Törmäysten käsittely
- Lisää, hae, poista
- Uudelleenmitoitus ja kuormituskerroin