carsonfarmer / fastpair Goto Github PK

This error/bug happens when there's less pairs than the min_points parameters and we have custom dist function.

(cp_diff, cp_pair) = fp.closest_pair()
      File "/nix/store/65djwzlc0r0w59i5snby2dmfkbpjqm1h-python3.6-fastpair-2016-07-05/lib/python3.6/site-packages/fastpair/base.py", line 178, in closest_pair
        return self.closest_pair_brute_force()
      File "/nix/store/65djwzlc0r0w59i5snby2dmfkbpjqm1h-python3.6-fastpair-2016-07-05/lib/python3.6/site-packages/fastpair/base.py", line 190, in closest_pair_brute_force
        return _closest_pair_brute_force(self.points)
      File "/nix/store/65djwzlc0r0w59i5snby2dmfkbpjqm1h-python3.6-fastpair-2016-07-05/lib/python3.6/site-packages/fastpair/base.py", line 282, in _closest_pair_brute_force
        return min((dst(p1, p2), (p1, p2)) for p1, p2 in combinations(pts, r=2))
      File "/nix/store/65djwzlc0r0w59i5snby2dmfkbpjqm1h-python3.6-fastpair-2016-07-05/lib/python3.6/site-packages/fastpair/base.py", line 282, in <genexpr>
        return min((dst(p1, p2), (p1, p2)) for p1, p2 in combinations(pts, r=2))
      File "/nix/store/qw3cm7qzzvi68cl9ffz06l2xia52v07s-python3.6-scipy-1.0.0/lib/python3.6/site-packages/scipy/spatial/distance.py", line 553, in euclidean
        return minkowski(u, v, p=2, w=w)
      File "/nix/store/qw3cm7qzzvi68cl9ffz06l2xia52v07s-python3.6-scipy-1.0.0/lib/python3.6/site-packages/scipy/spatial/distance.py", line 470, in minkowski
        u_v = u - v
    TypeError: ufunc 'subtract' did not contain a loop with signature matching types dtype('S648') dtype('S648') dtype('S648')

