On Tue, 28 Oct 2014 05:42:52 -0700 (PDT)
Volker Braun <vbraun.n...@gmail.com> wrote:
> But the most important thing is that caching must be 100% reliable, and
> that means input must be really equal (at most up to some unique
> isomorphism), and not just "equal enough". So either we make __eq__ much
> stricter, or we write our own associative container that doesn't use __eq__
> to compare inputs. The _cache_key() convention in #16316 is a baby step in
> that direction, except that it does it only for caching and doesn't provide
> a generally usable associative container. Eg. you'd essentially have to
> write your own hash table for Buchberger just for padics.
>
> It seems that there could be three versions of associative containers
> (dict, set)
I have been thinking about this from time to time. I have some comments
below.
> 1) Python version. Randomly wrong if you add elements from different
> parents.
>
> 2) A version coercing to a common parent (similar to Sequence)
It might be useful to allow any callable for coercion instead of a
parent. Then this can also be used for user-defined normalization, or
to use keys that are not sage-objects, such as pairs of field elements
and strings.
This would be something like this:
class CoercingDict:
def __init__(self, f):
self.f = f
self.data = dict()
def __setitem__(self, key, value):
self.data[self.f(key)] = value
def __getitem__(self, key):
return self.data[self.f(key)]
> The first two are insertion-order dependent on same parent with overly
> loose == comparison.
I assume that you are supposing here that equality is still an
equivalence relation that is respected by the hash? If the hash does
not respect the equality, equal keys with distinct hashes might replace
each other depending on whether they end up in the same hash bucket.
This not only depends on the insertion-order, but also on the size of
the internal hash table. Or does python first compare hashes inside
each bucket?
> 3) A version that treats elements from different parents as distinct before
> even calling ==, and with a hook to override == with a stricter comparison.
> This is what caching needs to use.
I think there should also be a hook for alternative hashing to go with
the alternative comparison. It might be useful to have methods
_strict_eq_ and _strict_hash_ on sage objects and then to use something
like the following by default, which ensures transparency for tuples,
frozensets, ...:
def strict_equal(a, b):
# recurse into containers such as tuples, frozensets, ...
# Use a._strict_eq_(b) if available, __eq__ otherwise.
# (Parent checking is perhaps delegated to _strict_eq_, to allow
# elements of different realisations to compare equal.)
def strict_hash(a, b):
# recurse into containers such as tuples, frozensets, ...
# Use a._strict_hash_(b) if available, __hash__ otherwise.
I would also like to suggest a fourth container:
4) A version that computes an internal key and uses that, but to the
outside world presents the original key. This allows mixed-parent
containers, but (if the codomain of the keying function is sensible) is
explicit about what will replace what. It would be something like this:
class KeyingDict:
def __init__(self, f):
self.f = f
self.data = dict()
def __setitem__(self, key, value):
self.data[self.f(key)] = (key, value)
def __getitem__(self, key):
return self.data[self.f(key)][1]
def keys(self):
return [x[1][0] for x in self.data.iteritems()]
This can be used to implement 3, using the following class as f:
class StrictEqualityShim:
def __init__(self, x):
self.x=x
def __eq__(self, other):
# check that other is StrictEqualityShim
# check matching types of .x
# recurse for tuples, frozensets, ...
# call self.x._strict_eq_(other.x) if available and
# self.x.__eq__ (other.x) otherwise
def __hash__(self, x):
# recurse for tuples, frozensets, ...
# try _strict_hash_
# otherwise use __hash__
Regards,
Erik Massop
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
