API/ENH: add method='nearest' to Index.get_indexer/reindex and method to get_loc
State: closed

Fixes #8845

Currently only an index method; I'm open to ideas for how to expose it more
directly -- maybe `df.loc_nearest`?.

In particular, I think this is usually a more useful way to do indexing for
floats than pandas's reindex based `.loc`, because floats are inherently
imprecise.

CC @jreback @jorisvandenbossche @immerrr @hugadams


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

Comments:
Hmm. I think this has all the functionality we need, but it would also be good to reconcile the API design here with `asof`. I'll dig into that, but I'm also open to any proposals.

- Should it return an array or an Index when given multiple values?
- For `asof`, I think this can completely replace the usage of `asof`, and is also compatible in signature. Only differences are:
  - `asof` would have a default of `left` in terms of `get_nearest`
  - it returns NaN if it cannot find anything. 
  
  I think we can leave `asof` as is, but add above remarks to the docs. Referring in the docstring of `asof` to `get_nearest` and indicating how you can replace it.

I agree with @jorisvandenbossche this should just replace asof entirely
asod was essentially a simple version of this

I think you should extract the indexer into another method maybe asof_indexer (and asof just calls that)
then we can support 'asof' joins! (I think there is an outstanding issue for this)

> Should it return an array or an Index when given multiple values?

I'm returning an array, based on how `get_indexer` works.

I'm currently modeling this function as a sort of combination of `get_loc` and `get_indexer`. Perhaps it would indeed make more sense to separate this into two interfaces -- `get_loc_nearest` (could handle duplicate indexes) and `get_indexer_nearest`.

@shoyer yes this should be 2 methods `get_indexer_nearest` which is called by `get_loc_nearest` (whose impl is trivial), but this exposes the indexer which is important.

my 2c, is that we already have `asof` so this should be just an impl, e.g. `get_loc_asof/get_indexer_asof`. No reason to have both

OK, latest commits include the split to 2 methods and handle missing values properly (that was not being done right before). The differences are:
1. `get_loc_nearest` will coerce input to the appropriate Timedelta/Timestamp/Period scalar, like `get_loc`
2. `get_indexer_nearest` uses -1 to mark missing values that cannot be found whereas `get_loc_nearest` raises `KeyError`

I was able to make `Index.asof` be a thin wrapper around `get_loc_nearest`. So it should be able to handle non-datetimes now (for whatever that's worth).

The other use of asof is in the method `Series.asof` and the undocumented method `Index.asof_locs` (which appears to only be used or tested by `Series.asof`). This method is a little different and somewhat strange IMO -- it skips missing values in the Series. For now I've left it alone because the skipping of missing values makes it somewhat different, but is could definitely also use a cleanup.

Where do you find the time man!

One more design question: How should we handle partial string matching for `DatetimeIndex.get_loc_nearest`?

The current design casts the input to a Timestamp and finds the nearest label. This seems reasonable, but it's not consistent with `get_loc`, which will return all matching labels (even a slice, if possible). Arguably, `get_loc_nearest` should be equivalent to calling `get_loc` and then falling back to nearest lookup if the key is not found.

Here's an concrete example:

``` python
idx = pd.to_datetime(['2000-01-31', '2000-02-28'])
print idx.get_loc_nearest('2000-02', side='left')
print idx.get_loc_nearest('2000-02', side='nearest')
```

With the current implementation, each of these would print 0. This is consistent with the current behavior of `asof` (as verified by `test_asof_datetime_partial` in `test_index.py`), but not `get_loc`, which would print 1 for each of these.

OK, it looks like I need to make my own API decision :).

I've settled on using the result of `get_loc` for the result of `DatetimeIndex.get_loc_nearest`, if possible. This means that the "nearest" value to a partial string index like `'2000-01'` will be any values in January 2001, not the nearest value to `2000-01-01T00:00:00`.

This is also a small breaking API change for `DatetimeIndex.asof`. I've added documentation to that effect to what's new in the latest commit (along with more functionality/tests).

Any other comments? I think this is possibly ready to merge (once rebased).

Would it be much trouble to not have this API change in `asof`? (possibly just leaving it as it is if it causes too much problems)

A question: when you have a partial string, what is the 'nearest' value, so what will `DatetimeIndex.get_loc_nearest` return? (say if you have all days of the month in your index, what day is 'nearest' to the month)?

@jorisvandenbossche We definitely could include a work around to avoid the change for `asof` by overwriting the subclass `DatetimeIndex.asof` method.... but I'm not even entirely sure this should really be considered an API change rather than a bug fix (even though there _was_ a test for it).

Note the `asof` docstring: "For a sorted index, return the most recent label up to and including the passed label." A string like '2000-02' arguably does include the timestamp '2000-02-28'.

Looking into the history a little more: this test appeared in PR #8246 by @TomAugspurger. There, it appears that the issue was something else entirely -- `asof` was returning time stamps not in the index at all (see #8245). It's not clear to me that anyone carefully considered exactly _how_ partial datetime strings should be interpreted in this change.

@jorisvandenbossche The "nearest" value from `idx.get_loc_nearest('2000-01')` will be a slice object indexing all values in January 2001 if `idx.get_loc('2000-01')` is valid; otherwise, it will return the location of the nearest value to `2000-01-01T00:00:00`. I suppose it would be a good idea to document this more directly!

