Index mapping: Difference between revisions

Revision as of 01:15, 5 June 2011

Latest revision as of 19:41, 19 July 2024

(31 intermediate revisions by 19 users not shown)

Line 1:

{{distinguish|text=[[Index map]], a finding aid in cartography}}

'''Index mapping''' is a [[computer science]] term (also known as a "'''trivial hash function'''"<ref>http://en.wikipedia.org/wiki/Hash_function#Trivial_hash_function</ref>) that is used to describe the mapping of [[raw data]], used directly as in [[array index]], for an [[array data structure|array]]. The technique can be most effective for mapping data with a small range. If the array encompasses all combinations of input, a range check is not required.

'''Index mapping''' (or '''direct addressing''', or a '''trivial [[hash function]]''') in [[computer science]] describes using an [[array data structure|array]], in which each position corresponds to a key in the [[Universe (mathematics)|universe]] of possible values.<ref name=cormen>{{cite book|last1=Cormen|first1=Thomas H.|title=Introduction to algorithms|date=2009|publisher=MIT Press|___location=Cambridge, Mass.|isbn=9780262033848|pages=253–255|edition=3rd|url=https://mitpress.mit.edu/books/introduction-algorithms|accessdate=26 November 2015}}</ref>

==Applicable arrays==

The technique is most effective when the universe of keys is reasonably small, such that [[memory allocation|allocating]] an array with one position for every possible key is affordable.

In practise there are many examples of data exhibiting a small range of valid values all of which are suitable for processing using a trivial hash function including:

Its effectiveness comes from the fact that an arbitrary position in an array can be examined in [[time complexity#Constant time|constant time]].

* month in the year (1-12) - see C example 1 and 2 below

==Applicable arrays==

* day in the month (1-31)

There are many practical examples of data whose valid values are restricted within a small range. A trivial hash function is a suitable choice when such data needs to act as a lookup key. Some examples include:

* day of the week (1-7)

* [[month]] in the year (1–12)

* human lifespan (0-130) - eg. lifecover actuary tables, fixed term mortgage

* [[day]] in the month (1-311–31)

* [[ASCII]] characters (0-256), encompassing:

* [[day of the week]] (1-71–7)

:* common mathematical operator symbols (+-/*^)

* human lifespanage (0-1300–130) -– ege.g. lifecover actuary tables, fixed -term mortgage

:* common punctuation symbols (,.;:")

* [[ASCII]] characters (0–127), encompassing common mathematical operator symbols, digits, punctuation marks, and English language alphabet

:* english uppercase language alphabet (A-Z)

:* english lowercase language alphabet (a-z)

:* numeric digits (0-9)

:* etc

* [[EBCDIC]] characters (0-256)

==Examples==

TheUsing followinga twotrivial exampleshash demonstratefunction, howin a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing &and branching completely thereby, reducing the [[instruction path length]] significantly. Although both examples are shown here as functions, the required code would be better [[Inline expansion|inlined]] to avoid function call overhead in view of theira obviouscomputer simplicityprogram.

===Avoid branching===

Roger Sayle gives an example<ref>{{cite journal|last1=Sayle|first1=Roger Anthony|title=A Superoptimizer Analysis of Multiway Branch Code Generation|journal=Proceedings of the GCC Developers' Summit|date=June 17, 2008|pages=103–116|url=https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf|accessdate=26 November 2015}}</ref> of eliminating a [[multiway branch]] caused by a [[switch statement]]:

<syntaxhighlight lang="c++">

inline bool HasOnly30Days(int m)

{

switch (m) {

case 4: // April

case 6: // June

case 9: // September

case 11: // November

return true;

default:

return false;

}

}

</syntaxhighlight>

Which can be replaced with a table lookup:

===C example 1===

This example<ref>[http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf "A Superoptimizer Analysis of Multiway Branch Code Generation"] by Roger Anthony Sayle</ref> of a C function - returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly

<source lang="c">

if ((unsigned)x > 11) return 0; /*x>12?*/

static const int T[12] ={0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0' */

return T[x]; /* return with boolean 1 = true, 0=false */

</source>

<syntaxhighlight lang="c++">

===C example 2===

inline bool HasOnly30Days(int m)

Example of another C function - incrementing a month number (x) by 1 and automatically resetting if greater than 12

{

<source lang="c">

static const intbool MT[12] = {2 0,3 0,4 0,5 1,6 0,7 1,8 0,9 0,10 1,11,12 0,1}; /* 1-based, table0 to increment x */};

return T[m-1];

return M[x]; /* return with new month number */

}

</source>

</syntaxhighlight>

==See also==

*[[Multiway branch]]

*[[lookup table]]

==References==

{{Reflist}}

==External links==

*[http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf A Superoptimizer Analysis of Multiway Branch Code Generation] by Roger Anthony Sayle

[[Category:Arrays]]

[[Category:Associative arrays]]

[[Category:Articles with example C code]]

[[Category:Hashing|*]]

[[Category:Search algorithms]]