Ticket #11382 (closed defect: fixed)

Opened 2 years ago

Last modified 15 months ago

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 Work issues:
Report Upstream: N/A Reviewers: Nicolas M. Thiéry
Authors: Florent Hivert Merged in: sage-5.0.beta5
Dependencies: #10998 Stopgaps:

Description (last modified by nthiery) (diff)

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 Download

Attachments

trac_11382-subposet_to_vertex_speedup-fh.patch Download (3.6 KB) - added by nthiery 16 months ago.

Change History

comment:1 Changed 2 years ago by hivert

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

comment:2 Changed 2 years ago by hivert

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

comment:3 Changed 2 years ago by hivert

  • Owner sage-combinat deleted
  • Dependencies set to #10998

comment:4 Changed 18 months ago by hivert

  • Owner set to hivert

comment:5 Changed 16 months ago by hivert

  • Keywords poset, subposet, Cernay2012 added; poset subposet removed

comment:6 Changed 16 months ago by nthiery

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

comment:7 Changed 16 months ago by nthiery

  • Description modified (diff)

comment:8 Changed 16 months ago by nthiery

  • Description modified (diff)

comment:9 Changed 16 months 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).

Changed 16 months ago by nthiery

comment:10 Changed 16 months ago by hivert

  • Status changed from needs_review to positive_review

comment:11 Changed 15 months ago by jdemeyer

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