Speed up computing outside corners of partition

[trevorkarn]

Speed up the code for getting the corners of a partition.

CC: @tscrim

Component: combinatorics

Keywords: gsoc2022 partition optimization

Author: Trevor K. Karn

Branch/Commit: bde6bb5

Reviewer: Travis Scrimshaw

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

[sagetrac-git]

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

434071a

Rewrite loop computing outside corners

[sagetrac-git]

Commit: 434071a

[trevorkarn]

comment:2

With change:

sage: mu = Partition(range(100,0,-1))
sage: %lprun -f mu.outside_corners mu.outside_corners()
Timer unit: 1e-06 s

Total time: 0.000114 s
File: /Users/trevorkarn/Applications/sage/src/sage/combinat/partition.py
Function: outside_corners at line 4006

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  4006                                               def outside_corners(self):
  4007                                                   r"""
  4008                                                   Return a list of the outside corners of the partition ``self``.
  4009                                           
  4010                                                   An outside corner (also called a cocorner) of a partition
  4011                                                   `\lambda` is a cell on `\ZZ^2` which does not belong to
  4012                                                   the Young diagram of `\lambda` but can be added to this Young
  4013                                                   diagram to still form a straight-shape Young diagram.
  4014                                           
  4015                                                   The entries of the list returned are pairs of the form `(i,j)`,
  4016                                                   where `i` and `j` are the coordinates of the respective corner.
  4017                                                   The coordinates are counted from `0`.
  4018                                           
  4019                                                   EXAMPLES::
  4020                                           
  4021                                                       sage: Partition([2,2,1]).outside_corners()
  4022                                                       [(0, 2), (2, 1), (3, 0)]
  4023                                                       sage: Partition([2,2]).outside_corners()
  4024                                                       [(0, 2), (2, 0)]
  4025                                                       sage: Partition([6,3,3,1,1,1]).outside_corners()
  4026                                                       [(0, 6), (1, 3), (3, 1), (6, 0)]
  4027                                                       sage: Partition([]).outside_corners()
  4028                                                       [(0, 0)]
  4029                                                   """
  4030         1          6.0      6.0      5.3          p = self
  4031         1          8.0      8.0      7.0          if p.is_empty():
  4032                                                       return [(0,0)]
  4033         1          3.0      3.0      2.6          res = [(0, p[0])]
  4034         1         93.0     93.0     81.6          res.extend((n, j) for n, (i, j) in enumerate(zip(p[:-1], p[1:]), start=1) if i != j)
  4035         1          3.0      3.0      2.6          res.append((len(p), 0))
  4036         1          1.0      1.0      0.9          return res

vs before:

Timer unit: 1e-06 s

Total time: 0.000405 s
File: /Users/trevorkarn/Applications/sage/src/sage/combinat/partition.py
Function: outside_corners at line 4006

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  4006                                               def outside_corners(self):                                               
  ....
  4030         1          3.0      3.0      0.7          p = self
  4031         1          9.0      9.0      2.2          if p.is_empty():
  4032                                                       return [(0,0)]
  4033         1          3.0      3.0      0.7          res = [ (0, p[0]) ]
  4034       100         75.0      0.8     18.5          for i in range(1, len(p)):
  4035        99        168.0      1.7     41.5              if p[i-1] != p[i]:
  4036        99        145.0      1.5     35.8                  res.append((i,p[i]))
  4037         1          2.0      2.0      0.5          res.append((len(p), 0))
  4038                                           
  4039         1          0.0      0.0      0.0          return res

---

New commits:

434071a

Rewrite loop computing outside corners

---

New commits:

434071a

Rewrite loop computing outside corners

[trevorkarn]

comment:4

sage: mu = Partition(range(100,0,-1))
sage: %lprun -f mu.outside_corners mu.outside_corners()

  4030         1         11.0     11.0      7.0          from itertools import islice
  4031         1          5.0      5.0      3.2          p = self._list
  4032         1          2.0      2.0      1.3          if not p:
  4033                                                       return [(0,0)]
  4034         1          1.0      1.0      0.6          res = [(0, p[0])]
  4035         2        128.0     64.0     81.0          res.extend((n, j) for n, (i, j)
  4036         1          8.0      8.0      5.1                     in enumerate(zip(islice(p, 0, len(p)-1), islice(p, 1, len(p))), start=1)
  4037                                                              if i != j)
  4038         1          2.0      2.0      1.3          res.append((len(p), 0))
  4039         1          1.0      1.0      0.6          return res

[trevorkarn]

comment:5

sage: mu = Partition(range(100000,0,-1))
sage: %lprun -f mu.outside_corners mu.outside_corners()
Timer unit: 1e-06 s

Total time: 0.163733 s
File: /Users/trevorkarn/Applications/sage/src/sage/combinat/partition.py
Function: outside_corners at line 4006

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  4030         1         10.0     10.0      0.0          p = self._list
  4031         1          2.0      2.0      0.0          if not p:
  4032                                                       return [(0,0)]
  4033         1          2.0      2.0      0.0          res = [(0, p[0])]
  4034         1     163711.0 163711.0    100.0          res.extend((n, j) for n, (i, j) in enumerate(zip(p[:-1], p[1:]), start=1) if i != j)
  4035         1          8.0      8.0      0.0          res.append((len(p), 0))
  4036         1          0.0      0.0      0.0          return res

It seems like making p = self._list and then using normal slicing (rather than islice) is the fastest.

Compare to

sage: mu = Partition(range(100000,0,-1))
sage: %lprun -f mu.outside_corners mu.outside_corners()
Timer unit: 1e-06 s

Total time: 0.191122 s
File: /Users/trevorkarn/Applications/sage/src/sage/combinat/partition.py
Function: outside_corners at line 4006

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  4030         1          7.0      7.0      0.0          from itertools import islice
  4031         1          2.0      2.0      0.0          p = self._list
  4032         1          1.0      1.0      0.0          if not p:
  4033                                                       return [(0,0)]
  4034         1          1.0      1.0      0.0          res = [(0, p[0])]
  4035         2     191099.0  95549.5    100.0          res.extend((n, j) for n, (i, j)
  4036         1          5.0      5.0      0.0                     in enumerate(zip(islice(p, 0, len(p)-1), islice(p, 1, len(p))), start=1)
  4037                                                              if i != j)
  4038         1          7.0      7.0      0.0          res.append((len(p), 0))
  4039         1          0.0      0.0      0.0          return res

sage: mu = Partition(range(100000,0,-1))
sage: %lprun -f mu.outside_corners mu.outside_corners()
Timer unit: 1e-06 s

Total time: 0.174545 s
File: /Users/trevorkarn/Applications/sage/src/sage/combinat/partition.py
Function: outside_corners at line 4006

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  4030         1          6.0      6.0      0.0          p = self
  4031         1         11.0     11.0      0.0          if p.is_empty():
  4032                                                       return [(0,0)]
  4033         1          3.0      3.0      0.0          res = [(0, p[0])]
  4034         1     174511.0 174511.0    100.0          res.extend((n, j) for n, (i, j) in enumerate(zip(p[:-1], p[1:]), start=1) if i != j)
  4035         1         14.0     14.0      0.0          res.append((len(p), 0))
  4036         1          0.0      0.0      0.0          return res

[sagetrac-git]

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

bde6bb5

Change to list

[sagetrac-git]

Changed commit from 434071a to bde6bb5

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:7

Let it be so.

[vbraun]

Changed branch from u/tkarn/partition-corners-202208 to bde6bb5