Perché un HashMap dovrebbe essere usato (nelle funzioni) per determinare quale valore restituire (per una chiave) quando un costrutto if else può eseguire il lavoro in tempi migliori?

Question

Perché un HashMap dovrebbe essere usato (nelle funzioni) per determinare quale valore restituire (per una chiave) quando un costrutto if else può eseguire il lavoro in tempi migliori?

#1 da (16 voti)
#2 da (12 voti)
#3 da (3 voti)
#4 da (2 voti)
#5 da (1 voti)

9

Mentre di recente lavoravo in una grande azienda, ho notato che i programmatori seguivano questo stile di codifica:

Supponiamo che io abbia una funzione che ritorna 12 se l'ingresso è A, 21 se l'ingresso è B, e 45 se l'ingresso è C.

Quindi posso scrivere la firma della funzione come:

int foo(String s){
    if(s.equals("A"))      return 12;
    else if(s.equals("B")) return 21;
    else if(s.equals("C")) return 45;
    else throw new RuntimeException("Invalid input to function foo");
}

Ma alla revisione del codice mi è stato chiesto di cambiare la funzione nel modo seguente:

int foo(String s){
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    map.put("A", 12);
    map.put("B", 21);
    map.put("C", 45);
    return map.get(s);
}

Non riesco a convincermi del perché il secondo codice è migliore del primo. Il secondo codice richiederebbe sicuramente più tempo per l'esecuzione.

L'unico motivo per utilizzare il secondo codice può essere che offre una migliore leggibilità. Ma se la funzione viene richiamata più volte, la seconda funzione non rallenterebbe il tempo di esecuzione dell'utilità richiamandola?

Che cosa ne pensi?

coding-style coding-standards

posta Nikunj Banka 17.02.2015 - 18:04

fonte

5 risposte

Leggi altre domande sui tag coding-style coding-standards

Come sviluppatore professionista, è accettabile non scrivere test unitari? [chiuso] Come può un team applicare la metodologia Scrum senza un cliente chiaro? [duplicare]

score 16 · Answer 1

Il punto è spostare la creazione dell'hashmap fuori dalla funzione e farlo una volta (o solo meno volte di quanto altrimenti).

private static final Map<String, Integer> map;
static{
    Map<String, Integer> temp = new HashMap<String, Integer>();
    temp.put("A", 12);
    temp.put("B", 21);
    temp.put("C", 45);
    map = Collections.unmodifiableMap(temp);//make immutable
}

int foo(String s){
    if(!map.containsKey(s))
        throw new RuntimeException("Invalid input to function foo");

    return map.get(s);
}

Comunque java da quando java7 è stato in grado di avere stringhe (finali) nelle opzioni:

int foo(String s){
    switch(s){
    case "A":
        return 12;
    case "B": 
        return 21;
    case "C": 
        return 45;
    default: throw new RuntimeException("Invalid input to function foo");
}

score 12 · Answer 2

Nel tuo secondo esempio, Map dovrebbe essere un membro statico privato per evitare l'overhead di inizializzazione ridondante.

Per grandi quantità di valori, la mappa funzionerà meglio. Usando un hashtable, si può cercare la risposta in tempo costante. Il costrutto multiplo se deve confrontare l'input con ciascuna delle possibilità fino a trovare la risposta giusta.

In altre parole, la ricerca della mappa è O (1) mentre if s è O (n) dove n è il numero di possibili input.

La creazione della mappa è O (n), ma viene eseguita una sola volta se è statica e costante. Per una ricerca eseguita frequentemente, la mappa supererà le dichiarazioni if a lungo termine, al costo di un tempo leggermente maggiore all'avvio del programma (o della classe caricata, a seconda della lingua).

Detto questo, la mappa non è sempre lo strumento giusto per questo lavoro. È bello quando ci sono molti valori, o i valori devono essere configurabili attraverso un file di testo, un input dell'utente o un database (nel qual caso la mappa funge da cache).

score 3 · Answer 3

Ci sono due velocità nel software: il tempo necessario per scrivere / leggere / eseguire il debug del codice; e il tempo necessario per eseguire il codice.

Se riesci a convincermi (e ai tuoi revisori del codice) che la funzione hashmap è effettivamente più lenta di if / then / else (dopo aver effettuato il refactoring per creare una hashmap statica) E puoi convincermi / revisori che è stato chiamato abbastanza volte per fai una vera differenza, quindi vai avanti e sostituisci l'hashmap con if / else.

Altrimenti, il codice hashmap è eminentemente leggibile; e (probabilmente) privo di errori; lo puoi determinare rapidamente solo guardandolo. Non si può davvero dire la stessa cosa del se / else senza veramente studiarlo; la differenza è ancora più esagerata quando ci sono centinaia di opzioni.

score 2 · Answer 4

Preferisco di gran lunga la risposta in stile HashMap.

Esiste una metrica per questo

Esiste una metrica sulla qualità del codice denominata Cyclomatic Complexity . Questa metrica conta fondamentalmente il numero di percorsi diversi attraverso il codice ( come calcolare la complessità ciclomatica ).

Per ogni possibile percorso di esecuzione un metodo diventa sempre più difficile sia per capire che per verificare completamente la correttezza.

Si riduce al fatto che le "parole chiave di controllo" come: ifs, elses, whiles, ecc. fanno leva su test booleani che possono essere sbagliati. L'uso ripetuto di "parole chiave che controllano" produce codice fragile.

Vantaggi aggiuntivi

Inoltre, l '"approccio basato sulla mappa" incoraggia gli sviluppatori a pensare alle coppie input-output come un set di dati che può essere estratto, riutilizzato, manipolato in fase di runtime, testato e verificato. Ad esempio, di seguito ho riscritto "foo" in modo tale da non essere permanentemente bloccati in "A- > 12, B- > 21, C- > 45":

int foo(String s){
    HashMap<String, Integer> map = getCurrentMapping();
    return map.get(s);
}

rachet_freak menziona questo tipo di refactoring nella sua risposta, argomenta per la velocità e il riutilizzo, sto discutendo per la flessibilità di runtime (sebbene usare una collezione immutabile possa avere enormi benefici a seconda della situazione)

score 1 · Answer 5

I dati sono migliori del codice. Non ultimo perché è troppo allettante aggiungere un altro ramo al codice, ma aggiungere una riga a un tavolo è difficile da sbagliare. Questa domanda è un piccolo esempio di questo. Stai scrivendo una tabella di ricerca. O scrivi un'implementazione, completa la logica condizionale e la documentazione, oppure scrivi la tabella e poi cerca in essa.

Una tabella di dati è sempre una rappresentazione migliore di alcuni dati rispetto al codice, l'ottimizzazione del modulo passa. Quanto può essere difficile esprimere la tabella può dipendere dalla lingua: non conosco Java, ma spero che possa implementare una tabella di ricerca più semplicemente rispetto all'esempio in OP.

Questa è una tabella di ricerca in python. Se questo è considerato come un conflitto invitante, considera che la domanda non è taggata java, che il refactoring è indipendente dalla lingua e che molte persone non conoscono java.

def foo(s):
    return {
               "A" : 12,
               "B" : 21,
               "C" : 45,
           }[s]

L'idea di ristrutturare il codice per ridurre il runtime ha valore, ma preferirei usare un compilatore che solleva l'installazione comune piuttosto che farlo da solo.