Opened 7 months ago

Closed 4 months ago

#26639 closed enhancement (fixed)

geometry/cone.py: use generator expressions and future-proof range() iterator

Reported by: mjo Owned by:
Priority: major Milestone: sage-8.7
Component: geometry Keywords:
Cc: novoselt, chapoton Merged in:
Authors: Michael Orlitzky Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 7b51289 (Commits) Commit: 7b512897c453982d4a21ac0ed74b60c49c00e8ad
Dependencies: Stopgaps:

Description

We have a lot of lists that don't need to be lists in geometry/cone.py, potentially slowing things down and wasting a bit of memory. This is especially prevalent in my own doctests (oops).

Two things should help:

  1. Use generator expressions instead of list comprehensions when we're merely iterating over things.
  2. Use xrange-type iterators instead of range() lists. This is complicated only by the fact that xrange() isn't future-proof with respect to python-3.x.

Change History (9)

comment:1 Changed 7 months ago by mjo

  • Authors set to Michael Orlitzky
  • Branch set to u/mjo/ticket/26639
  • Cc novoselt chapoton added
  • Commit set to 474b3356c7a55ed34bf8525747b6dc37a82d746a
  • Status changed from new to needs_review
  • Summary changed from geometry/cones.py: use generator expressions and future-proof range() iterator to geometry/cone.py: use generator expressions and future-proof range() iterator

Frédéric, please make sure I'm not doing something stupid with the range import.

comment:2 Changed 7 months ago by mjo

By the way, I should warn the reviewer: in the following hunk,

@@ -5519,17 +5524,16 @@ class ConvexRationalPolyhedralCone(IntegralRayCollection,
             sage: L = ToricLattice(m*n)
             sage: M1 = MatrixSpace(F, m, m)
             sage: M2 = MatrixSpace(F, n, n)
-            sage: LL_K1 = [ M1(x.list())
-            ....:           for x in K1.dual().lyapunov_like_basis() ]
-            sage: LL_K2 = [ M2(x.list()) for x in K2.lyapunov_like_basis() ]
-            sage: tps = [ s.tensor_product(x) for x in LL_K1 for s in LL_K2 ]
+            sage: tps = ( M2(s.list()).tensor_product(M1(x.list()))
+            ....:             for x in K1.dual().lyapunov_like_basis()
+            ....:             for s in K2.lyapunov_like_basis() )
             sage: W = VectorSpace(F, (m**2)*(n**2))
-            sage: expected = span(F, [ W(x.list()) for x in tps ])
-            sage: pi_cone = Cone([g.list() for g in pi_gens],
+            sage: expected = span(F, ( W(x.list()) for x in tps ))
+            sage: pi_cone = Cone((g.list() for g in pi_gens),
             ....:                lattice=L,
             ....:                check=False)
             sage: LL_pi = pi_cone.lyapunov_like_basis()
-            sage: actual = span(F, [ W(x.list()) for x in LL_pi ])
+            sage: actual = span(F, ( W(x.list()) for x in LL_pi ))
             sage: actual == expected
             True
         """

I did initially try the simpler change, to make LL_K1 and LL_K2 use generator expressions individually. But, that broke the test in a way that I don't understand. I don't like mysteries. Before merging this, we should know why that breaks, so that we can be sure it doesn't affect any of the other changes I made.

comment:3 Changed 7 months ago by chapoton

Rather use from six.moves import range

Beware of the risk of conflict with the other ticket about the very same file.

comment:4 Changed 7 months ago by git

  • Commit changed from 474b3356c7a55ed34bf8525747b6dc37a82d746a to 7b512897c453982d4a21ac0ed74b60c49c00e8ad

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

65f4f7bpy3: fix doctests in geometry/cone
e63b0ceTrac #26639: use future-proof range() iterator in geometry/cone.py
5fa22d5Trac #26639: add two missing set_random_seed() calls to geometry/cone.py.
7b51289Trac #26639: use PEP 289 generator expressions in geometry/cone.py.

comment:5 Changed 7 months ago by mjo

  • Dependencies set to 26636

Thanks, I rebased onto your branch and force pushed.

comment:6 Changed 7 months ago by chapoton

  • Dependencies changed from 26636 to #26636

comment:7 Changed 7 months ago by mjo

To address my previous concern, the failure in comment 2 was due to an implementation detail that we need to be aware of. When I write,

LL_K1 = ( M1(x.list()) for x in K1.dual().lyapunov_like_basis() )
LL_K2 = ( M2(x.list()) for x in K2.lyapunov_like_basis() )
tps_gen = ( s.tensor_product(x) for x in LL_K1 for s in LL_K2 )

where LL_K1 and LL_K2 are generators (as opposed to lists) python will loop through the inner iterator multiple times for every item in the outer iterator. That doesn't work: the inner iterator is exhausted the first time around, and returns nothing for outer iterations 2, 3, etc.

So the situations we need to watch out for are:

  1. Don't return an iterator anywhere that we used to return a list (in case anyone is using the result in a nested loop).
  1. Don't turn two lists into generator expressions if they're later going to be used in a nested loop.

I've looked through the rest of the changes and don't think I made the same mistake anywhere else.

comment:8 Changed 4 months ago by chapoton

  • Dependencies #26636 deleted
  • Milestone changed from sage-8.5 to sage-8.7
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:9 Changed 4 months ago by vbraun

  • Branch changed from u/mjo/ticket/26639 to 7b512897c453982d4a21ac0ed74b60c49c00e8ad
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.