3 ms·
It doesn't need to be an integer but you're right in that it requires an additional property of the key type that most sorting and searching algorithms do not n
by DrJokepu 16y ago
It doesn't need to be an integer but you're right in that it requires an additional property of the key type that most sorting and searching algorithms do not need: being able to measure the distance between two keys. Most algorithms only need to be able to decide whether a key is less, equal or greater than another key.
- by 16y agoWe only need a ball-park estimate of the distance between keys not an exact measurement. Anything better than random should be an improvement.
- sesqu 16y agoThis is implicit in having access to the (cumulative) key distribution. Still, the interpolation function can turn out to be pretty expensive, if your data isn't uniform 0-100.