Opened 6 years ago

Closed 6 years ago

#11382 closed defect (fixed)

Speedup subposet and _vertex_to_element

Reported by: hivert Owned by: hivert
Priority: major Milestone: sage-5.0
Component: combinatorics Keywords: poset, subposet, Cernay2012
Cc: sage-combinat Merged in: sage-5.0.beta5
Authors: Florent Hivert Reviewers: Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10998 Stopgaps:

Description (last modified by nthiery)

A lot of unnecessary and redundant check were performed with a preliminary version of #10998. See a more precise analyze on this thread of sage-combinat-devel

sage: P = cutting_poset(WeylGroup(['A',3]))
sage: P.cardinality()
24

Before:

sage: %timeit P.subposet(P.list()[1:])
5 loops, best of 3: 214 ms per loop

After:

sage: %timeit P.subposet(P.list()[1:])
25 loops, best of 3: 24.8 ms per loop

Here is another timing for a bigger poset:

sage: P = cutting_poset(WeylGroup(['A',4]))
sage: P.cardinality()
120

Before:

sage: %timeit P.subposet(P.list()[1:])
5 loops, best of 3: 28.8 s per loop

After:

sage: %timeit P.subposet(P.list()[1:])
5 loops, best of 3: 597 ms per loop

This is basically fixed in the final version of #10998 (run on a slightly slower machine than for the above timings):

sage: %timeit P.subposet(P.list()[1:])
5 loops, best of 3: 801 ms per loop

The attached patch optimizes it a tiny bit further and adds doctests:

sage: %timeit P.subposet(P.list()[1:])
5 loops, best of 3: 688 ms per loop

Apply: trac_11382-subposet_to_vertex_speedup-fh.patch

Attachments (1)

trac_11382-subposet_to_vertex_speedup-fh.patch (3.6 KB) - added by nthiery 6 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 6 years ago by hivert

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by hivert

  • Summary changed from subposet is too slow to Speedup subposet and _vertex_to_element

comment:3 Changed 6 years ago by hivert

  • Dependencies set to #10998
  • Owner changed from sage-combinat to (none)

comment:4 Changed 6 years ago by hivert

  • Owner changed from (none) to hivert

comment:5 Changed 6 years ago by hivert

  • Keywords Cernay2012 added

comment:6 Changed 6 years ago by nthiery

  • Description modified (diff)
  • Reviewers set to Nicolas M. Thiéry

comment:7 Changed 6 years ago by nthiery

  • Description modified (diff)

comment:8 Changed 6 years ago by nthiery

  • Description modified (diff)

comment:9 Changed 6 years ago by nthiery

We finalized the patch together with Florent. Positive review on the version I just uploaded, assuming the test pass (I am running them).

comment:10 Changed 6 years ago by hivert

  • Status changed from needs_review to positive_review

comment:11 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.0.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.