Skip to content

Conversation

dcoudert
Copy link
Contributor

@dcoudert dcoudert commented May 7, 2024

We propose a direct implementation of the graph generator BalancedTree that is faster than the previous method using networkx.

Before (using networkx)

sage: %timeit G = graphs.BalancedTree(3, 5)
550 µs ± 1.17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
5.33 ms ± 37.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 5)
2.13 ms ± 18.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
54.5 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

With this PR

sage: %timeit G = graphs.BalancedTree(3, 5)
157 µs ± 809 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
1.44 ms ± 4.94 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(4, 5)
569 µs ± 6.78 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
9.52 ms ± 61.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

Copy link

github-actions bot commented May 8, 2024

Documentation preview for this PR (built with commit e8f0782; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

All of these changes can be ignored if you prefer as they are either tangential or micro-optimizations. Once changed or ignored, you can set a positive review.

@dcoudert
Copy link
Contributor Author

I have implemented all proposed changes. Thanks.

@tscrim
Copy link
Collaborator

tscrim commented May 10, 2024

Thank you.

vbraun pushed a commit to vbraun/sage that referenced this pull request May 11, 2024
sagemathgh-37956: faster implementation of method `sage.graphs.generators.families.BalancedTree`
    
We propose a direct implementation of the graph generator `BalancedTree`
that is faster than the previous method using networkx.

Before (using networkx)
```
sage: %timeit G = graphs.BalancedTree(3, 5)
550 µs ± 1.17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
5.33 ms ± 37.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 5)
2.13 ms ± 18.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
54.5 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

With this PR
```
sage: %timeit G = graphs.BalancedTree(3, 5)
157 µs ± 809 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
1.44 ms ± 4.94 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops
each)
sage: %timeit G = graphs.BalancedTree(4, 5)
569 µs ± 6.78 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
9.52 ms ± 61.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37956
Reported by: David Coudert
Reviewer(s): David Coudert, Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
sagemathgh-37956: faster implementation of method `sage.graphs.generators.families.BalancedTree`
    
We propose a direct implementation of the graph generator `BalancedTree`
that is faster than the previous method using networkx.

Before (using networkx)
```
sage: %timeit G = graphs.BalancedTree(3, 5)
550 µs ± 1.17 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
5.33 ms ± 37.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 5)
2.13 ms ± 18.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
54.5 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

With this PR
```
sage: %timeit G = graphs.BalancedTree(3, 5)
157 µs ± 809 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit G = graphs.BalancedTree(3, 7)
1.44 ms ± 4.94 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops
each)
sage: %timeit G = graphs.BalancedTree(4, 5)
569 µs ± 6.78 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit G = graphs.BalancedTree(4, 7)
9.52 ms ± 61.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37956
Reported by: David Coudert
Reviewer(s): David Coudert, Travis Scrimshaw
@vbraun vbraun merged commit e72a3e4 into sagemath:develop May 12, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants