Best Practice für die Reverse-Lookup-Suche in Java

75

Ich habe in einem Blog gesehen, dass das Folgende eine vernünftige Möglichkeit ist, eine "Reverse-Lookup" mit der getCode(int)in einer Java-Enumeration durchzuführen:

public enum Status {
    WAITING(0),
    READY(1),
    SKIPPED(-1),
    COMPLETED(5);

    private static final Map<Integer,Status> lookup 
            = new HashMap<Integer,Status>();

    static {
        for(Status s : EnumSet.allOf(Status.class))
            lookup.put(s.getCode(), s);
    }

    private int code;

    private Status(int code) {
        this.code = code;
    }

    public int getCode() { return code; }

    public static Status get(int code) { 
        return lookup.get(code); 
    }
}

Für mich sehen sowohl die statische Karte als auch der statische Initialisierer wie eine schlechte Idee aus, und mein erster Gedanke wäre, die Suche so zu codieren:

public enum Status {
    WAITING(0),
    READY(1),
    SKIPPED(-1),
    COMPLETED(5);

    private int code;

    private Status(int code) {
        this.code = code;
    }

    public int getCode() { return code; }

    public static Status get(int code) { 
        for(Status s : values()) {
            if(s.code == code) return s;
        }
        return null;
    }
}

Gibt es offensichtliche Probleme mit beiden Methoden und gibt es eine empfohlene Möglichkeit, diese Art der Suche zu implementieren?

Armand
quelle
Übrigens, für Sie Map Building Loop, die Sie hätten tun könnenfor(Status s : values()) lookup.put(s.code, s);
Peter Lawrey
4
Stimmt etwas mit der Verwendung nicht Enum.valueOf()? Können Sie Strings nicht speichern?
Jonathan
1
@ Jonathan Sehr oft müssen Sie Aufzählungen aus Binär- oder Zahleneingaben erstellen. Also ich denke , es ist nichts falsch mit Enum.valueOf()(mind Kapitalisierung obwohl) , aber ziemlich oft haben Sie nur ein Byte oder eine Nummer zu beginnen habe. Und bitte: Wenn eine Zeichenfolge nicht benötigt wird, lassen Sie sie weg und suchen Sie nach "Stringing Typed Coding Horror", wenn Sie wissen möchten, warum. Grundsätzlich sollten Sie sich ständig fragen: Wenn ich eine Zeichenfolge erhalte, weiß ich, was darin enthalten ist? Es enthält weit mehr Zustand als eine ganze Zahl oder in der Tat eine Aufzählung, und die Erhöhung des Zustands ist schlecht .
Maarten Bodewes
Werfen
Bohemian

Antworten:

29

Maps.uniqueIndex aus Googles Guave ist sehr praktisch, um Lookup-Karten zu erstellen.

Update: Hier ist ein Beispiel für die Verwendung Maps.uniqueIndexmit Java 8:

public enum MyEnum {
    A(0), B(1), C(2);

    private static final Map<Integer, MyEnum> LOOKUP = Maps.uniqueIndex(
                Arrays.asList(MyEnum.values()),
                MyEnum::getStatus
    );    

    private final int status;

    MyEnum(int status) {
        this.status = status;
    }

    public int getStatus() {
        return status;
    }

    @Nullable
    public static MyEnum fromStatus(int status) {
        return LOOKUP.get(status);
    }
}
Michael
quelle
2
Dies ist eine gute Antwort und beseitigt den staticKlasseninitialisierer. Weiß jemand, ob es andere Vorteile gegenüber einem bestimmten Mapvon Java hat (nur ein statischer Initialisierer für einen feldspezifischen Initialisierer loszuwerden, reicht für mich nicht aus, um eine Bibliothek in meinen Klassenpfad aufzunehmen, selbst wenn diese Bibliothek Guava ist).
Maarten Bodewes
Meiner Meinung nach ist dies eine hackige Lösung, die eine unnötige Abhängigkeit von einer externen Bibliothek hinzufügt. Eine schönere, elegantere Lösung finden Sie hier stackoverflow.com/questions/28762438/how-to-reverse-enum
Bohemian
1
Natürlich brauchst du bei Streams keine Guave : LOOKUP = stream(values()).collect(toMap(MyEnum::getStatus, x -> x));.
Gene
20

Obwohl der Overhead höher ist, ist die statische Karte gut, da sie eine zeitlich konstante Suche nach bietet code. Die Suchzeit Ihrer Implementierung erhöht sich linear mit der Anzahl der Elemente in der Aufzählung. Bei kleinen Aufzählungen trägt dies einfach nicht wesentlich dazu bei.

Ein Problem bei beiden Implementierungen (und wohl auch bei Java-Enums im Allgemeinen) ist, dass es wirklich einen versteckten zusätzlichen Wert gibt, den a Statusannehmen kann : null. Abhängig von den Regeln der Geschäftslogik kann es sinnvoll sein, einen tatsächlichen Aufzählungswert zurückzugeben oder einen zu werfen Exception, wenn die Suche "fehlschlägt".

