Bill Page wrote:
>
> On 27 March 2015 at 03:30, Ralf Hemmecke <[email protected]> wrote:
> >
> > Furthermore, deviating from
> >
> > if eq(a, b) then hash(a) = hash(b)
> >
> > might yield unpredictable results. Maybe not for insertion and
> > searching, but it should be checked carefully what happens when
> >
> > not eq(a,b) and hash(a) = hash(b)
> >
> > when a or b is deleted from the table, because deleting a might result
> > in actually removing b from the table.
> >
>
> I do not intend to deviate from
>
> if eq(a, b) then hash(a) = hash(b)
>
> I agree that that is an essential part of the definition of hash
> function. In the existing XHashTable code if an incompatible hash
> function is passed the almost immediate result is an array bounds
> failure in the 'rehashAux!' routine due to an unexpected duplicate
> key. A simple change in 'localSearch' to check both hash and eq, for
> example:
>
> hk := h k
> h1: Z := hk::Z
> ...
> hk = h toKey mk and eq(k,toKey mk) => return p -- key found
> ...
> not deleted? mk and hk = h toKey mk and eq(k,toKey mk) =>
>
> is sufficient to prevent this and maybe preferable since usually
> calling hash is much cheaper than computing eq even when eq defaults
> to =$Key. Since evaluation of 'and' is lazy I guess the mileage will
> depend on the statistics of hits and misses.
1) Why do you expect 'hash' to be cheaper than 'eq'? In normal
case both 'hash' and 'eq' have to look at all components
of a value. For builtion types 'hash' have to perform some
computations which look more complicated than equality.
In important special cases equality is quite fast: if values
are different, then frequently we will notice difference
after looking only at few components. If values occupy the
same place in memory. then Lisp 'EQ' will very quickly tell
us that they are equal. For expression equality requires
computing difference, while simple hash would remove irrationalities
from denominators, which is much more involved.
2) What you write above looks like attempt at error hiding.
If essential precondition is violated, then more approprate
reaction is to signal error. In this case I would say that
doing extra computation to detect errors is probably not
worth the effort. Rather, detectiong out of bound array
index is enough. We may add some test to give better
error message, but it should be cheap (like comparing index
with bound).
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
