C Academy · Lezione

Ridimensionamento e fattore di carico

Ottimizzazione delle prestazioni

Ridimensionamento e fattore di carico è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Che cos'è il fattore di carico

Il fattore di carico è il rapporto tra gli elementi memorizzati e i bucket: alpha = size / capacity. Misura quanto è piena la tabella e influisce direttamente sulle prestazioni.

Perché il fattore di carico è importante

Quando il fattore di carico aumenta, i bucket contengono catene più lunghe (oppure i probe formano raggruppamenti), quindi le operazioni rallentano.

Alpha basso: veloce, ma spreca memoria
Alpha alto: compatto, ma lento

Per il concatenamento, un obiettivo comune è 0.75.

Calcolo del fattore di carico

Calcolatelo come rapporto in virgola mobile, così potrete confrontarlo con una soglia.

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

Quando ridimensionare

Dopo ogni inserimento, verificate se il fattore di carico supera la soglia. In tal caso, espandete la tabella (di solito raddoppiandone la capacità) e ricalcolate gli hash.

#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;
}

Spiegazione del rehashing

Non potete copiare i bucket alla cieca, perché l'indice di ogni chiave dipende dalla capacità. Il rehashing ricalcola il bucket di ogni chiave in base alla nuova capacità e la reinserisce.

Una funzione di ridimensionamento

Allochiamo un nuovo array di bucket più grande; percorriamo ogni vecchio nodo e lo spostiamo nel nuovo array usando la nuova capacità; infine sostituiamo gli array. Ecco il ricalcolo dell'indice fondamentale.

#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;
}

Spostare i nodi senza riallocarli

Con il concatenamento potete spostare i nodi esistenti nel nuovo array invece di allocarne di nuovi. Scollegate ogni nodo, ricalcolate il bucket e inseritelo in testa.

#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;
}

Strategia di crescita

Raddoppiare la capacità mantiene il costo ammortizzato dell'inserimento pari a O(1): anche se un ridimensionamento costa O(n), si verifica abbastanza raramente da mantenere costante il costo medio per inserimento.

Le potenze di due consentono inoltre di usare la veloce maschera AND.

#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;
}

Riduzione della capacità

Facoltativamente, riducete la capacità quando il fattore di carico scende troppo (ad esempio sotto 0.1) dopo numerose eliminazioni. Ridurre la capacità recupera memoria, ma aggiunge il costo del rehashing; procedete quindi con cautela per evitare ridimensionamenti continui.

Indirizzamento aperto e fattore di carico

Le tabelle con indirizzamento aperto sono molto più sensibili al fattore di carico. Le prestazioni crollano quando alpha si avvicina a 1, quindi in genere vengono ridimensionate tra 0.5 e 0.7, valori inferiori allo 0.75 del concatenamento.

Dimostrazione del costo ammortizzato

Simuliamo inserimenti che raddoppiano la capacità a 0.75 e contiamo il lavoro totale, mostrando che la media rimane bassa.

#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;
}

Verifica rapida

Verifichi la Sua comprensione del ridimensionamento.

Riepilogo

Ha imparato a ottimizzare le prestazioni delle tabelle hash.

Fattore di carico = size / capacity
Ridimensionare quando supera una soglia (circa 0.75 per il concatenamento)
Eseguire il rehashing perché gli indici dipendono dalla capacità
Il raddoppiamento garantisce inserimenti O(1) ammortizzati

Domande Frequenti

La lezione «Ridimensionamento e fattore di carico» è gratuita?

Sì — il testo completo di «Ridimensionamento e fattore di carico» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Ridimensionamento e fattore di carico»?

Ottimizzazione delle prestazioni Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Ridimensionamento e fattore di carico»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy