|
Authored by: greed on Monday, May 14 2012 @ 10:35 PM EDT |
Try this on:
With an index, you find the right memory location by calculating. Typically
with base+(index*stride). Or base+((index-1)*stride) for people who think
everything starts at 1.... (Obvious optimization: store base' as base-stride
and use that instead.)
With a symbol, you have to look it up. The defining characteristic of
"looking it up" is comparing. If you use a B-tree, you compare. If
you do a binary search, you compare. If you do a linear search, you compare.
Even if you use a hash table, you still have to compare: hash collisions mean
you are never sure that there isn't a different value at the same hash position
you calculated.
(If you have a known input set and can calculate a "perfect hash"--one
without collisions for the given input--then you can skip the compare. Guess
what? I would argue it's no longer a symbolic look up: you are now directly
calculating the array index with the hash function. Very fast, and nice work if
you can get it. I never get to deal with known inputs....)
[ Reply to This | Parent | # ]
|
- Absolutely - Authored by: Wol on Tuesday, May 15 2012 @ 07:58 PM EDT
|
|
|
|