search

pysal / libpysal

Core components of Python Spatial Analysis Library
http://pysal.org/libpysal
Other
249 stars 79 forks source link

PERF: don't build coincident lookup if not needed #710

Closed martinfleis closed 1 month ago

martinfleis commented 1 month ago

I was building some triangulation graphs on a fairly large data (150k points) and it took 25 minutes. I figured that vast majority of time was consumed by the handing of coincident points, even though there were no coincident points in the whole dataset. With this PR, the same Gabriel graph took 7s.

See the timings on a repr:

coords = np.random.rand(10000, 2)

g = Graph.build_triangulation(coords, kernel="identity")
# main: 10 s ± 58.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# this PR: 193 ms ± 1.81 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

The tests on this will fail until #709 is merged.

codecov[bot] commented 1 month ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 84.9%. Comparing base (bcabdbc) to head (1cb2e88). Report is 13 commits behind head on main.

Additional details and impacted files [![Impacted file tree graph](https://app.codecov.io/gh/pysal/libpysal/pull/710/graphs/tree.svg?width=650&height=150&src=pr&token=wgnkG5Rj0J&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal)](https://app.codecov.io/gh/pysal/libpysal/pull/710?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) ```diff @@ Coverage Diff @@ ## main #710 +/- ## ======================================= - Coverage 85.0% 84.9% -0.1% ======================================= Files 141 141 Lines 15203 15233 +30 ======================================= + Hits 12924 12931 +7 - Misses 2279 2302 +23 ``` | [Files](https://app.codecov.io/gh/pysal/libpysal/pull/710?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal) | Coverage Δ | | |---|---|---| | [libpysal/graph/\_kernel.py](https://app.codecov.io/gh/pysal/libpysal/pull/710?src=pr&el=tree&filepath=libpysal%2Fgraph%2F_kernel.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvZ3JhcGgvX2tlcm5lbC5weQ==) | `82.2% <100.0%> (+0.1%)` | :arrow_up: | | [libpysal/graph/\_triangulation.py](https://app.codecov.io/gh/pysal/libpysal/pull/710?src=pr&el=tree&filepath=libpysal%2Fgraph%2F_triangulation.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvZ3JhcGgvX3RyaWFuZ3VsYXRpb24ucHk=) | `98.0% <100.0%> (+0.1%)` | :arrow_up: | | [libpysal/graph/\_utils.py](https://app.codecov.io/gh/pysal/libpysal/pull/710?src=pr&el=tree&filepath=libpysal%2Fgraph%2F_utils.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal#diff-bGlicHlzYWwvZ3JhcGgvX3V0aWxzLnB5) | `94.9% <100.0%> (-<0.1%)` | :arrow_down: | ... and [2 files with indirect coverage changes](https://app.codecov.io/gh/pysal/libpysal/pull/710/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=pysal)