Opened 6 years ago
Closed 6 years ago
#15332 closed defect (fixed)
Poset.lt computes too much
Reported by: | ncohen | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.1 |
Component: | combinatorics | Keywords: | |
Cc: | darij, sage-combinat, nthiery, fhivert | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | Darij Grinberg |
Report Upstream: | N/A | Work issues: | |
Branch: | u/ncohen/15332 (Commits) | Commit: | 2286c10767b69e51430a36baded02bee6e6ab9d5 |
Dependencies: | #15330 | Stopgaps: |
Description
Poset.lt(x,y)
also wonder whether x>y
and nobody asked it to.
Change History (11)
comment:1 Changed 6 years ago by
- Branch set to u/ncohen/15332
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Commit set to 2bed8dcf4aba1534081a5c047d8f7993e4b3e16f
comment:3 Changed 6 years ago by
Before:
sage: P = Posets.BooleanLattice(4) sage: %timeit [P.le(i, j) for i in P for j in P] 1000 loops, best of 3: 847 us per loop
After:
sage: P = Posets.BooleanLattice(4) sage: %timeit [P.le(i, j) for i in P for j in P] 1000 loops, best of 3: 1.13 ms per loop
There is probably something inefficient about shortest_path
that was done better with the breadth-first iterator?
comment:4 Changed 6 years ago by
Arggggggg. Stupid me. Not only did I forget that breadth-first search was an iterator, but I somehow read the code and convinced myself that it called shortest_path somewhere, hence that I was better off calling it directly.
I will give it another look and if I can't do anything better than the current implementation (which is very likely) then I will remove this stupid change. Thanks for checking !!!
Nathann
comment:5 Changed 6 years ago by
- Commit changed from 2bed8dcf4aba1534081a5c047d8f7993e4b3e16f to 6d75c23822d2a11a434f6791214e88ee7d1b3c28
comment:6 Changed 6 years ago by
Sorry for that. I just updated the last commit without this stupid change. Thanks for saving my skin :-P
This can be made a bit more efficient later, when Posets will use static graph backend instead of the current immutable one. Not by a lot though :-)
Nathann
comment:7 Changed 6 years ago by
- Commit changed from 6d75c23822d2a11a434f6791214e88ee7d1b3c28 to 2286c10767b69e51430a36baded02bee6e6ab9d5
Branch pushed to git repo; I updated commit sha1. New commits:
2286c10 | Rebase on 5.13.beta2 |
comment:8 Changed 6 years ago by
- Status changed from needs_review to positive_review
Very nice! Now I do see the almost-50% improvement.
P = Posets.BooleanLattice(4) %timeit [P.le(i, j) for i in P for j in P] %timeit [P.lt(i, j) for i in P for j in P] %timeit [P.ge(i, j) for i in P for j in P] %timeit [P.gt(i, j) for i in P for j in P] P = RootSystem(['A', 4]).root_poset() %timeit [P.le(i, j) for i in P for j in P] %timeit [P.lt(i, j) for i in P for j in P] %timeit [P.ge(i, j) for i in P for j in P] %timeit [P.gt(i, j) for i in P for j in P] P = Poset({1: [2, 3]}) %timeit [P.le(i, j) for i in P for j in P] %timeit [P.lt(i, j) for i in P for j in P] %timeit [P.ge(i, j) for i in P for j in P] %timeit [P.gt(i, j) for i in P for j in P] before: sage: P = Posets.BooleanLattice(4) sage: %timeit [P.le(i, j) for i in P for j in P] 100 loops, best of 3: 1.65 ms per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 1000 loops, best of 3: 1.58 ms per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 1000 loops, best of 3: 1.6 ms per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 1000 loops, best of 3: 1.56 ms per loop sage: P = RootSystem(['A', 4]).root_poset() sage: %timeit [P.le(i, j) for i in P for j in P] 1000 loops, best of 3: 1.39 ms per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 1000 loops, best of 3: 1.39 ms per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 1000 loops, best of 3: 1.39 ms per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 1000 loops, best of 3: 1.38 ms per loop sage: P = Poset({1: [2, 3]}) sage: %timeit [P.le(i, j) for i in P for j in P] 10000 loops, best of 3: 98.8 us per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 10000 loops, best of 3: 96.7 us per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 10000 loops, best of 3: 96.9 us per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 10000 loops, best of 3: 96.7 us per loop after: sage: P = Posets.BooleanLattice(4) sage: %timeit [P.le(i, j) for i in P for j in P] 1000 loops, best of 3: 810 us per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 1000 loops, best of 3: 890 us per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 1000 loops, best of 3: 840 us per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 1000 loops, best of 3: 890 us per loop sage: P = RootSystem(['A', 4]).root_poset() sage: %timeit [P.le(i, j) for i in P for j in P] 1000 loops, best of 3: 698 us per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 1000 loops, best of 3: 734 us per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 1000 loops, best of 3: 702 us per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 1000 loops, best of 3: 736 us per loop sage: P = Poset({1: [2, 3]}) sage: %timeit [P.le(i, j) for i in P for j in P] 10000 loops, best of 3: 50.9 us per loop sage: %timeit [P.lt(i, j) for i in P for j in P] 10000 loops, best of 3: 54.9 us per loop sage: %timeit [P.ge(i, j) for i in P for j in P] 10000 loops, best of 3: 51.2 us per loop sage: %timeit [P.gt(i, j) for i in P for j in P] 10000 loops, best of 3: 55.2 us per loop
comment:9 Changed 6 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:10 Changed 6 years ago by
- Reviewers set to Darij Grinberg
comment:11 Changed 6 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits: