Istruzione switch con un numero enorme di casi

Question

Cosa succede se lo switch ha più di 5000 case. Quali sono gli svantaggi e come possiamo sostituirlo con qualcosa di più veloce?

Nota: non mi aspetto di utilizzare la matrice per archiviare i casi poiché è la stessa.

Answer 1

Non c'è una ragione specifica per pensare che si desideri qualcosa di diverso da un'istruzione switch/case (e in effetti mi aspetterei che fosse inutile). Il compilatore dovrebbe creare un codice di dispacciamento efficiente, che potrebbe comportare una combinazione di tabelle [sparse] statiche e indicizzazione diretta, binario, ecc .; ha una visione approfondita dei valori statici dei casi e dovrebbe svolgere un lavoro eccellente (risintonizzandoli al volo ogni volta che si cambiano i casi, mentre i nuovi valori non si adattano bene a un approccio artigianale - come valori estremamente diversi quando hai avuto una ricerca di array abbastanza affollata - potrebbe richiedere la rielaborazione del codice o causare silenziosamente un aumento di memoria o un calo delle prestazioni).

Alla gente interessavano davvero questo genere di cose quando C cercava di conquistare i programmatori di assemblaggi hard-core ... i compilatori erano ritenuti responsabili di generare un buon codice. In altre parole - se non è (misurabilmente) rotto, non aggiustarlo.

Più in generale, è bello essere curioso di questo genere di cose e di avere idee della gente sulle alternative e le loro implicazioni di prestazioni, ma se si davvero cura e la differenza di prestazioni potrebbe fare la differenza utile al vostro programma (soprattutto se la profilazione lo suggerisce), quindi sempre un punto di riferimento con il tuo programma che fa un vero lavoro.

Answer 2

Provare a utilizzare la classe Dizionario con i valori Delegate. Almeno rende il codice un po 'più leggibile.

Answer 3

Come spunto di riflessione ... nel caso in cui uno potrebbe essere bloccato con un compilatore vecchio/bacato/inefficiente o semplicemente l'amore per l'hacking.

Il lavoro interno di switch è composto da due parti. Trovare l'indirizzo per saltare e saltare bene lì. Per la prima parte è necessario utilizzare una tabella per trovare l'indirizzo. Se il numero di casi aumenta, la tabella diventa più grande - la ricerca dell'indirizzo per saltare richiede tempo. Questo è il punto in cui i compilatori cercano di ottimizzare, combinando diverse tecniche, ma un approccio semplice è quello di utilizzare direttamente la tabella che dipende dallo spazio dei valori del caso.

In un retro dell'esempio tovagliolo;

switch (n) { 
    case 1: foo(); break; 
    case 2: bar(); break; 
    case 3: baz(); break; 
} 

con tale pezzo di compilatore codice può creare una matrice di jump_addresses e direttamente ottenere l'indirizzo mediante array [n]. Ora la ricerca ha appena preso O (1). Ma se si ha un interruttore come di seguito:

switch (n) { 
    case 10: foo(); break; 
    case 17: bar(); break; 
    case 23: baz(); break; 
    // and a lot other 
} 

compilatore deve generare una tabella contenente case_id, coppie jump_address e il codice per la ricerca in quella struttura, che con la peggiore applicazione può richiedere O (n). (I compilatori decenti ottimizzano il tutto da questo scenario quando sono completamente liberati attivando le rispettive bandiere di ottimizzazione in modo tale che quando è necessario eseguire il debug di questo codice ottimizzato il cervello inizia a friggere.)

Quindi la domanda è puoi farlo tutto te stesso a livello C per battere il compilatore? e la cosa divertente è che durante la creazione di tabelle e la ricerca attraverso di loro sembra facile, saltando a un punto variabile utilizzando goto non è possibile in standard C. Quindi c'è una possibilità che se non si intende utilizzare i puntatori di funzione a causa di sovraccarico o struttura del codice, sei bloccato ... beh se non stai usando GCC. GCC ha una funzione non standard denominata Labels as Values che consente di ottenere i puntatori alle etichette.

Per completare l'esempio è possibile scrivere il secondo switch con "etichette come valori" caratteristica del genere:

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....}; 
goto *labels[n]; 
case_foo: 
    foo(); 
    goto switch_end; 
case_bar: 
    bar(); 
    goto switch_end; 
case_baz: 
    baz(); 
    goto switch_end; 
// and a lot other 
switch_end: 

Naturalmente se si sta parlando di circa 5000 casi, è molto meglio se si scrive un pezzo di codice per creare questo codice per te - ed è probabilmente solo un modo per mantenere tale software.

Come note di chiusura; migliorerà il tuo lavoro quotidiano? No. Questo migliorerà le tue abilità? Sì e parlando per esperienza, una volta mi sono trovato a migliorare un algoritmo di sicurezza in una smart card semplicemente ottimizzando i valori dei casi. È un mondo strano.

Answer 4

La dichiarazione di switch di grandi dimensioni, generalmente generata automaticamente, può richiedere molto tempo per la compilazione. Ma mi piace l'idea che il compilatore ottimizzi l'istruzione switch.

Un modo per spezzare l'istruzione switch è quello di utilizzare bucket,

int getIt(int input) 
{ 
    int bucket = input%16; 
    switch(bucket) 
    { 
    case 1: 
     return getItBucket1(input); 
    case 2: 
     return getItBucket2(input); 
    ... 
    ... 
    } 
    return -1; 
} 

Così nel codice qui sopra, abbiamo rotto a parte la nostra istruzione switch in 16 parti. È facile cambiare il numero di bucket nel codice generato automaticamente.

Questo codice ha aggiunto il costo di runtime di uno strato di riferimento indiretto o di chiamata di funzione. . Ma considerando i bucket definiti in diversi file, è più veloce compilarli in parallelo.