refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class #35073

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 Outdated 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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class #35073

refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class #35073

Uh oh!

kliem commented Feb 11, 2023

Uh oh!

codecov-commenter commented Feb 11, 2023 •

edited

Loading

Uh oh!

Uh oh!

tscrim left a comment

Uh oh!

tscrim Feb 13, 2023

Uh oh!

kliem Feb 13, 2023

Uh oh!

tscrim Feb 13, 2023

Uh oh!

kliem Feb 13, 2023

Uh oh!

This comment was marked as resolved.

Uh oh!

kliem Feb 13, 2023

Uh oh!

This comment was marked as resolved.

Uh oh!

kliem Feb 13, 2023

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!

Uh oh!

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

Uh oh!

refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class #35073

refactor(34773): combinatorial polyhedron: move list of pairs to dedicated class #35073

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!

Uh oh!

codecov-commenter commented Feb 11, 2023 •

edited

Loading