@carsonfarmer I think you may have to "turn on" codecov for the report from CI, (see failed report upload here). You should be able to access via [https://app.codecov.io/gh/carsonfarmer/fastpair/new] and follow the instructions for adding a CODECOV_TOKEN repository secret. This is low on the list of criticalities, so no rush at all (but also does only take 5 seconds).

xref #20

While working on (3.) in #20, I am running into the problem of there being no associated dynamic version with the fastpair==0.1.0 tag, which is causing the pip install -e . to fail.

The two options (IMHO) are a conservative approach [1,2] or a more aggressive approach [2] that does it all at once.

1. conservative approach (2 PRs):
   1. explicitly declaring version = "v0.1.0" in pyproject.toml in a first PR addressing (3.)
   2. (perhaps create a v0.1.1 tag and associated release, but this might be overkill)
   3. proceed to step 2
2. one stroke (1 PR):
   1. delete the fastpair==0.1.0 tag (remote & local)
   2. declare dynamic = ["version"] in pyproject.toml

@carsonfarmer Let me know if (A) you have any questions/concerns here; and (B) which approach you'd like me to take.

Add a codecov.yml for customized reporting on coverage checks in Pull Request.

xref:

• #26
• #27

example: spopt/codecov.yml

Currently with FastPair.__add__() only a single point can be added at time after calling build():

def __add__(self, p):
    self.points.append(p)
    if self.initialized:
        self._find_neighbor(p)
    elif len(self) >= self.min_points:
        self.build()
    return self

With some modification, a collection of points could be added to the data structure:

def __add__(self, p):
    if isinstance(p, list):
        for _p in p:
            self._add_1_point(_p)
    else:
        self._add_1_point(p)
    return self

def _add_1_point(self, p):
    self.points.append(p)
    if self.initialized:
        self._find_neighbor(p)
    elif len(self) >= self.min_points:
        self.build()
    return self

Seems like the same could go for FastPair.__sub__()

Thoughts?

cc @gegen07

Yes pointpats offers this, as well as a new geopandas that wraps pointpats (Levi & Martin put a ton of work into that). I think these are great option for an advanced use case demo, but the dependencies would really explode if they were to be used in tests.

• to consider:
  • +1 for more robust
  • -1 for dependency bloat

xref: #40 (comment)

• test_all_closest_pairs mentions a closest_pair_divide_conquer() method.
• noted here for future investigation

• Add a advanced_usage demo w/ high-dimensional points.
• Do this in conjunction with #41.
• Once @carsonfarmer is satisfied with with both notebooks, clean up the README.md:
  • #35
  • add links to notebooks

xref #20

• start supplemental testing schema
  • rename (and keep for now) test_fastpair.py --> test_fastpair_pre_010.py
  • initialize test_fastpair.py for breaking out updated and fleshed out tests
• review current testing helper
  • add type hinting
  • DRY for robustness
• add more as we think of it

@carsonfarmer Do you have any interest in seeing fastpairs modernized (e.g., Python 312 compatibility, pyproject.toml, GHA for testing, structured formatting & linting, etc.)? If so (and as time permits), I can start making specific tickets and chipping away at it.

xref: #12

We should move the info at top of base.py into the FastPair docstring.

Instead of merging, removing single points results in the wrong solution. The test image looks like this:

When I merge with this method:

fp = FastPair()
fp.build(points)

for i in range(int(len(fp) * 0.8)): # remove 80 percent of points
    dist, (a, b) = fp.closest_pair()

    c = (a[0]/2+b[0]/2, a[1]/2+b[1]/2)
    fp -= b
    fp -= a
    fp += c
    
for p in fp:
    plt.plot(p[0], p[1], "b.")

I get this result:

But if I remove a point from the closest pairs iteratively like this:

fp = FastPair()
fp.build(points)

for i in range(int(len(fp) * 0.8)):  # remove 80 percent of points
    dist, (a, b) = fp.closest_pair()
    fp -= a

for p in fp:
    plt.plot(p[0], p[1], "b.")

I get this output:

Do you have any ideas why this is happening? Input image and ipynb can be found here:
fastpair_test.zip

add type hints

• xref:
  • #20
  • #50

Within test_update_point_less_points(), I am not sure this final assert is testing what it's supposed to and I am concerned about it currently passing.

• ✅ pytest passes in remote CI
• ✅ pytest passes locally in serial run (1 core)
• ❌ pytest fails locally in xdist run (multicore)
• ❌ the code chunk broken out and run in jupyterlab

From what I understand, the final assert statement should be testing number of point currently in fp, and that should not be 1 because we are only adding points to fp and then updating a single point, never removing any points, where:

• point_set create 50 points; and
• rand_tuple create 1 point

So I think the final line here should pass with assert len(fp) == 9, but it somehow passes with assert len(fp) == 1 in the ✅ above...

def test_update_point_less_points(self, point_set):
    ps = point_set
    fp = FastPair()
    for p in ps[:9]:
        fp += p
    assert fp.initialized is False
    old = ps[0]  # Just grab the first point...
    new = rand_tuple(len(ps[0]))
    fp._update_point(old, new)
    assert len(fp) == 1

cc @gegen07

Edit 1

I have seen failure in local serial testing, but it is not consistent.

FAILED fastpair/tests/test_fastpair.py::TestFastPairUpdatePointLessPoints::test_basic - assert 9 == 1

swap out math& random for numpy in tests

I noticed that point removal is O(n) as it uses list remove function. Instead one can switch to using sets, which would make it close to O(1) for removal. All other operations don't really change by switching to sets as far as I can see.

• Add explicit testing against both intel & apple silicon for macOS CI.
• #72

add matplotlib to dependencies

xref #35

Latest pytest fails on this repository.

Complains:

Fixture "PointSet" called directly. Fixtures are not meant to be called directly,
but are created automatically when test functions request them as parameters.
See https://docs.pytest.org/en/latest/fixture.html for more information about fixtures, and
https://docs.pytest.org/en/latest/deprecations.html#calling-fixtures-directly about how to update your code.

Fixture code should be updated.

• add config to pyproject.toml
  • example
• add config to .pre-commit-config.yaml
  • example
• either add: not needed since pre-commit is enabled
  • a stand-alone action - as in momepy - or
  • adapt testing.yml to run mypy only on ubuntu-latest
• xref:
  • #55
  • #20

• failing doctests due to the new formatting in numpy -- only run doctests on one CI environment
• add pytest-doctestplus plugin for option to run only doctests through pytest

We'll remove test_fastpair_pre_v010.py when ready. Either after next:

1. minor release -- v0.2.0; or
2. major release -- v1.0.0

Any preference @carsonfarmer?

cc @gegen07

On another note I am thinking that boiling the basic_usage demo even further by having hard-coded points would be an even better intro. Probably move the the random_points function to another demo when that happens. Leave as it for this PR.

• boil down basic_usage.ipynb further - hard code points
• move random_points() to an advanced notebook (high-dimensional points)

xref - #40 (comment)

Is this ready to be on PyPi now?

The conga line structure must have min_points to be initialized from the FastPair class. However, when an instance is created via FastPair.build() there is no assumption any min_points.

Should we perhaps throw a warning if min_points are not yet met when calling .build()?

Also, here in test_iter().

Currently fastpairs is not compatible with scipy>=1.12 – here

fastpair/test/test_fastpair.py:23: in <module>
    from scipy import mean, array, unique
ImportError: cannot import name 'mean' from 'scipy'

xref #20

Currently, this section of setup.py causes an install error due to non-conforming versioning (pypa/setuptools#3772). Simply removing for now resolves this problem.

   raise InvalidVersion(f"Invalid version: '{version}'")
      setuptools.extern.packaging.version.InvalidVersion: Invalid version: '0.1.0.dev-d3170fd'

xref #20

@carsonfarmer How do you think about having the Features section of the README moved from there into a notebook? If that sounds like a good idea, would we want that directory to be named:

• notebooks/
• examples/
• demos/
• something else?

xref #20, #35

• failing Python 310 in #72
• Solution here on SO.
• Once fixed in #72, create a fresh ticket as a reminder to remove once Python 3.11 in minimum.
• xref #55

update random number generator in tests to use modern numpy.random.default_rng() instead of the legacy generator -- here

ideas for more notebooks – edit for any idea further idea

• same point set with varied distance metrics
• same point set with varied min_points
• direct time comparison with closest_pair vs. closest_pair_brute_force
• demo with empirical data, probably from geodatasets

cc @gegen07

Does dist (scipy.spatial.distance) actually need to be listed in all? I think we can remove, but wanted to see if I'm missing something.

I curious about the possibility of utilizing the fastpair data structure for querying nearest neighbors in disjoint sets à la cross $k$-nearest, for example. Would that even be possible with fastpair?

@carsonfarmer Do you have any strong feelings for keeping shorthand imports within fastpair? I will defer to your preference if you'd like to keep them. My general preference is explicit importing of names where possible (I think the improved readability vastly makes up for the several saved characters of shorthand imports.

cc @gegen07

• Came across this while working on #55
• Do does there actually need to be return statements in _find_neighbor()¹ and _update_point()²? The values are being set to the data structure itself, and there appears to be nothing being return in the current functional codebase.
• The unknown here is the currently commented out merge_closest()³ method that may in fact need to return a value
• xref:
  • #34

cc @gegen07

Noticed several typos in README following #46 -- review to find and correct

beef up docstrings

tasks:

• review language for clarity, etc.
• conform to numpydoc standards
• clean up & flesh out Examples
• start performing doctests during CI

xref:

• #20
• #55

• add a descriptive __repr__() to FastPair
• xref:
  • #20
  • #55
  • #56

update README by section

• Overview
• Installation
• Testing
• Features -- move to a notebook?
• License -- anything here?

Add PyPI & conda-forge badges to the Installation section of the README.md (once available).

I am curious about the history & commenting out of the merge_closest() method. A quick search didn't lead to any previous issues or PRs (though I likely overlooked something). Is there anything you can point me to for that, @carsonfarmer?

@carsonfarmer before works start on modernization, would it be possible to rename branches: master for main for more inclusive language, as we have done over in the PySAL ecosystem -- pysal/pysal#1285?