#16316: cached_function and cached_method for unhashable elements
-------------------------------------+-------------------------------------
Reporter: saraedum | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.3
Component: misc | Resolution:
Keywords: | Merged in:
Authors: Julian Rueth | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/saraedum/ticket/16316 | a65ac8524294fde91e021c39b9f227277ec33d23
Dependencies: #16251 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by saraedum):
Replying to [comment:8 pbruin]:
> It seems that the problem really has to do with key comparison in
dictionaries, not with hashing or caching specifically. Given (1)
Python's use of `==` for key comparison and (2) Sage's lenient
implementation of `==` for elements, we basically cannot use Sage elements
as dictionary keys.
This is not really the topic of the ticket, but I do not agree. It depends
on what you want to do. If you have sufficient control over which elements
are put in the dictionary, then you can use Sage objects. Of course you
are right, that our `==` causes a lot of trouble.
> One would like a third comparison operator, say `equal`^1^, that regards
two objects as equal if and only if all their "mathematically relevant"
properties (e.g. value and precision for real or ''p''-adic numbers, but
not memory location) are the same. Our caching problems would then
disappear if keys were compared using `equal`. In this hypothetical case,
the correct property for hash functions would be `X equal Y` => `hash(X)
== hash(Y)`.
Such an operator might be helpful and would really fix trouble with
caching. Then again, when are two objects `equal`? Do their parents have
to be identical? Or just `equal`? It is not clear to me whether there can
be a generic implementation that makes everybody happy. If you are aware
of the current limitations, then you can work around the problems.
> - Do I understand correctly that the purpose of `cache_key` can be
viewed as emulating the "missing" `equal` by assigning to each object `X`
a (hashable) object `cache_key(X)` satisfying the condition `cache_key(X)
== cache_key(Y)` <=> `X equal Y` ?
Yes and no. The idea is really to give elements a `hash` which don't have
one normally. The intention was to do something similar to what you
propose above: Two unhashable elements in the same parent with equal cache
key should behave identical in any reasonable computation. (There is of
course room for interpretation in this 'definition'.)
> - If so, does the implementation in this ticket satisfy this condition?
(I am mainly worried that the parent of an element `x` does not seem to be
encoded in `cache_key(x)`.)
I did this on purpose. I replicate the current behaviour in sage, i.e., if
you mix elements with different parents in one dictionary, then you really
need to know what you are doing. Why not include the parent? Well, are two
parents equal if they are `==`-equal, or identical, and what if they can
not be hashed (which will be the case for `p`-adic extension fields).
I have no strong opinion on whether or not to include the parent but I
think it can be more confusing than helpful. Also keys might unnecessarily
be rather large. If your application will only get elements from a single
parent but you store all the data needed to create the extension field
with every element in a cache, that could be really a waste. We could of
course only store `id(parent)`; but I'm not sure whether that is too
extreme.
--
Ticket URL: <http://trac.sagemath.org/ticket/16316#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" 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/sage-trac.
For more options, visit https://groups.google.com/d/optout.
