refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class by kliem · Pull Request #35073 · sagemath/sage

kliem · 2023-02-11T11:38:36Z

📚 Description

CombinatorialPolyhedron currently contains a lot of code related to (possibly long) lists of pairs. This code can and should be moved elsewhere. This is a step towards better readability and allowing future changes to the code.

This is a first step of #34773.

Along the way I update my outdated email address.

📝 Checklist

I have made sure that the title is self-explanatory and the description concisely explains the PR.
I have linked an issue or discussion.
I have created tests covering the changes.
I have updated the documentation accordingly.

⌛ Dependencies

codecov-commenter · 2023-02-11T14:12:35Z

Codecov Report

Base: 88.59% // Head: 88.58% // Decreases project coverage by -0.02% ⚠️

Coverage data is based on head (f01ed7d) compared to base (05329f6).
Patch has no changes to coverable lines.

❗ Current head f01ed7d differs from pull request most recent head 0a710d3. Consider uploading reports for the commit 0a710d3 to get more accurate results

Additional details and impacted files

@@             Coverage Diff             @@
##           develop   #35073      +/-   ##
===========================================
- Coverage    88.59%   88.58%   -0.02%     
===========================================
  Files         2140     2140              
  Lines       396998   396961      -37     
===========================================
- Hits        351740   351632     -108     
- Misses       45258    45329      +71

Impacted Files	Coverage Δ
src/sage/geometry/polyhedron/base.py	`93.20% <ø> (ø)`
src/sage/geometry/polyhedron/base0.py	`94.97% <ø> (ø)`
src/sage/geometry/polyhedron/base1.py	`89.06% <ø> (ø)`
src/sage/geometry/polyhedron/base2.py	`95.31% <ø> (ø)`
src/sage/geometry/polyhedron/base3.py	`94.78% <ø> (ø)`
src/sage/geometry/polyhedron/base4.py	`57.32% <ø> (ø)`
src/sage/geometry/polyhedron/base5.py	`93.17% <ø> (ø)`
src/sage/geometry/polyhedron/base6.py	`92.00% <ø> (ø)`
src/sage/geometry/polyhedron/base7.py	`46.69% <ø> (ø)`
src/sage/graphs/generic_graph.py	`89.12% <ø> (-0.02%)`	⬇️
... and 36 more

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

☔ View full report at Codecov.
📢 Do you have feedback about the report comment? Let us know in this issue.

…cated_class

src/sage/data_structures/binary_list.pyx

…_list_of_pairs_to_dedicated_class' into refactor/34773/move_list_of_pairs_to_dedicated_class

tscrim

While the changes here are unlikely to have any major net change on the timings, nevertheless it would be good to check on an example or two.

tscrim · 2023-02-13T11:20:11Z

src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx

-        cdef size_t j
        if add_equations and names:
-            # Also getting the equations for each facet.
-            return tuple(
-                (((facet_one(i),) + self.equations()),
-                 ((facet_two(i),) + self.equations()))
-                for i in range(n_ridges))
+            def get_ridge(size_t i):
+                ridge = self._ridges.get(i)[0]
+                return ((f(ridge.first),) + self.equations(),
+                        (f(ridge.second),) + self.equations())
+
        else:
-            return tuple((facet_one(i), facet_two(i))
-                         for i in range(n_ridges))
+            def get_ridge(size_t i):
+                ridge = self._ridges.get(i)[0]
+                return (f(ridge.first), f(ridge.second))
+
+        cdef size_t j
+        return tuple(get_ridge(j) for j in range(n_ridges))


I am not sure about these changes. They seem to slow it down (extra Python function calls) and is at best a net zero improvement to readability (I would actually argue it makes it more complicated). Although I guess you are halving the number of function calls, but I think it would be better to just have the two cases do a return.

Improved in 2367bc9.

tscrim · 2023-02-13T11:21:15Z

src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx

-            while (dimension_one < dim + 1):
-                already_seen = sum(f_vector[j] for j in range(dimension_two + 1))
-                already_seen_next = already_seen + f_vector[dimension_two + 1]
+        while (dimension_one < dim + 1):


Suggested change

while (dimension_one < dim + 1):

while dimension_one < dim + 1:

