Content deleted Content added
Stevebroshar (talk | contribs) →One-dimensional tables: Get to the point; accuracy |
Stevebroshar (talk | contribs) →Sparse one-dimensional array: add link |
||
Line 44:
| ... ||style="background:lightblue;"| 00
|}
A relatively simple implementation consists of a [[sparse file |sparse]], one-dimensional array of values. The index space is fully covered by the array such that lookup involves indexing into the array by the input value, and a value is found even for an index that is not intended to be used; preventing an error that might otherwise occur for an unused index value. The lookup is achieved in [[constant time]]; without searching. In most [[computer architecture |architecture]]s, this can be accomplished in two or three [[machine instruction]]s. The technique is known as a "[[trivial hash function]]" or, when used specifically for branch tables, "[[double dispatch]]". To be feasible, the range of index values should be relatively small. In the example, the table is indexed by ASCII character value so it has 256 entries; an entry for each ASCII value. Only the values for the letter A, D, M, and S are important. All other values are uninteresting and set to 0.
In automata-based programming and [[pseudoconversational transaction]] processing, if the number of distinct program states is small, a "dense sequence" control variable can be used to efficiently dictate the entire flow of the main program loop.
| |||