Opened 6 years ago
Closed 6 years ago
#20110 closed enhancement (fixed)
Speed up Polyhedron_base.graph()
| Reported by: | jplitza | Owned by: | |
|---|---|---|---|
| Priority: | trivial | Milestone: | sage-7.1 |
| Component: | geometry | Keywords: | |
| Cc: | Merged in: | ||
| Authors: | Jan-Philipp Litza | Reviewers: | Volker Braun |
| Report Upstream: | N/A | Work issues: | |
| Branch: | 0a2602f (Commits, GitHub, GitLab) | Commit: | 0a2602fcba8d18b204dbcd23f8a106f9bc63d55d |
| Dependencies: | Stopgaps: |
Status badges
Description
Currently, Polyhedron_base.graph() intersects with the base set of all vertices in every of the n over 2 loop iterations in line 3321, where n is the number of vertices. This is useless as far as I can see, because the sets that are being intersected cannot possibly ever contain something that is not a vertex.
Leaving out this additional intersection speeds up the process of constructing the graph significantly. I tested it on a 4 GHz machine for the polyhedron polytopes.associahedron(['E', 7]), and with my patch it only took close to two minutes instead of 5:15. Other examples like polytopes.associahedron(['E', 8]) also suggest a significant speedup, although I don't have precise measurements from the same machine.
I also tested that the resulting graph is actually the same for some polyhedra.
Change History (6)
comment:1 Changed 6 years ago by
comment:2 Changed 6 years ago by
- Status changed from new to needs_review
comment:3 Changed 6 years ago by
- Reviewers set to Volker Braun
Can you fill in the "Author" field with your real name?
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:6 Changed 6 years ago by
- Branch changed from u/jplitza/polyhedron_graph to 0a2602fcba8d18b204dbcd23f8a106f9bc63d55d
- Resolution set to fixed
- Status changed from positive_review to closed
Looks good to me. I assume tests pass. You should set tickets to "needs review" when you are ready...