ENH: tolerance argument for limiting pad, backfill and nearest neighbor reindexing
State: closed

xref #9817

This does not entirely solve the floating point precision issues, but gets us part of the way there -- we can explicitly lookup data with a fixed tolerance for nearest neighbor matches.

It is also is useful in its own right, mostly as a simple sanity check to verify that labels are not entirely misaligned.

Example usage:

```
In [2]: df = pd.DataFrame({'x': range(5)})

In [3]: df.reindex([0.1, 1.9, 3.5], method='nearest', max_distance=0.2)
Out[3]:
      x
0.1   0
1.9   2
3.5 NaN
```


Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: API Design

Comments:
`max_distance` -> `precision/tol`? slightly more inline with other routines of this type (e.g. `allclose`)

Hmm. Getting the name / API design right here is a little tricky.

My thought was that `max_distance` makes the most sense in terms of selecting nearest values.

On the other hand, `precision`/`tol` (or `atol`/`abs_tol`?) makes more sense in the context of imprecise matches / floating point issues. When providing a tolerance or precision, it seems implicit that you're doing nearest neighbor lookups, i.e., `precision=0.1` would imply `method='nearest'`.

~~For alignment purposes, we probably want an API that looks similar to [`math.isclose`](https://www.python.org/dev/peps/pep-0485/), which has the signature `isclose(a, b, rel_tol=1e-9, abs_tol=0.0)` and returns the result of `abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)`.~~

Some further thoughts on API design (after some offline discussions):
- It's difficult to conceive of a true need for relative tolerance, because array labels are generally not multi-scale. A fixed absolute tolerance seems like the use case here.
- I'm leaning toward the argument name `tol`/`tolerance`, which makes sense in the context of getting nearest values (at least somewhat) and also for alignment purposes -- we can later add a `tol` parameter to `align` and index set operations.

Here's an unsettled API design question: What should happen when you do `df.reindex(..., tol=1e-3)`?

In particular: should this imply `method='nearest'` if `method` is not provided? This is probably the behavior we'll want for align (e.g., `df1.align(df2, tol=1e-3)`) -- I don't think there's a usecase for one-sided tolerance in alignment.

The alternative (as @jreback suggests) is to just raise an error....

> - A fixed absolute tolerance seems like the use case here.
> - I'm leaning toward the argument name tol/tolerance,

Agreed with both of these.
My only experience here is when I was working with lat/lngs which got misaligned from the regular grid I was expecting. A `tol` argument would have been perfect for me there.

Added some thoughts on possible API for setting a default tolerance on an index in #9817.

@TomAugspurger indeed, that's pretty much the exact case I'm thinking of here :).

Feedback was solicited, so one thought: I generally prefer leaning towards the more-verbose keyword/argument names, unless it is a very, very long word. `tolerance` will be more easily deciphered when reading through someone else's code than `tol`. 

+1 on `tolerance`. If we are going to use it in other functions as well, this seems a better fit in general (although I find `max_distance` is a bit more explicit when it is only about 'nearest' reindexing)

Would this have a default value for FloatIndices? As I think they are only useful when that would be the case (otherwise all operations would become way too much verbose) (edit: @shoyer ah, I see you put some ideas on that in #9817)

@jorisvandenbossche Yeah, I agree that some sort of default tolerance would be nice. The problem is that while it's true that many floating point index operations are only useful with a defined tolerance, how to automatically infer that tolerance is not obvious -- any solution seems likely to involve enough magic that it will break in unexpected ways.

I think we could provide a tolerance as a keyword on the constructor and have a simple way of inferring (if needed) eg just do a couple of sample and diff and see

There is a subtle difference between `tolerance` and `max_distance` is if we generalize nearest neighbor indexing support to MultiIndex (#9365): the former implies an independent precision for each dimension, whereas the later implies a combined maximum distance. This distinction suggests to me that while `tolerance` would make more sense as an innate index property (e.g., as a keyword on the constructor), `max_distance` might make more sense as the keyword argument for `get_indexer`/`reindex`.

I have now renamed the parameter to `tolerance`, per the consensus. I have also made `method='nearest'` the default if a tolerance is supplied. We could also raise an error, but IMO `df.reindex(targets, tolerance=1e-3)` is not ambiguous, and we'll want to make the "nearest" aspect implicit for alignment operations.

I don't think tolerance can be allowed for some inferred dtypes iow

strings and cases where tolerance is not a relevant unit , eg DatetimeInde/TimedeltaIndex/PeriodIndex must be a Timedelta or Offset

I think I have tests for other dtypes -- I'll double check. 

On further consideration, I think I need to remove the default method='nearest' when a tolerance is provided. If I provide tolerance=2, I would expect a reindex/get_loc to match everything within that tolerance, not just the nearest value.

You now get errors if you try to use `limit` or `tolerance` with the default reindexing method.

With the current approach, you get a `ValueError` when you try to use `get_indexer` with an invalid tolerance, but `KeyError` on `DatetimeIndex.get_loc`. The later is because `get_loc` currently uses a rats nest of exception handling to allow for various types of indexers. Adding the proper error for an invalid tolerance there is probably a good idea but I'm not sure it's worth the trouble....

OK, OK -- I added a bunch more error handling for `tolerance`.

@jreback any further comments?

looks pretty good.

not sure if this matters, but something has to be: `(value - test_value) or (test_value - value) <= tolerance` right? I would just make equal clear, that if the distance is equal to the tolerance is INCLUDED.

@jreback OK, I think I responded to all your suggestions:
1. This now works on `PeriodIndex` (was easier than I thought)
2. Added a section on `limit` and `tolerance` to the "Filling while reindexing" docs in basics.rst
3. Added an example of using tolerance with a datetimeindex to what's new
4. Updated docstrings to clarify the formula used for `tolerance`.

This still needs a rebase/squash, but I thought I would get your review before squashing.

lgtm
minor comment
rebase / squash snd merge

OK, did the rebase / squash.

If Travis gives the OK, I'll merge EOD tomorrow.

Travis passed prior to the last docstring fixup, so I decided it was safe to merge.

Thanks everyone for your help on this one!

nice :)