HashMap vs Switch-Anweisung Leistung

Eine HashMap hat im Wesentlichen O (1) Leistung, während ein Switch-Status entweder O (1) oder O (log (n)) je nachdem, ob der Compiler einen Tableswitch oder Lookup-Schalter verwendet.HashMap vs Switch-Anweisung Leistung

Verständlicherweise, wenn eine Switch-Anweisung als solche geschrieben wird,

switch (int) { 
    case 1: 
    case 2: 
    case 3: 
    case 4: 
    default: 
}

dann wäre es ein table verwenden und hat eindeutig einen Leistungsvorteil gegenüber einem Standard-HashMap. Aber was, wenn die switch-Anweisung spärlich ist? Dies wären zwei Beispiele, die ich vergleichen würde:

HashMap<Integer, String> example = new HashMap<Integer, String>() {{ 
     put(1, "a"); 
     put(10, "b"); 
     put(100, "c"); 
     put(1000, "d"); 
}};

switch (int) { 
    case 1: 
     return "a"; 
    case 10: 
     return "b"; 
    case 100: 
     return "c"; 
    case 1000: 
     return "d"; 
    default: 
     return null; 
}

Was würde mehr Durchsatz, einen Lookupswitch oder HashMap bieten? Gibt der Overhead der HashMap dem LookupSwitch einen frühen Vorteil, fällt er aber allmählich ab, wenn die Anzahl der Fälle/Einträge zunimmt?

Edit: Ich habe einige Benchmarks mit JMH versucht, hier sind meine Ergebnisse und Code verwendet. https://gist.github.com/mooman219/bebbdc047889c7cfe612 Wie Sie erwähnten, übertraf die Lookup-Anweisung die HashTable. Ich wundere mich immer noch warum.

Quelle

2015-01-16 Joe C

Wie bei so ziemlich jeder Performance-Frage: Sie müssen es messen. http://stackoverflow.com/q/504103/139010 Ich freue mich auf deine Ergebnisse ':)' –

Eine gute Standardantwort ist es, Ihnen zu sagen, den Unterschied zu messen ... Ich würde erwarten, dass die switch-Anweisung schneller sein wird, weil es sollte weniger Instruktionen ergeben. Mit C und GCC wird ein Switch implementiert als if/elseif-Ketten, Sprungtabellen oder was nicht abhängig vom Kontext (zB wie viele Fälle im Switch, Indizierung etc.) –

Zusätzlich zu weitaus geringerer Komplexität hat der Lookupswitch-Mechanismus der wichtige Vorteil der Fundstelle. Die Hashmap muss 1. den Integer-Schlüssel dereferenzieren; 2. Dereferenzierung des Bucket-Arrays; 3. Dereferenzieren der Knoteninstanz in dem Array bei dem von 1 abgeleiteten Index; 4. Dereferenzieren Sie den Integer-Schlüssel des Knotens, um sicherzustellen, dass er dem angeforderten Schlüssel entspricht. 5. Deferenzieren Sie den Rückgabewert vom Knoten. –

Es hängt von vielen Dingen:

Wenn es ein paar Dinge/feste Gegenstände. Schalter verwenden (Worst Case O (n))
Wenn es eine Menge von Elementen gibt ODER möchten Sie zukünftige Elemente hinzufügen, ohne viel Code zu ändern ---> Mit Hash-Karte (Zugriffszeit gilt als konstante Zeit)
Für Ihren Fall. Sie sollten sich keine Gedanken über die Leistung machen, da der Zeitaufwand für beide Fälle sehr niedrig ist. Konzentrieren Sie sich nur auf die Lesbarkeit/Wartbarkeit Ihres Codes.

Quelle

2015-01-16 22:39:34 Loc

Die Länge des Schlüssels ist ebenfalls relevant. – OldCurmudgeon

Warum sind viele Dinge schlecht für switch statement? Ich habe gehört, dass der Compiler in Switch-Anweisungen Optimierung und Binärbaum für uns tut. – shuva

In Ihrem Fall, da Sie einen Integer Schlüssel für Ihre HashMap und ein schlichtes ‚int‘ verwenden für Ihre switch Anweisung, mit der besten Performance Implementierung wird die switch Aussage, es sei denn die Anzahl der Durchgänge durch diesen Abschnitt sein, Code ist sehr hoch (Zehntausende oder Hunderttausende).

Quelle

2017-05-18 12:51:24 sqlsword

Antwort

Verwandte Themen