Opened 5 years ago
Closed 5 years ago
#19555 closed enhancement (fixed)
Implement a containment for cartesian_product
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.10 
Component:  combinatorics  Keywords:  
Cc:  sagecombinat, vdelecroix  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  6a440d5 (Commits)  Commit:  6a440d55060e2a7debbed41b22990951d8a3c6a5 
Dependencies:  Stopgaps: 
Description
We currently have this:
sage: C = cartesian_product([range(5), range(5)]) sage: (1, 1) in C False
Change History (22)
comment:1 Changed 5 years ago by
 Branch set to public/sets/contains_cartesian_product19555
 Commit set to fb14675d6a264ca2405cebbcdb62a3eddfadd1f4
 Status changed from new to needs_review
comment:2 followup: ↓ 4 Changed 5 years ago by
I admittedly do not know much about such matters, but isn't the problemm here that the object is not a 'facade' object, while you expect it to be in your bug report?
Nathann
comment:3 Changed 5 years ago by
 Cc vdelecroix added
comment:4 in reply to: ↑ 2 Changed 5 years ago by
Replying to ncohen:
I admittedly do not know much about such matters, but isn't the problemm here that the object is not a 'facade' object, while you expect it to be in your bug report?
More or less. The current generic code (from sage.structure.parent
) tries to compare the tuple with the corresponding object of the cartesian product. And they of course compare as different:
sage: C = cartesian_product([srange(5), srange(5)]) sage: c = C((1,1)) sage: c (1, 1) sage: c == (1,1) False sage: (1,1) == c False
Warning: your example is completely broken
sage: C = cartesian_product([range(5), range(5)]) sage: C((1r,1r)) (1, 1) sage: C((1,1)) Traceback (most recent call last): ... TypeError: Cannot convert int to sage.structure.element.Element
Warning++: you can not use range
and srange
in the same Sage session since FiniteEnumeratedSet
uses UniqueRepresentation
... I guess a safer way to implement this unique representation, would be to force a common universe for the elements... (see #19562)
comment:5 Changed 5 years ago by
comment:6 followup: ↓ 8 Changed 5 years ago by
 Status changed from needs_review to needs_info
 What is the rationale for having tuple being considered as elements of the cartesian product?
 With this version
__contains__
andElement.__eq__
are not compatiblesage: (1,1) in C True sage: any(x == (1,1) for x in C) False
comment:7 Changed 5 years ago by
 Commit changed from fb14675d6a264ca2405cebbcdb62a3eddfadd1f4 to 7466511b9ba67f2d6b8985fa0f4c641fb9e58978
comment:8 in reply to: ↑ 6 ; followup: ↓ 9 Changed 5 years ago by
 Status changed from needs_info to needs_review
Replying to vdelecroix:
 What is the rationale for having tuple being considered as elements of the cartesian product?
They are just wrappers around tuples, and at times, it is beneficial to not wrap/unwrap such objects, such as if the Cartesian product is the set of keys of a dict/Family.
 With this version
__contains__
andElement.__eq__
are not compatiblesage: (1,1) in C True sage: any(x == (1,1) for x in C) False
Good point. I added equality of tuples.
comment:9 in reply to: ↑ 8 Changed 5 years ago by
Replying to tscrim:
Replying to vdelecroix:
 What is the rationale for having tuple being considered as elements of the cartesian product?
They are just wrappers around tuples, and at times, it is beneficial to not wrap/unwrap such objects, such as if the Cartesian product is the set of keys of a dict/Family.
Then in that case I would actually implement an option in CartesianProduct
to actually use tuples directly.
comment:10 Changed 5 years ago by
Err.. Just wondering aloud: is it safe to enable equality with tuples? It means that the hash has to be the same, doesn't it?
Nathann
comment:11 Changed 5 years ago by
sage: A = cartesian_product([ZZ, ZZ]) sage: elt = A((1,1)) sage: hash(elt) 3713081631935493181 sage: hash((1,1)) 3713081631935493181
comment:12 Changed 5 years ago by
Oh, okay okay then. I didn't see a hash function in the file, and so I wondered if we were sure that the parent was not involved.
comment:13 Changed 5 years ago by
The default hash of ElementWrapper
is the hash of the wrapper value.
comment:14 Changed 5 years ago by
 Status changed from needs_review to needs_work
Equality does not work (see patchbot report). And what about comment:9?
comment:15 Changed 5 years ago by
 Commit changed from 7466511b9ba67f2d6b8985fa0f4c641fb9e58978 to f1d029a3a3518265f1f88c2438bbc9b00c7ecd36
Branch pushed to git repo; I updated commit sha1. New commits:
f1d029a  Fixing me being dumb with super calls.

comment:16 Changed 5 years ago by
 Status changed from needs_work to needs_review
With regards to comment:9, we don't want them to be tuples because we want all of the category information to be inherited, e.g.
sage: C = cartesian_product([ZZ, ZZ]) sage: x = C.an_element() sage: x (1, 1) sage: x.is_one() True
comment:17 Changed 5 years ago by
I fully agree on the above example and there are many others. As you said, wrapping has a cost. Having an option looks reasonable
sage: C = cartesian_product([range(5), range(5)], with_elements_as_tuple=True) sage: C.element_class <type 'tuple'>
Though, I am just asking for your opinion. I am not considering it good for inclusion in this ticket.
On the other hand, with your laxism with respect to tuples the equality test is about 3x slower. We had
sage: C = cartesian_product([srange(5), srange(5)]) sage: c = C((1,1)) sage: d = C((1,1)) sage: e = C((1,2)) sage: %timeit c == d and c == e 1000000 loops, best of 3: 327 ns per loop
And with your branch
sage: %timeit c == d and c == e 100000 loops, best of 3: 1.93 µs per loop
If the comparison has to be touched, it has to be at the level of ElementWrapper
. Probably a new class.
comment:18 Changed 5 years ago by
 Commit changed from f1d029a3a3518265f1f88c2438bbc9b00c7ecd36 to 6a440d55060e2a7debbed41b22990951d8a3c6a5
Branch pushed to git repo; I updated commit sha1. New commits:
6a440d5  Added cython class which also does comparions on the wrapped class.

comment:19 followup: ↓ 20 Changed 5 years ago by
Ahh...the speed of Cython. I created a new class in between ElementWrapper
and CartesianProduct.Element
that has specialized equality comparisons against the wrapped class.
Current:
sage: C = cartesian_product([ZZ, ZZ]) sage: c = C((1, 1)) sage: d = C((1, 1)) sage: e = C((1, 2)) sage: %timeit c == d 1000000 loops, best of 3: 183 ns per loop sage: %timeit c == e 10000000 loops, best of 3: 183 ns per loop
vs old:
sage: %timeit c == d 1000000 loops, best of 3: 175 ns per loop sage: %timeit c == e 10000000 loops, best of 3: 179 ns per loop
So we might loose up to ~2%, but I think this will get lost in noise if someone is doing Cartesian products of things with any harder comparison operators. (Although IMO the previous slowdown would likely have been negligible in computations (at least I would recommend using itertools
and tuple
s if this was an issue)).
As suggested in the parenthetical, if you wanted this to be a facade parent for tuples, which is I think what you would end up with, then you likely could just use itertools
.
comment:20 in reply to: ↑ 19 Changed 5 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
Replying to tscrim:
As suggested in the parenthetical, if you wanted this to be a facade parent for tuples, which is I think what you would end up with, then you likely could just use
itertools
.
But itertools does not care about rank
, unrank
, __contains__
. Python iterators might not be rich enough.
Vincent
comment:21 Changed 5 years ago by
Well, we'll see if such a situation arises. Thanks for the review.
comment:22 Changed 5 years ago by
 Branch changed from public/sets/contains_cartesian_product19555 to 6a440d55060e2a7debbed41b22990951d8a3c6a5
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Implement a containment check for cartesian_product.