Mapování indexu - Index mapping

Nesmí být zaměňována s Indexová mapa, vyhledávací pomůcka v kartografii.

Mapování indexu (nebo přímé adresovánínebo triviální hashovací funkce) v počítačová věda popisuje použití pole, ve kterém každá pozice odpovídá klíči v vesmír možných hodnot.[1]Tato technika je nejúčinnější, když je vesmír klíčů přiměřeně malý přidělování pole s jednou pozicí pro každý možný klíč je cenově dostupné. Jeho účinnost vychází ze skutečnosti, že libovolnou pozici v poli lze zkoumat v konstantní čas.

Použitelná pole

Existuje mnoho praktických příkladů dat, jejichž platné hodnoty jsou omezeny v malém rozsahu. Triviální hashovací funkce je vhodnou volbou, když tato data musí fungovat jako vyhledávací klíč. Některé příklady zahrnují:

  • Měsíc v roce (1–12)
  • den v měsíci (1–31)
  • den v týdnu (1–7)
  • lidský věk (0–130) - např. pojistné matematické tabulky, hypotéka na dobu určitou
  • ASCII znaky (0–127), zahrnující běžné matematické operátorské symboly, číslice, interpunkční znaménka a anglickou abecedu

Příklady

Použití triviální hashovací funkce v ne iteračním vyhledávání tabulky může zcela vyloučit podmíněné testování a větvení, čímž se sníží délka instrukční cesty počítačového programu.

Vyvarujte se větvení

Roger Sayle uvádí příklad[2] vyloučení a vícecestná větev způsobené a příkaz switch:

v souladu bool HasOnly30Days(int m){	přepínač (m) {	případ 4:  // Duben	případ 6:  // Červen	případ 9:  // září	případ 11: // Listopad		vrátit se skutečný;	výchozí:		vrátit se Nepravdivé;	}}

Které lze nahradit vyhledáním tabulky:

v souladu bool HasOnly30Days(int m){	statický konst bool T[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };	vrátit se T[m-1];}

Viz také

Reference

  1. ^ Cormen, Thomas H. (2009). Úvod do algoritmů (3. vyd.). Cambridge, Massachusetts: MIT Press. str. 253–255. ISBN  9780262033848. Citováno 26. listopadu 2015.
  2. ^ Sayle, Roger Anthony (17. června 2008). „Superoptimizační analýza generování vícecestných kódů poboček“ (PDF). Sborník jednání ze summitu vývojářů GCC: 103–116. Citováno 26. listopadu 2015.