Speedup adding horizontal and vertical border strips

[tscrim]

We can be better about the number of conjugations involved.

CC: @trevorkarn @anneschilling @nthiery @darijgr @zabrocki

Component: performance

Keywords: combinat, partition

Author: Travis Scrimshaw

Branch/Commit: 5e52832

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/34339

[tscrim]

comment:1

With my branch, this is now

sage: %timeit Partition([2,2]).add_vertical_border_strip(2)
57.9 µs ± 484 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit Partition([3,2,2]).add_vertical_border_strip(2)
101 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit Partition([7,4,2,2,2,1,1]).add_vertical_border_strip(5)  # 43 partitions
871 µs ± 6.03 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

sage: %timeit Partition([2,2]).add_horizontal_border_strip(2)
54.6 µs ± 388 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit Partition([3,2,2]).add_horizontal_border_strip(2)
99.3 µs ± 1.01 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit Partition([7,4,2,2,2,1,1]).add_horizontal_border_strip(5)  # 43 partitions
908 µs ± 3.09 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit Partition([5,4,3,2,1]).add_horizontal_border_strip(5)  # 32 partitions
769 µs ± 2.95 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

versus before:

109 µs ± 650 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
170 µs ± 1.31 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
1.32 ms ± 5.69 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

99.2 µs ± 773 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
158 µs ± 559 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
1.15 ms ± 4.29 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
997 µs ± 4.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

The output order of the add_horizontal_border_strip() has changed, but this should be inconsequential.

---

New commits:

6ccd9e4

Optimization of add_*_border_strip() and doctest update.

[tscrim]

Commit: 6ccd9e4

[tscrim]

Branch: public/combinat/speedup_adding_strips-34339

[fchapoton]

comment:2

pathbot reports a failing doctest in src/sage/tests/book_schilling_zabrocki_kschur_primer

[sagetrac-git]

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

5e52832

Fixing order of k_atoms in k-Schur book.

[sagetrac-git]

Changed commit from 6ccd9e4 to 5e52832

[tscrim]

comment:4

Fixed.

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:5

ok, let's move on

[tscrim]

comment:6

Thank you.

[vbraun]

Changed branch from public/combinat/speedup_adding_strips-34339 to 5e52832