Repository navigation
perf: closest() and near() use a matrix of coordinates, not a loop - #81
Open
petercorke wants to merge 1 commit into
Open
petercorke wants to merge 1 commit into
petercorke wants to merge 1 commit into
Conversation
Without a k-d tree both measured the metric of every vertex in a Python loop, and any add_vertex discarded the tree, so a planner that interleaves add_vertex with closest (RTB's LatticePlanner, RRTPlanner) always paid for the loop. The graph now keeps the coordinates of its embedded vertices as a matrix, built on first use and appended to by add_vertex, and applies the built-in metrics to all rows at once. Removing a vertex or assigning a coord drops it. A metric of your own is still applied to each vertex in turn. It is not pickled or copied, and has its own staleness flag. closest at N=1,000: 726 us -> 12 us. Lattice plan of 1,292 vertices: 1.07 s -> 0.06 s. Vertices, edges and paths of the RTB planners are unchanged. A coordinate changed in place (v.coord[0] = x) is not seen, as with build_kdtree(); documented. Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com>
Up to standards ✅🟢 Issues
|
| Metric | Results |
|---|---|
| Complexity | 42 |
| Duplication | 0 |
NEW Get contextual insights on your PRs based on Codacy's metrics, along with PR and Jira context, without leaving GitHub. Enable AI reviewer
TIP This summary will be updated as you push new changes.
Codecov Report✅ All modified and coverable lines are covered by tests. Additional details and impacted files@@ Coverage Diff @@
## main #81 +/- ##
==========================================
+ Coverage 97.54% 97.62% +0.08%
==========================================
Files 4 4
Lines 1586 1645 +59
==========================================
+ Hits 1547 1606 +59
Misses 39 39 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
This branch has not been deployed
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
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.
Refs #74.
What
closest()andnear()measured the metric of every vertex in a Python loop unlessbuild_kdtree()had been called, and anyadd_vertexdiscards a tree, so a planner that interleavesadd_vertexwithclosest(RTB'sLatticePlanner,RRTPlanner) always paid for the loop.The graph now keeps the coordinates of its embedded vertices as a matrix (
_PointCache): built on first use, appended to byadd_vertex, and the built-in metrics (L1, L2, SE2) are applied to all rows at once via the existing_metric_columns. A metric of your own is still applied to each vertex in turn. It is not pickled or copied and has its own staleness flag (not_spatialchange).Measured
mainclosest, N=1,000 (examples/benchmark.py)add_vertexLatticePlanner.plan, 1,292 verticesRRTPlanner.plan, 300 nodesVertices, edges and paths of the RTB RRT, PRM and Lattice planners are identical to
main(digest of every coordinate and edge). RTBtests/test_mobile.pyand MVTBtests/test_bundleadjust.pypass against this branch;make -C docs htmlbuilds.Behaviour to know about
v.coord[0] = x) is not seen byclosest/near, as withbuild_kdtree(). Assigningv.coord = x(or+=) is seen. Documented in theclosestdocstring; there is a test pinning it.v.coordon a vertex already in the graph drops the matrix, and the next query rebuilds it in O(n). That is still about 6x faster than the old loop (0.21 ms against 1.34 ms at n=2,000, measured), but the constructor formadd_vertex(coord=x)keeps the matrix and is ~15x faster again. Not changed here: nothing in RTB or MVTB assignscoordafter adding.Tests
tests/test_point_cache.py(17 tests, expectations from a hand-written oracle): interleaved add/query across a buffer growth, L1/L2/SE2, ties, vertices without coordinates, removal,coordassignment, the in-place limit, non-finite and odd-shaped coordinates, user metric,near, pickle/copy/subgraph. 788 tests pass,mypy srcis clean, and the changed lines are covered.🤖 Generated with Claude Code