Mapowanie indeksu
Mapowanie indeksów (lub adresowanie bezpośrednie lub trywialna funkcja skrótu ) w informatyce opisuje użycie tablicy , w której każda pozycja odpowiada kluczowi we wszechświecie możliwych wartości. Technika ta jest najskuteczniejsza, gdy wszechświat kluczy jest stosunkowo mały, tak że przydzielenie tablicy z jedną pozycją dla każdego możliwego klucza jest niedrogie. Jego skuteczność wynika z faktu, że dowolną pozycję w tablicy można badać w stałym czasie .
Obowiązujące tablice
Istnieje wiele praktycznych przykładów danych, których prawidłowe wartości są ograniczone w małym zakresie. Trywialna funkcja skrótu jest odpowiednim wyborem, gdy takie dane muszą działać jako klucz wyszukiwania. Niektóre przykłady obejmują:
- miesiąc w roku (1–12)
- dzień miesiąca (1–31)
- dzień tygodnia (1–7)
- wiek człowieka (0–130) – np. tablice aktuarialne dożywotnie, hipoteka terminowa
- ASCII (0–127), obejmujące typowe symbole operatorów matematycznych, cyfry, znaki interpunkcyjne i alfabet języka angielskiego
Przykłady
Użycie trywialnej funkcji skrótu w nieiteracyjnym przeszukiwaniu tabeli może całkowicie wyeliminować testowanie warunkowe i rozgałęzienia, zmniejszając długość ścieżki instrukcji programu komputerowego.
Unikaj rozgałęzień
Roger Sayle podaje przykład wyeliminowania gałęzi wielokierunkowej spowodowanej instrukcją switch :
inline bool HasOnly30Days ( int m ) { switch ( m ) { przypadek 4 : // kwiecień przypadek 6 : // czerwiec przypadek 9 : // wrzesień przypadek 11 : // listopad powrót true ; domyślnie : zwróć fałsz ; } }
Które można zastąpić wyszukiwaniem w tabeli:
0 0 0 0 0 0 0 0
inline bool HasOnly30Days ( int m ) { static const bool T [] = { , , , 1 , , 1 , , , 1 , , 1 , }; powrót T [ m -1 ]; }