Opened 5 years ago

Closed 5 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 5 years ago by ncohen

  • Branch set to u/ncohen/15332
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 2bed8dcf4aba1534081a5c047d8f7993e4b3e16f

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

[changeset:2bed8dc]Poset.lt computes too much
[changeset:2fc96d4]Poset.is_chain is wrong and other details

comment:3 Changed 5 years ago by darij

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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 2bed8dcf4aba1534081a5c047d8f7993e4b3e16f to 6d75c23822d2a11a434f6791214e88ee7d1b3c28

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

6d75c23Poset.lt computes too much
2fc96d4Poset.is_chain is wrong and other details

comment:6 Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 6d75c23822d2a11a434f6791214e88ee7d1b3c28 to 2286c10767b69e51430a36baded02bee6e6ab9d5

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

2286c10Rebase on 5.13.beta2

comment:8 Changed 5 years ago by darij

  • 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:10 Changed 5 years ago by vbraun

  • Reviewers set to Darij Grinberg

comment:11 Changed 5 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.