>
> On 31 March 2015 at 18:21, Waldek Hebisch <[email protected]> wrote:
> >
> > 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.
>
> If we look for A among many B_i we must look at all the components of
> A and all the components of B_i for each B_i. If I compute the hash of
> A by looking at all the components of A, I only need to do that once.
Normal case of equality a = b is:
for all components c
if c(a) ~= c(b) then return false
true
Normal case for hash(a) is:
for all components c
s := hashUpdate(s, c(a))
In both cases you need to go trough components of a and b, but
in case of equality there is possibility of early exit. In
case of sets we do all-by all comparison of elements, but
that is quite unusual.
> > For builtin types 'hash' have to perform some
> > computations which look more complicated than equality.
>
> Domains like SingleInteger and Symbol export hash (SXHASH) directly
> from Lisp. But do any of the other built-in types export 'hash'? I
> especially miss 'hash' in the case of Record.
>
> > In important special cases equality is quite fast: if values
> > are different, then frequently we will notice difference
> > after looking only at few components.
>
> Yes. As I said: YMMV. It is not unusual that the cost of computing ~=
> is different than the cost of computing =.
>
> > If values occupy the
> > same place in memory. then Lisp 'EQ' will very quickly tell
> > us that they are equal.
>
> At least as long as we are not using a "quantum computer", if we
> already know that two things are identical then of course it is fast
> to check that they are equal.
>
> > For expression equality requires
> > computing difference, while simple hash would remove irrationalities
> > from denominators, which is much more involved.
>
> Expressing the difference of two rational functions as a rational
> function involves at least the product of two polynomials but I admit
> that I am not certain that it is even possible to define a compatible
> hash function for expression equality defined in this way. Could you
> explain what you mean by removing irrationalities from the
> denominators?
For example transforming:
1/sqrt(x^2 + 1) into sqrt(x^2 + 1)/(x^2 + 1)
This is trivial case, but in general all algebraics (in particular roots)
can be removed from denominator to numerator, so that denominator
is purely transcendental. If you also normalize numerator in some
way (for example by forcing leading coefficient to 1) then
for given set of independent kernels you get canononical form.
>
> Perhaps relevant to this discussion, I liked the following article:
>
> Equality and hashing for (almost) free: Generating implementations
> from abstraction functions
> Derek Rayside, et al.
> http://dspace.mit.edu/handle/1721.1/51695
>
> Abstract:
> In an object-oriented language such as Java, every class requires
> implementations of two special methods, one for determining equality
> and one for computing hash codes.
> I am not sure how easily their proposed method could be applied to
> FriCAS, but I think their definition of the problem is important.
I will look at it, but usualy in such setting authors mean data
structure equality, which is not entirely trivial but has no
problems which appear in math.
>
> > 2) What you write above looks like attempt at error hiding.
> > If essential precondition is violated, then more approprate
> > reaction is to signal error.
>
> Yes perhaps but in 'xhash.spad' Ralf wrote:
>
> table: (Key -> SingleInteger) -> %
> ++ table(h) creates an empty hash table that uses h instead of
> ++ hash$Key. Note that h should be a mathematical function in
> ++ the sense that from k1=k2 follows h(k1)=h(k2). If that is not
> ++ the case, k1 and k2 will internally be considered as being
> ++ different keys.
>
> My suggested change would only do what he claims.
Ralf should say if he cares about this specification. AFAICS
currently even if we ignore problem with rehash this does
not work. Namely consider case when eq(k1, k2) holds but h(k1)~= h(k2).
Still, k1 and k2 may map to the same slot (because we reduce hashes
to smaller range, so after reduction values may match). Without
extra test we will store one of k-s and ignore the second.
To fix this basically in any place you use 'eq' we would have use
your variant. We could say that k1 and k2 _may_ be treated
as different and modify rehash to ignore (drop) duplicates.
But then you may inseret the same key case several times:
you insert k1
you insert k2 bacause it maps to different slot
rehash: k1 and k2 map to the same slot, drop one say k1
reshash: k1 and k2 map to different slots
you insert k1
rehash: k1 and k2 map to the same slot, drop one say k2
reshash: k1 and k2 map to different slots
you insert k2
...
That looks crazy for me, so while it is easy to specify
and probably to implement I do not think we want this.
If treating k1 and k1 is really desirable, then custom
eq, for examples
eq(x, y) ==
x = y and hash(x) = hash(y)
looks like reliable way. This has advantage that normal
case is not burdened with extra computations -- we do
extra work only when needed.
--
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.