Done in 2367bc9.

kliem · 2023-02-13T19:41:33Z

src/sage/data_structures/list_of_pairs.pyx

+        self._lists[n_lists] = <pair_s*> check_allocarray(length_per_list, sizeof(pair_s))
+        self.length += 1
+
+    cdef inline pair_s* get(self, size_t index) except NULL:


Done in 2367bc9.

kliem · 2023-02-13T19:40:44Z

src/sage/data_structures/list_of_pairs.pyx

+        cdef size_t first, second
+        (first, second) = value
+
+        if (index == self.length):


Done in 2367bc9.

…cated_class

kliem · 2023-02-13T19:54:34Z

While the changes here are unlikely to have any major net change on the timings, nevertheless it would be good to check on an example or two.

I did, but of course it valuable to share this

Before:

sage: P = polytopes.permutahedron(8, backend='field')
sage: %timeit C = CombinatorialPolyhedron(P); C.edges()
1.08 s ± 22.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit C = CombinatorialPolyhedron(P); C.ridges()
634 ms ± 58 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

After:

sage: P = polytopes.permutahedron(8, backend='field')
sage: %timeit C = CombinatorialPolyhedron(P); C.edges()
1.06 s ± 20.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit C = CombinatorialPolyhedron(P); C.ridges() 
626 ms ± 6.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

tscrim · 2023-02-14T01:48:20Z

Thank you. LGTM.

kliem · 2023-02-14T06:54:36Z

Thank you.

…cated_class

github-actions · 2023-02-20T07:23:38Z

Documentation preview for this PR is ready! 🎉
Built with commit: 0a710d3

kliem added 2 commits February 11, 2023 10:04

fix: Update email adresses

d127e67

refactor: Move list of pairs to dedicated class

2f2732e

kliem mentioned this pull request Feb 11, 2023

Dual algorithm for Face iterator of Unbounded Combinatorial Polyhedron #34773

Open

Merge branch 'develop' into refactor/34773/move_list_of_pairs_to_dedi…

bba1593

…cated_class

mkoeppe reviewed Feb 11, 2023

View reviewed changes

src/sage/data_structures/binary_list.pyx Show resolved Hide resolved

kliem added 2 commits February 12, 2023 11:02

refactor: BinaryList -> ListOfPairs

1ef47d1

Merge remote-tracking branch 'refs/remotes/origin/refactor/34773/move…

1017ab7

…_list_of_pairs_to_dedicated_class' into refactor/34773/move_list_of_pairs_to_dedicated_class

kliem added s: needs review c: geometry labels Feb 12, 2023

tscrim requested changes Feb 13, 2023

View reviewed changes

kliem added 3 commits February 13, 2023 20:27

improvements suggested by reviewer

2367bc9

use attribute access to derefence

98974d5

Merge branch 'develop' into refactor/34773/move_list_of_pairs_to_dedi…

f01ed7d

…cated_class

kliem requested a review from tscrim February 13, 2023 19:55

tscrim approved these changes Feb 14, 2023

View reviewed changes

tscrim added p: major / 3 s: positive review t: refactoring and removed s: needs review labels Feb 14, 2023

Merge branch 'develop' into refactor/34773/move_list_of_pairs_to_dedi…

0a710d3

…cated_class

vbraun merged commit 39b4912 into sagemath:develop Mar 13, 2023

	while (dimension_one < dim + 1):
	while dimension_one < dim + 1:

Uh oh!

Conversation

kliem commented Feb 11, 2023

📚 Description

📝 Checklist

⌛ Dependencies

Uh oh!

codecov-commenter commented Feb 11, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

tscrim left a comment

Choose a reason for hiding this comment

Uh oh!

tscrim Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

kliem Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

tscrim Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

kliem Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

This comment was marked as resolved.

Uh oh!

kliem Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

This comment was marked as resolved.

Uh oh!

kliem Feb 13, 2023

Choose a reason for hiding this comment

Uh oh!

kliem commented Feb 13, 2023

Uh oh!

tscrim commented Feb 14, 2023

Uh oh!

kliem commented Feb 14, 2023

Uh oh!

github-actions bot commented Feb 20, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

codecov-commenter commented Feb 11, 2023 •

edited

Loading