Matt Ball
quelle
2
@Matt, ich glaube, beide Möglichkeiten sind eine konstante Zeitsuche, da die Karte eine konstante Anzahl von Elementen enthält.
jjnguy
3
@jjnguy: Es ist O(n)in der Größe der Aufzählung. Dies ist alles Pedanterie, da es unwahrscheinlich ist, dass die Aufzählung groß ist.
Matt Ball
6
@jinguy, beide sind möglicherweise "konstante" Zeitoperationen, aber die Konstante in jeder Operation ist unterschiedlich. Eine ist die Zeit, um einen Wert in einer Hashtabelle zu finden, die andere ist die Zeit, die erforderlich ist, um ein variables (aber zur Laufzeit konstantes) Array von Werten zu durchlaufen. Wenn Sie eine Million Werte in dieser Aufzählung hätten (nicht praktisch, aber nur ein Beispiel), würden Sie die Option zum Nachschlagen von Karten bevorzugen.
Matt B
5
@jjnguy: Die Angabe, dass ein Algorithmus vorhanden ist, O(n)bedeutet nicht, dass er nsich zur Laufzeit ändern kann . Was wäre, wenn dies eine analoge Suche in einer unveränderlichen (daher zur Laufzeit festgelegten) Liste durchführen würde? Das wäre absolut ein O(n)Algorithmus, wo nist die Größe der Liste.
Matt Ball
11
@jjnguy werfen Sie einen Blick auf rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation O (1) ist "ein Algorithmus, der unabhängig davon immer zur gleichen Zeit (oder im gleichen Raum) ausgeführt wird der Größe des Eingabedatensatzes. " Während O (N) "ein Algorithmus ist, dessen Leistung linear und direkt proportional zur Größe des Eingabedatensatzes wächst", ändert sich in diesem Fall die Größe des Datensatzes nicht von Lauf zu Lauf (warum denke ich? Sie betrachten es als 'konstant'), die Leistung des Algorithmus basiert immer noch auf der Größe des Eingabedatensatzes (in diesem Fall der Anzahl der Einträge in der Aufzählung)
digitaljoel
7

Hier ist eine Alternative, die vielleicht sogar etwas schneller ist:

public enum Status {
    WAITING(0),
    READY(1),
    SKIPPED(-1),
    COMPLETED(5);

    private int code;

    private Status(int code) {
        this.code = code;
    }

    public int getCode() { return code; }

    public static Status get(int code) {
        switch(code) {
            case  0: return WAITING;
            case  1: return READY;
            case -1: return SKIPPED;
            case  5: return COMPLETED;
        }
        return null;
    }
}

Dies ist natürlich nicht wirklich wartbar, wenn Sie später weitere Konstanten hinzufügen möchten.

Paŭlo Ebermann
quelle
9
Nicht genau das Gleiche, die Switch-Version könnte eine Nachschlagetabelle verwenden, um direkt zum richtigen Code zu springen, anstatt eine Reihe von Tests durchzuführen: artima.com/underthehood/flowP.html
Dan Berindei
12
@jjnguy: Nein, der Compiler kann diesen Schalter für die Verwendung einer binären Suche oder einer Nachschlagetabelle (abhängig von den Zahlen) optimieren. Und Sie müssen das values()Array vorher nicht erstellen und füllen (was allein diese Variante ergeben würde O(n)). Natürlich ist die Methode jetzt länger, daher dauert das Laden länger.
Paŭlo Ebermann
1
@Alison: case WAITING.codeist eine nette Idee, aber ich befürchte, dass dies keine Konstante zur Kompilierungszeit ist.
Paŭlo Ebermann
1
@jinguy Ich glaube nicht, dass sie sich die Mühe gemacht hätten, die Tabellenschalteranweisung zu erstellen, wenn sie die Tabellensuche nicht verwenden wollten. Ich weiß nicht, ob der Lookupswitch-Befehl Optimierungen enthält.
Dan Berindei
15
Dies ist jedoch eine absolut inakzeptable Lösung in Bezug auf sauberen Code. Mit dieser Lösung haben Sie zwei verschiedene Stellen, an denen die ID dem Aufzählungswert zugeordnet ist, sodass es zu Fehlern kommen kann, wenn sich die Zuordnungen unterscheiden!
Zordid
6

Offensichtlich bietet die Karte eine konstante Zeitsuche, während die Schleife dies nicht tut. In einer typischen Aufzählung mit wenigen Werten sehe ich kein Problem mit der Traversal-Suche.

digitaljoel
quelle
Für eine Handvoll Aufzählungen spielt es aus meiner Sicht keine Rolle.
Endlos
3

Hier ist eine Java 8-Alternative (mit Unit-Test):

// DictionarySupport.java :

import org.apache.commons.collections4.Factory;
import org.apache.commons.collections4.map.LazyMap;

import java.util.HashMap;
import java.util.Map;

public interface DictionarySupport<T extends Enum<T>> {

    @SuppressWarnings("unchecked")
    Map<Class<?>,  Map<String, Object>> byCodeMap = LazyMap.lazyMap(new HashMap(), (Factory) HashMap::new);

