Opened 5 years ago

Closed 5 years ago

#19555 closed enhancement (fixed)

Implement a containment for cartesian_product

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-6.10
Component: combinatorics Keywords:
Cc: sage-combinat, 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 tscrim

  • Branch set to public/sets/contains_cartesian_product-19555
  • Commit set to fb14675d6a264ca2405cebbcdb62a3eddfadd1f4
  • Status changed from new to needs_review

New commits:

fb14675Implement a containment check for cartesian_product.

comment:2 follow-up: Changed 5 years ago by 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?

Nathann

comment:3 Changed 5 years ago by ncohen

  • Cc vdelecroix added

comment:4 in reply to: ↑ 2 Changed 5 years ago by vdelecroix

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 tscrim

The issue of the element constructor is worked around on #19554 (see #19553 for the general issue).

comment:6 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info
  1. What is the rationale for having tuple being considered as elements of the cartesian product?
  1. With this version __contains__ and Element.__eq__ are not compatible
    sage: (1,1) in C
    True
    sage: any(x == (1,1) for x in C)
    False
    

comment:7 Changed 5 years ago by git

  • Commit changed from fb14675d6a264ca2405cebbcdb62a3eddfadd1f4 to 7466511b9ba67f2d6b8985fa0f4c641fb9e58978

Branch pushed to git repo; I updated commit sha1. New commits:

23f5c7eMerge branch 'public/sets/contains_cartesian_product-19555' of trac.sagemath.org:sage into public/sets/contains_cartesian_product-19555
7466511Adding a check for equality with tuples.

comment:8 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by tscrim

  • Status changed from needs_info to needs_review

Replying to vdelecroix:

  1. 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.

  1. With this version __contains__ and Element.__eq__ are not compatible
    sage: (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 vdelecroix

Replying to tscrim:

Replying to vdelecroix:

  1. 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 ncohen

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 tscrim

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 ncohen

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 tscrim

The default hash of ElementWrapper is the hash of the wrapper value.

comment:14 Changed 5 years ago by vdelecroix

  • 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 git

  • Commit changed from 7466511b9ba67f2d6b8985fa0f4c641fb9e58978 to f1d029a3a3518265f1f88c2438bbc9b00c7ecd36

Branch pushed to git repo; I updated commit sha1. New commits:

f1d029aFixing me being dumb with super calls.

comment:16 Changed 5 years ago by tscrim

  • 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 vdelecroix

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 git

  • Commit changed from f1d029a3a3518265f1f88c2438bbc9b00c7ecd36 to 6a440d55060e2a7debbed41b22990951d8a3c6a5

Branch pushed to git repo; I updated commit sha1. New commits:

6a440d5Added cython class which also does comparions on the wrapped class.

comment:19 follow-up: Changed 5 years ago by tscrim

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 tuples 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 vdelecroix

  • 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 tscrim

Well, we'll see if such a situation arises. Thanks for the review.

comment:22 Changed 5 years ago by vbraun

  • Branch changed from public/sets/contains_cartesian_product-19555 to 6a440d55060e2a7debbed41b22990951d8a3c6a5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.