Add NodeIndices return type #198
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This commit adds a new return type NodeIndices that is used as the return type for functions that return Vec<usize> when its used as the return type to return a list of node indices. This custom type implements the Python sequence protocol and can be used as the list which was previously returned except for where explicit type checking was used. Just as in Qiskit#185 the advantage here is that for large lists of node indices the type conversion from a Vec<usize> to list(int) becomes a large bottleneck. This avoids that conversion and only does a usize to python int conversion on access. Related to Qiskit#71
9 tasks
Pull Request Test Coverage Report for Build 372748559
💛 - Coveralls |
mtreinish
added a commit
to mtreinish/qiskit-core
that referenced
this pull request
Nov 18, 2020
In Qiskit#5117 the noise adaptive layout pass was updated to use retworkx internally for performance. In that PR there were a couple of TODO comments added about using neighbors methods when they were released. The retworkx 0.6.0 release was pushed last week so we can update the usage and remove the TODO comments. The neighbors methods should have lower overhead since it only returns a list of node indices instead of a dictionary of (node index, edge weight). This will also get significantly faster (for large neighbors lists) with Qiskit/rustworkx#198.
lcapelluto
approved these changes
Nov 19, 2020
| /// | ||
| /// :raises Exception: If an unexpected error occurs or a path can't be found | ||
| /// :raises DAGHasCycle: If the input PyDiGraph has a cycle | ||
| #[pyfunction] | ||
| #[text_signature = "(graph, /)"] | ||
| fn dag_longest_path(graph: &digraph::PyDiGraph) -> PyResult<Vec<usize>> { | ||
| longest_path(graph) |
There was a problem hiding this comment.
It looks like longest_path still returns PyResult<Vec<usize>>. Should that not be updated to NodeIndices?
There was a problem hiding this comment.
It's easier to leave it returning Vec<usize> because dag_longest_path_length calls it too. I actually did that in the first rev before pushing this and it errored because there is no len() on NodeIndices it felt easier to leave it like this and have dag_longest_path just move the result into the NodeIndices struct as the return and leave it as a Vec<usize> for the other method
Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com>
mtreinish
added a commit
to mtreinish/retworkx
that referenced
this pull request
Nov 19, 2020
This commit adds 2 new return types EdgeList and WeightedEdgeList that are used as the return type for functions that return Vec<(usize, usize)> and Vec<(usize, usize, PyObject)> respectively. This custom type implements the Python sequence protocol and can be used as the list which was previously returned except for where explicit type checking was used. Just as in Qiskit#185 and Qiskit#198 the advantage here is that for large edge lists the conversion from Rust to a Python type becomes a large bottleneck. This avoids that conversion and only does it per element on access.
|
I ran some benchmarks on this from https://github.com/mtreinish/retworkx-bench before merging and forgot to paste here. The numbers for the hosted bencharks are running now and when they finish it'll be updated on https://mtreinish.github.io/retworkx-bench/ but for now this is what it shows: |
mtreinish
added a commit
that referenced
this pull request
Dec 2, 2020
* Add EdgeList and WeightedEdgeList return types This commit adds 2 new return types EdgeList and WeightedEdgeList that are used as the return type for functions that return Vec<(usize, usize)> and Vec<(usize, usize, PyObject)> respectively. This custom type implements the Python sequence protocol and can be used as the list which was previously returned except for where explicit type checking was used. Just as in #185 and #198 the advantage here is that for large edge lists the conversion from Rust to a Python type becomes a large bottleneck. This avoids that conversion and only does it per element on access. * Add new return types to docs * Apply suggestions from code review Co-authored-by: Lauren Capelluto <laurencapelluto@gmail.com> * Fix docstring mistakes * Update in_edges and out_edges to use WeightedEdgeList
mergify bot
added a commit
to Qiskit/qiskit
that referenced
this pull request
Dec 9, 2020
In #5117 the noise adaptive layout pass was updated to use retworkx internally for performance. In that PR there were a couple of TODO comments added about using neighbors methods when they were released. The retworkx 0.6.0 release was pushed last week so we can update the usage and remove the TODO comments. The neighbors methods should have lower overhead since it only returns a list of node indices instead of a dictionary of (node index, edge weight). This will also get significantly faster (for large neighbors lists) with Qiskit/rustworkx#198. Co-authored-by: Kevin Krsulich <kevin.krsulich@ibm.com> Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This commit adds a new return type NodeIndices that is used as the
return type for functions that return Vec when its used as the
return type to return a list of node indices. This custom type implements
the Python sequence protocol and can be used as the list which was
previously returned except for where explicit type checking was used.
Just as in #185 the advantage here is that for large lists of node
indices the type conversion from a Vec to list(int) becomes a
large bottleneck. This avoids that conversion and only does a usize to
python int conversion on access.
Related to #71