Dlaczego warto używać HashMap (w funkcjach), aby określić, która wartość ma zostać zwrócona (dla klucza), gdy konstrukcja if else może wykonać zadanie w lepszym czasie?

9

Podczas niedawnej pracy w dużej firmie zauważyłem, że programiści stosowali ten styl kodowania:

Załóżmy, że mam funkcję, która zwraca 12, jeśli wejście to A, 21, jeśli wejście to B, i 45, jeśli wejście to C.

Więc mogę napisać podpis funkcji jako:

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");
}

Ale podczas przeglądu kodu poproszono mnie o zmianę funkcji na:

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

Nie mogę się przekonać, dlaczego drugi kod jest lepszy od pierwszego. Uruchomienie drugiego kodu zdecydowanie zajmie więcej czasu.

Jedynym powodem użycia drugiego kodu może być to, że oferuje on lepszą czytelność. Ale jeśli funkcja jest wywoływana wiele razy, to czy druga funkcja nie spowolni czasu działania narzędzia, które ją wywołuje?

Co o tym myślisz?

Nikunj Banka
źródło
4
W przypadku trzech wartości Mapa wydaje się przesadna ( switchwydaje się bardziej odpowiednia niż if-else). Ale w pewnym momencie staje się problematyczne. Główną zaletą korzystania z mapy jest to, że można ją załadować z pliku lub tabeli itp. Jeśli kodujesz dane wejściowe na mapie, nie widzę dużej wartości nad przełącznikiem.
JimmyJames

Odpowiedzi:

16

Chodzi o to, aby przesunąć tworzenie mapy skrótów poza funkcję i zrobić to raz (lub tylko mniej razy niż w innym przypadku).

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

Jednak java od czasu java7 może mieć (końcowe) ciągi w przełącznikach:

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");
}
maniak zapadkowy
źródło
1
Nie rozumiem, jak to odpowiada na pytanie OP, więc -1 tam. Ale +1 za zasugerowanie zmiany.
user949300,
Pokazuje, jak prawidłowo wdrożyć styl kodowania, aby faktycznie miał sens i ewentualnie poprawić wydajność. Nadal nie ma to sensu dla 3 opcji, ale oryginalny kod był prawdopodobnie znacznie dłuższy.
Florian F
12

W drugim przykładzie Mappowinien to być prywatny element statyczny, aby uniknąć zbędnych kosztów inicjalizacji.

W przypadku dużych ilości wartości mapa będzie działać lepiej. Korzystając z tablicy hasht, można wyszukać odpowiedź w stałym czasie. Konstrukcja wielokrotnego użycia musi porównywać dane wejściowe z każdą z możliwości, dopóki nie znajdzie właściwej odpowiedzi.

Innymi słowy, wyszukiwanie mapy to O (1), zaś ifs to O (n), gdzie n jest liczbą możliwych danych wejściowych.

Tworzenie mapy to O (n), ale jest wykonywane tylko raz, jeśli jest to stan statyczny stały. W przypadku często wykonywanego wyszukiwania mapa ifw dłuższej perspektywie osiągnie lepsze wyniki niż instrukcje, kosztem nieco więcej czasu przy uruchamianiu programu (lub załadowaniu klasy, w zależności od języka).

Biorąc to pod uwagę, mapa nie zawsze jest odpowiednim narzędziem do tego zadania. Jest to przydatne, gdy istnieje wiele wartości lub wartości muszą być konfigurowalne za pomocą pliku tekstowego, danych wejściowych użytkownika lub bazy danych (w takim przypadku mapa działa jak pamięć podręczna).