    @SuppressWarnings("unchecked")
    Map<Class<?>,  Map<Object, String>> byEnumMap = LazyMap.lazyMap(new HashMap(), (Factory) HashMap::new);


    default void init(String code) {
        byCodeMap.get(this.getClass()).put(code, this);
        byEnumMap.get(this.getClass()).put(this, code) ;
    }

    static <T extends Enum<T>> T getByCode(Class<T> clazz,  String code) {
        clazz.getEnumConstants();
        return (T) byCodeMap.get(clazz).get(code);
    }

    default <T extends Enum<T>> String getCode() {
        return byEnumMap.get(this.getClass()).get(this);
    }
}

// Dictionary 1:
public enum Dictionary1 implements DictionarySupport<Dictionary1> {

    VALUE1("code1"),
    VALUE2("code2");

    private Dictionary1(String code) {
        init(code);
    }
}

// Dictionary 2:
public enum Dictionary2 implements DictionarySupport<Dictionary2> {

    VALUE1("code1"),
    VALUE2("code2");

    private Dictionary2(String code) {
        init(code);
    }
}

// DictionarySupportTest.java:     
import org.testng.annotations.Test;
import static org.fest.assertions.api.Assertions.assertThat;

public class DictionarySupportTest {

    @Test
    public void teetSlownikSupport() {

        assertThat(getByCode(Dictionary1.class, "code1")).isEqualTo(Dictionary1.VALUE1);
        assertThat(Dictionary1.VALUE1.getCode()).isEqualTo("code1");

        assertThat(getByCode(Dictionary1.class, "code2")).isEqualTo(Dictionary1.VALUE2);
        assertThat(Dictionary1.VALUE2.getCode()).isEqualTo("code2");


        assertThat(getByCode(Dictionary2.class, "code1")).isEqualTo(Dictionary2.VALUE1);
        assertThat(Dictionary2.VALUE1.getCode()).isEqualTo("code1");

        assertThat(getByCode(Dictionary2.class, "code2")).isEqualTo(Dictionary2.VALUE2);
        assertThat(Dictionary2.VALUE2.getCode()).isEqualTo("code2");

    }
}
Vitaliy Oliynyk
quelle
1
Könnten Sie bitte Ihren Code erklären, anstatt nur einen Code-Dump bereitzustellen? Es sieht aus wie eine OK-Implementierung (eigentlich habe ich gerade eine ähnliche Lösung selbst programmiert), aber ohne die Eigenschaften aufzulisten, müssten die Leute sie basierend auf dem Code bewerten, und das ist unwahrscheinlich.
Maarten Bodewes
0

In Java 8 würde ich einfach die folgende Factory-Methode zu Ihrer Aufzählung hinzufügen und die Lookup-Map überspringen.

public static Optional<Status> of(int value) {
    return Arrays.stream(values()).filter(v -> value == v.getCode()).findFirst();
}
ce72
quelle
Gedanken dazu: Nur eine for-Schleife unter der Decke. Nicht super lesbar. Könnte interessant sein, eine wiederverwendbare Funktion zu schreiben, um dies zu tun und sie nehmen zu lassen (Wert, Status :: getCode) (wie es Maps.uniqueIndex tut)
Barett
1
Dies ist langsamer als alle anderen oben genannten Antworten. 1. Sie erstellen jedes Mal ein neues Array aus values()(dies ist an sich sehr langsam. Wenn Sie also viel tun, können Sie dies erheblich beschleunigen, indem Sie das Array einmal zwischenspeichern und wiederverwenden). 2. Sie verwenden Streams (die in Leistungs- / Benchmark-Tests im Allgemeinen viel langsamer testen als eine einfache for-Schleife).
Shadow Man
-2

Beide Wege sind vollkommen gültig. Und sie haben technisch die gleiche Big-Oh-Laufzeit.

Wenn Sie jedoch zuerst alle Werte in einer Karte speichern, sparen Sie die Zeit, die erforderlich ist, um das Set jedes Mal zu durchlaufen, wenn Sie eine Suche durchführen möchten. Daher denke ich, dass die statische Karte und der Initialisierer ein etwas besserer Weg sind.

jjnguy
quelle
3
Da die Anzahl der Enum-Konstanten konstant ist, ist alles O(1):-)
Paŭlo Ebermann
12
Nein, die lineare Suche läuft in der linearen Zeit O (n) anstelle von O (1) für die HashMap. Auf der anderen Seite ist n 4 ...
Tom Hawtin - Tackline
6
@jjnguy: Die Sache ist, eine Erhöhung der Anzahl der Konstanten ist eine lineare Erhöhung der Laufzeit der Suche, wodurch die Suche O (N) wird. Dass sich die Anzahl der Konstanten zur Laufzeit nicht ändert, ist unerheblich.
ColinD
4
@jjnguy: Dieser Kommentar ist bedeutungslos. N ist die Anzahl der Elemente. Zeitraum.
Marquis von Lorne
2
Sie sollten die Antwort wirklich korrigieren. Das n- te Element im Array zu erhalten ist O (n).
user1803551