I haven't really looked at this in depth - but

the string slicing should be analogous to partial string indexing with the same semantics

at first glance it appears that they are the same?

@jreback Yes, the nearest partial string indexing of a DatetimeIndex is exactly equivalent to partial partial string indexing if there is a match; otherwise, it casts the string label to a Timestamp and finds the nearest value.

@shoyer on `asof`, OK then, given this is rather new behaviour as you pointed out, so lets regard that as a bug fix (maybe also specify it like that in the whatsnew docs)

Some other things:
- On the partial string indexing. The docstring of `get_loc_nearest` says it returns an int -> so this is not always correct then.
- For a DatetimeIndex, you only implemented `get_loc_nearest` and not `get_indexer_nearest`. Is this on purpose? If you now try using `get_indexer_nearest` with a string, you get rather unhelpful error messages.

I know you modelled the functions to the existing `get_loc` and `get_indexer`, but supposing these wouldn't exist, I would have the following remarks:
- Why have both? Why not just one function that accepts label or array of labels? (and returns int or array of ints)
- I find the name a bit confusing. `get_loc_nearest` returns the 'integer location by position'. But in the 'indexing terminology', `loc` is for the 'label-location' based indexer.
- The return of `-1` if a key is not found, seems a bit strange for me. As you would typically use the result to index your frame/series. But -1 has in that case a specific meaning, namely the last value. And that is not always what you want I think. (I know this is not that simple, as you cannot have NaN in integer, and you cannot have non-integer in the indexer, ..)

@jorisvandenbossche 

I think this impl is fine. The signal of -1 is typical in the way the indexers work. These are by definition `int64` and -1 is a not-found value. It is up to the user to process these.

By definition these are always indexers, by position, always, full-stop. These only have a single semantic for the output results. `loc` here is not location based, but just location (its an older nomenclature and I can see it being somewhat confusing, but its how all of the Index classes work.)

@shoyer I would think this API simpler if you do this;

```
def get_indexer(self, target, method=None, limit=None):   
        """
        Compute indexer and mask for new index given the current index. The
        indexer should be then used as an input to ndarray.take to align the
        current data to the new index. The mask determines whether labels are
        found or not in the current index

        Parameters
        ----------
        target : Index
        method : {'pad', 'ffill', 'backfill', 'bfill'}
            pad / ffill: propagate LAST valid observation forward to next valid
            backfill / bfill: use NEXT valid observation to fill gap
```

and allow `method='nearest'` (and allow the `side` parameter to be passed as well).
(similarly for `get_loc`). 

I think its just think its adding API noise otherwise. These conceptually do exactly the same thing. (you certainly could have an internal `_get_indexer_nearest` if that makes the impl clearer though).

@jreback This is a good point about incorporating this into the `get_indexer` method. In fact, I realize now that `get_indexer_nearest(side='left')` is actually just a slower version of `get_indexer(method='pad')`. So it looks like adding `method='nearest'` is probably the way to go here.

It appears that the existing `get_indexer` method only works for monotonic ascending indexes and keys. So I'll probably keep around some of this code as a fallback option for `pad`/`backfill` with decreasing indexes and/or unordered keys.

@jorisvandenbossche I agree, the current index API is a little strange -- some refactoring to provide a unified API and to untangle `core.indexers` would definitely be in order. See also: #7651.

I'm implementing only the low level methods now, but eventually we should figure out a higher level API for nearest neighbor lookups in pandas.

OK, I did a big refactor here and moved everything around to match @jreback's suggested organization (I also did a rebase since the old changes are almost all moved). This yielded the nice benefit of supporting non-monotonic targets for pad/backfill with get_indexer, so I put that down as an enhancement (not sure if pandas currently uses that directly or not; probably not).

I was disappointed by the lack of direct test coverage I encountered for the existing `get_loc` and `get_indexer` methods. I added some in but assuredly we could do more. In particular, the index methods currently allows integer values ( in nanoseconds) to pass through as valid values for the time/delta/period indexes. I know most of that is currently checked by `core.indexers` when used with `.loc`, etc., but that is poor separation of concerns -- that logic should all be on the index.

@shoyer looks much better. consolidates the functionaility pretty nicely. Just some minor comments.

It looks like we can very easily expose this directly through `DataFrame.reindex` with `method='nearest'` (most of the current test failures are because `reindex` with `method='pad' no longer fails for non-monotonic targets). We may eventually want some sort of "nearest neighbor" indexer, but`reindex` is a useable API, so I will see if I can get that working at least.

as a side issue

a time like join is essentially nearest_left (eg nearest but only looking left)
so maybe want to add nearest_left/nearest_right 
the can easily do : http://stackoverflow.com/questions/12322289/kdb-like-asof-join-for-timeseries-data-in-pandas

@jreback  OK, I think I address most of your suggestions in my latest patchset. I'm also presenting the public API using `reindex` instead of the low-level `get_indexer`.

We should also add this to the [docs section on reindexing](http://pandas-docs.github.io/pandas-docs-travis/basics.html#filling-while-reindexing), at least once fillna with `method='nearest'` also works (made a new issue for that, #9471)

yeh I would update the docs once #9471 is addressed.

Other thoughts for this issue? `fillna` will come in another PR.

minor comments, lgtm otherwise.

docstring of reindex should still be updated