źródło
Tak, w przypadku dużych ilości wartości mapa będzie działać lepiej. Ale ilość wartości jest stała i wynosi trzy.
RemcoGerlich,
tworzenie mapy to O (N), tylko wyszukiwanie w niej to O (1).
Pieter B
Dobrze, wyjaśniłem swoją odpowiedź.
Mapa wymaga również automatycznego rozpakowywania, co ma niewielki wpływ na wydajność.
user949300,
@ user949300 w Javie, tak, a kod w pytaniu wygląda na Java. Jednak nie jest oznaczony żadnym językiem, a podejście działa w wielu językach (w tym C # i C ++, z których żaden nie wymaga boksu).
3

Oprogramowanie ma dwie prędkości: czas potrzebny na napisanie / odczyt / debugowanie kodu; i czas potrzebny do wykonania kodu.

Jeśli możesz mnie przekonać (i twoich recenzentów kodu), że funkcja skrótu jest rzeczywiście wolniejsza niż if / then / else (po refaktoryzacji w celu uzyskania statycznego skrótu) ORAZ możesz przekonać mnie / recenzentów, że została wywołana wystarczająco dużo razy, aby stworzyć rzeczywistą różnicę, a następnie idź naprzód i zamień skrót na if / else

W przeciwnym razie kod skrótu jest doskonale czytelny; i (prawdopodobnie) bezbłędny; możesz to szybko ustalić, patrząc na to. Nie można tak naprawdę powiedzieć tego samego o if / else, nie badając go naprawdę; różnica jest jeszcze bardziej przesadzona, gdy istnieją setki opcji.

Robert Hanson
źródło
3
Cóż, ten zarzut rozpada się, gdy zamiast tego porównuje się z przełącznikiem ...
Deduplicator
Rozpada się również, jeśli wypiszesz instrukcje if w jednym wierszu.
gnasher729
2
Umieszczając tworzenie mapy skrótów w innym miejscu, po prostu utrudniasz zrozumienie, co się naprawdę dzieje. Musisz zobaczyć te klucze i wartości, aby wiedzieć, jaki jest rzeczywisty efekt funkcji.
RemcoGerlich,
2

Bardzo wolę odpowiedź w stylu HashMap.

Jest na to metryka

Istnieje metryka jakości kodu o nazwie Cyklomatyczna złożoność . Ta metryka zasadniczo liczy liczbę różnych ścieżek w kodzie ( jak obliczyć złożoność cykliczną ).

Dla każdej możliwej ścieżki wykonania metoda staje się coraz trudniejsza do zrozumienia ORAZ pełnego sprawdzenia poprawności.

Sprowadza się to do faktu, że „kontrolowanie słów kluczowych”, takich jak: ifs, elses, whiles itp., Wykorzystuje testy logiczne, które mogą być niepoprawne. Wielokrotne użycie „kontrolujących słów kluczowych” powoduje powstanie delikatnego kodu.

Dodatkowe korzyści

Ponadto „podejście oparte na mapie” zachęca programistów do myślenia o parach danych wejściowych i wyjściowych jako zestawie danych, który można wyodrębnić, ponownie wykorzystać, zmanipulować w czasie wykonywania, przetestować i zweryfikować. Na przykład poniżej przepisałem „foo”, abyśmy nie byli na stałe zamknięci w „A-> 12, B-> 21, C-> 45”:

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

rachet_freak wspomina o tym typie refaktora w swojej odpowiedzi, argumentuje za szybkością i ponownym użyciem, argumentuję za elastycznością środowiska wykonawczego (chociaż użycie niezmiennej kolekcji może mieć ogromne korzyści w zależności od sytuacji)

Ivan
źródło
1
Dodanie tej elastyczności środowiska uruchomieniowego jest albo świetnym pomysłem na przyszłość, albo niepotrzebnym przepracowaniem, które znacznie utrudnia ustalenie, co się dzieje. :-).
user949300,
@JimmyJames Link działa dla mnie: To jest: leepoint.net/principles_and_practices/complexity/…
Ivan
1
@ user949300 Chodzi o to, że dane klucz / wartość cofając się „foo” metody jest odrębną koncepcją, która mogłaby zasłużyć na jakąś formę jasności. Ilość kodu, który chcesz napisać, aby wyodrębnić Mapę, będzie w dużym stopniu zależała od tego, ile elementów zawiera Mapa i jak często te elementy mogą wymagać zmiany.
Ivan
1
@ user949300 Jednym z powodów, dla których sugeruję wycofanie łańcucha if-else jest to, że widziałem łańcuchy if-else w grupach. Trochę podobnych karaluchów, jeśli istnieje jedna metoda oparta na łańcuchu if-else, prawdopodobnie istnieje inna metoda w innym miejscu w bazie kodu z podobnym / identycznym łańcuchem if-else. Wyodrębnienie mapy przynosi dywidendy, jeśli założymy, że mogą istnieć inne metody wykorzystujące podobną strukturę logiczną wyszukiwania / przełączania.
Ivan
Ja też widziałem duplikaty, prawie identyczne, jeśli / else bloki rozrzucone po całym miejscu. Dobrze powiedziane
Jon Chesterfield,
1

Dane są lepsze niż kod. Nie tylko dlatego, że dodawanie kolejnej gałęzi do kodu jest zbyt kuszące, ale dodanie wiersza do tabeli jest trudne do pomyłki. To pytanie jest niewielkim tego przykładem. Piszesz tablicę przeglądową. Napisz implementację z logiką warunkową i dokumentacją lub napisz tabelę, a następnie wyszukaj w niej.

Tabela danych jest zawsze lepszą reprezentacją niektórych danych niż kod, przechodzi optymalizacja modulo. To, jak trudna jest tabela do wyrażenia, może zależeć od języka - nie znam Javy, ale mam nadzieję, że zaimplementuje ona tablicę przeglądową prostszą niż przykład w OP.

To jest tabela odnośników w pythonie. Jeśli jest to postrzegane jako konflikt zapraszający, należy wziąć pod uwagę, że pytanie nie jest oznaczone java, refaktoryzacja jest niezależna od języka i że większość ludzi nie zna java.

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

Pomysł na restrukturyzację kodu w celu ograniczenia czasu działania ma swoją wartość, ale wolałbym raczej użyć kompilatora, który pobiera zwykłą konfigurację niż sam.

Jon Chesterfield
źródło
-1 nie jest odpowiedzią na pytanie.
Pieter B
W jakim sensie? Poprosiłbym autora o zastąpienie łańcucha if else mapą na podstawie tego, że dane i kod powinny być oddzielne. Jest to wyraźny powód, dla którego drugi kod jest lepszy od pierwszego, chociaż wszystkie wywołania map.put są niefortunne.
Jon Chesterfield
2
@JonChesterfield Ta odpowiedź jest w zasadzie „użyj lepszego języka”, co rzadko jest pomocne.
walpen
@walpen fair point. Ivan poczynił mniej więcej taką samą obserwację za pośrednictwem Javy, więc nie musiałem wyraźnie przechodzić do Pythona. Zobaczę, czy uda mi się trochę posprzątać
Jon Chesterfield
W jakimś starszym kodzie java potrzebowałem kilku map do czegoś bardzo podobnego, więc napisałem małe narzędzie do konwersji N-wymiarowych tablic tablic 2-D w mapę. Trochę zuchwały, ale działał dobrze. Ta odpowiedź wskazuje na moc Pythona / JS we wspieraniu notacji JSONy w tak prosty i łatwy sposób.
user949300,