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. > 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? 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. Although the specification of these methods is usually straightforward, they can be hard to code (due to subclassing, delegation, cyclic references, and other factors) and often harbor subtle faults. A technique is presented that simplifies this task. Instead of writing code for the methods, the programmer gives, as a brief annotation, an abstraction function that defines an abstract view of an object's representation, and sometimes an additional observer in the form of an iterator method. Equality and hash codes are then computed in library code that uses reflection to read the annotations. Experiments on a variety of programs suggest that, in comparison to writing the methods by hand, our technique requires less text from the programmer and results in methods that are more often correct. -- I am not sure how easily their proposed method could be applied to FriCAS, but I think their definition of the problem is important. > 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. > In this case I would say that > doing extra computation to detect errors is probably not > worth the effort. Rather, detecting out of bound array > index is enough. It was very confusing to me until I realized that the documentation was not quite accurate. > We may add some test to give better > error message, but it should be cheap (like comparing index > with bound). Yes, that is quite easy: -- 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.
