Re: Efficient way to store an isomorphism?


"Edsko de Vries" <devriese@xxxxxxxxx> wrote in message
news:1123684485.848173.251790@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> [...] would it be possible to define a hash function h': A -> B, that
> would
> "hash" an element of A directly onto the corresponding element of B?
> Then we only need to store this hash function, and finding m(a)
> corresponds to calculating h'(a). Then we can do lookups in O(1) time;
> additionally, we should be able to store the hash function in less than
> O(n) space.

Yes, but it takes O(n) space to store the hash function. It's still
advantageous if you have time to compute the hash function beforehand,
because lookups are actually O(1) worst case.

Google for "minimal perfect hashing". Many minimal perfect hashing
algorithms let you choose the mapping precisely. This one is my favourite:

http://citeseer.ist.psu.edu/czech92optimal.html

--
Matt



.

Relevant Pages

  • Efficient way to store an isomorphism?
    ... if "n" is the size of both sets, it takes Ospace to store the array ... Now we can do lookups in Otime, but we still need Ospace ... to store the array (assuming that storing the hash function takes less ...
    (comp.theory)
  • Re: Is "identify" really good for the game?
    ... Use the 2-3 bytes you store as the seed for an RNG. ... a hash function from your object space down to the 2-3 bytes you want ... POWDER does something very similar to this. ...
    (rec.games.roguelike.development)
  • Re: Efficient way to store an isomorphism?
    ... but it takes Ospace to store the hash function. ... > Google for "minimal perfect hashing". ...
    (comp.theory)