ENH: add pd.asof_merge
closes #1870
xref #2941 

[Here](http://nbviewer.jupyter.org/gist/jreback/5f089d308750c89b2a7d7446b790c056) is a notebook of example usage and timings

@sinhrks @jorisvandenbossche @wesm 

API question. now we have `pd.merge` (already existing), `pd.ordered_merge` (already existing) and `pd.asof_merge`. Makes sense to keep them separate as the take somewhat different args, but this IS adding to the namespace a bit.
 ## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/13358?src=pr) is **84.32%**

> Merging [#13358](https://codecov.io/gh/pydata/pandas/pull/13358?src=pr) into [master](https://codecov.io/gh/pydata/pandas/branch/master?src=pr) will increase coverage by **0.03%**

``` diff
@@             master     #13358   diff @@
==========================================
  Files           138        138          
  Lines         50929      51058   +129   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          42926      43055   +129   
  Misses         8003       8003          
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last updated by [9670b31...4592fa2](https://codecov.io/gh/pydata/pandas/compare/9670b3139171b3b628cecb87a3d0b46cc0361eba...4592fa21e56e5bc4c3ea52a515604499e9c3ab15)
 I think adding to the name space (with in reason) is better than shoe horning partially overlapping APIs together.   Having args/kwargs which are not used / disallowed / have different meaning based on the value of other input should be avoided.
 @jreback Just a general comment: for me (as a not financial guy :-)), the current explanation of the method (and also the examples) is not really clarifying on what it exactly does .. (at a first read, without looking at the code, which a user should not have to do). So we will have to do a better job explaining it I think.

Some things I was thinking:
- 'asof' is not a well-known term I think, so we need to explain it here as well (you should not have to look at the `.asof()` docstring to know what it means.
- maybe a more dummy example would also help? (the current example is rather detailed (milliseconds, ..), making it more difficult to grasp in an glance what it does) But can certainly keep the current example as an actual practical example!

Will take a more detailed look myself later.
 @jreback I think this needs to be a new API. I think adding `asof_merge` to the pandas NS is fine. see also http://code.kx.com/wiki/Reference/aj
 Ok taking @chrisaycock suggestion, changed `strict` -> `allow_exact_matches`, much more clear.

Here's the new signature.

```
Signature: pd.asof_merge(left, right, on=None, left_on=None, right_on=None, by=None, suffixes=('_x', '_y'), tolerance=None, allow_exact_matches=True)
Docstring:
Perform an asof merge. This by definition will fill the right data with
the asof the left data. The data must be ordered according to the 'on'
(typically time). Optionally perform group-wise merge.

Asof means return the last good (non-NaN) value in object for the date in
question. This is conceptually very close to a left-outer join with
forward filling.

.. versionadded 0.18.2

Parameters
----------
left: DataFrame
right: DataFrame
    Data will be de-duplicated on the [by, on] combination if needed.
on: label or list
    Field names to join on. Must be found in both DataFrames.
    The data MUST be ordered. Furthermore this must be a datetimelike or
    integer-index.
left_on: label or list, or array-like
    Field names to join on in left DataFrame. Can be a vector or list of
    vectors of the length of the DataFrame to use a particular vector as
    the join key instead of columns
right_on: label or list, or array-like
    Field names to join on in right DataFrame or vector/list of vectors per
    left_on docs
by: column name or list of column names
    Group both the left and right DataFrames by the group columns; perform
    the merge operation on these pieces and recombine.
suffixes: 2-length sequence (tuple, list, ...)
    Suffix to apply to overlapping column names in the left and right
    side, respectively
tolerance: integer or Timedelta, optional, default None
    select asof tolerance within this range, must be compatible
    to the merge index.
allow_exact_matches: boolean, default True
    If True, allow matching the same 'on' value (e.g. same time)
    If False, don't match the same 'on' value
        (e.g. don't match the same time)

Returns
-------
merged : DataFrame
```
 any other comments?
 What about this for the help statement?

```
Perform an asof merge. This is similar to a left-join except that we match on
nearest key rather than equal keys.

For each row in the left DataFrame, we select the last row in the right DataFrame
whose 'on' key is less than the left's key. Both DataFrames must be sorted by the
key.

Optionally perform group-wise merge. This matches the 'by' key equally, in
addition to the nearest match on the 'on' key.


Parameters
----------
left: DataFrame
right: DataFrame
    Data will be de-duplicated on the [by, on] combination if needed.
on: label or list
    Field names to join on. Must be found in both DataFrames.
    The data MUST be ordered. Furthermore this must be a datetimelike or
    integer-index.
left_on: label or list, or array-like
    Field names to join on in left DataFrame. Can be a vector or list of
    vectors of the length of the DataFrame to use a particular vector as
    the join key instead of columns
right_on: label or list, or array-like
    Field names to join on in right DataFrame or vector/list of vectors per
    left_on docs
by: column name or list of column names
    Group both the left and right DataFrames by the group columns; perform
    the merge operation on these pieces and recombine.
suffixes: 2-length sequence (tuple, list, ...)
    Suffix to apply to overlapping column names in the left and right
    side, respectively
tolerance: integer or Timedelta, optional, default None
    select asof tolerance within this range; must be compatible
    to the merge index.
allow_exact_matches: boolean, default True
    If True, allow matching the same 'on' value (i.e. less-than-or-equal-to)
    If False, don't match the same 'on' value
        (i.e., stricly less-than)
```
 updated according to @chrisaycock doc-string
 To @jorisvandenbossche's point, how about adding a smaller context-free example that makes it a little easier to see exactly what's going on.  Something like this: (edit: changed `'right_val`' to numbers so it's easier to match up the rows)

``` python
a = pd.DataFrame({'a':[1, 5, 10],
                  'left_val':['a', 'b', 'c']})
b = pd.DataFrame({'a': [1, 2, 3, 6, 7],
                  'right_val': [1, 2, 3, 6, 7],})

pd.asof_merge(a, b, on='a')
```

It might also be good to show an `ordered_merge` on the same set of data so you can see how they are different?
 sure maybe just in the actual docs / or in doc-string as well?
 yeah, I guess was just thinking about the docs
 @chris-b1 Yes, that is what I meant! 
I was also just experimenting with such a simple example in a notebook
 ok, so I optimized this a bit and got it down form 1.3s -> 500ms. But here's the rub. We have an ability to accept duplicates (on,by) subset for the right frame (e.g. (time,ticker) in quotes in this case).

The problem is that just dropping these dupes are not entirely cheap to drop (and then of course get aggregated into the calculation). Further even the _check_ for duplicates can be expensive. (We don't AFAIK have a cheap way to exit early from a duplicates calculation; its not hard to create though).

Duplicates will WORK on the right frame, they are just not what is expected.
 @jreback Is the plan to push de-dupe back on the user? Or will this be a parameter?
 @chrisaycock I think I can have deduping with only a small penalty. Should it be an option (or always de-dupe)?
 So here's the penalty. I have to check for ANY duplicates (I wrote this short circuit version).
Then if there IS a duplicate then takes about same time to filter.

```
In [4]: def f():
   ...:     idx = pd.MultiIndex.from_arrays([quotes['ticker'],quotes['time']])
   ...:     return idx.duplicated(shortcircuit=True)
   ...: 

In [5]: %timeit f()
10 loops, best of 3: 148 ms per loop

In [6]: quotes.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 1225198 entries, 0 to 1225197
Data columns (total 4 columns):
time      1225198 non-null datetime64[ns]
ticker    1225198 non-null category
bid       1225198 non-null float64
ask       1225198 non-null float64
dtypes: category(1), datetime64[ns](1), float64(2)
memory usage: 29.2 MB
```

So can:

a) ignore this issue if there are dupes then there are dupes in the output
b) do the check and raise/warn (maybe with option)
c) just do the check and drop
 ```
# check_dupes (and has them)
In [2]: %timeit pd.asof_merge(trades, quotes, on='time', by='ticker')
1 loop, best of 3: 809 ms per loop

In [3]: quotes = quotes.drop_duplicates(['time','ticker'],keep='last')

# check (and we don't)
In [4]: %timeit pd.asof_merge(trades, quotes, on='time', by='ticker')
1 loop, best of 3: 718 ms per loop

# don't check and we dont have them
In [5]: %timeit pd.asof_merge(trades, quotes, on='time', by='ticker',check_duplicates=False)
1 loop, best of 3: 526 ms per loop
```

so I added a `check_duplicates` kw to facilitate this.
 ok all update for comments. I added a `check_duplicates` kw for added flexibility.

```
asof_merge(left, right, on=None, left_on=None, right_on=None, by=None, suffixes=('_x', '_y'), tolerance=None, allow_exact_matches=True, check_duplicates=True)
    Perform an asof merge. This is similar to a left-join except that we
    match on nearest key rather than equal keys.

    For each row in the left DataFrame, we select the last row in the right
    DataFrame whose 'on' key is less than or equal to the left's key. Both
    DataFrames must be sorted by the key.

    Optionally perform group-wise merge. This searches for the nearest match
    on the 'on' key within the same group according to 'by'.

    .. versionadded 0.18.2

    Parameters
    ----------
    left : DataFrame
    right : DataFrame
    on : label or list
        Field names to join on. Must be found in both DataFrames.
        The data MUST be ordered. Furthermore this must be numeric index,
        typically a datetimelike or integer-index.
    left_on : label or list, or array-like
        Field names to join on in left DataFrame. Can be a vector or list of
        vectors of the length of the DataFrame to use a particular vector as
        the join key instead of columns
    right_on : label or list, or array-like
        Field names to join on in right DataFrame or vector/list of vectors per
        left_on docs
    by : column name or list of column names
        Group both the left and right DataFrames by the group columns; perform
        the merge operation on these pieces and recombine.
    suffixes : 2-length sequence (tuple, list, ...)
        Suffix to apply to overlapping column names in the left and right
        side, respectively
    tolerance : integer or Timedelta, optional, default None
        select asof tolerance within this range; must be compatible
        to the merge index.
    allow_exact_matches : boolean, default True

        - If True, allow matching the same 'on' value
            (i.e. less-than-or-equal-to)
        - If False, don't match the same 'on' value
            (i.e., stricly less-than)

    check_duplicates : boolean, default True

        - If True, check and remove duplicates for the right
            DataFrame, on the [by, on] combination, keeping the last value
        - If False, no check for duplicates

    Returns
    -------
    merged : DataFrame
```
 I like the additional `check_duplicates`. Looks like the default will always give the the expected answer, and the override allows for better performance if the user knows in advance.
 Would it make sense to have `merge_ordered` and `merge_asof` instead of using the reverse order for the name? That makes things a little more discoverable with auto-complete.
 @shoyer that does make sense. 

we could _in theory_ actually do `pd.merge.asof` (but would have to hijack like you did with `.plot.line`) and such.

?
 > Would it make sense to have merge_ordered and merge_asof instead of using the reverse order 

+1 (had already had the same thought :-) 
although I personally stringly prefer `merge_asof` above `merge.asof`
 pushed with `pd.merge_ordered()` and `pd.merge_asof()` and deprecation of `pd.ordered_merge()`
 `pd.merge.asof` makes sense only if we make `merge` a module. Since that it's the case, let's stick wit `merge_asof`.
 ok added a much simpler example (suggested by @chris-b1 ) to the doc-string.

any final thoughts?
 Some other things:
- It is not fully clear to me what `check_duplicates` does (from the docstring). In practice, you get the last value if there are duplicates with both `True` or `False`. So is the check just for performance reasons?
- I think we should make a more clear choice on the status of the `asof` method. Is it only supposed to be for timeseries data? (as the docstring vaguely says) Then we should be more strict about it. Or do just see it as a general shortcut to using `searchsorted(side='right')`? If so, we should update the docstring and test for this.
- ~~I would personally not add the `shortcircuit` keyword to `duplicated`. It alters the purpose of the method too much IMO.~~ Jeff allready responded to this
 @jorisvandenbossche comments

> It is not fully clear to me what check_duplicates does (from the docstring). In practice, you get the last value if there are duplicates with both True or False. So is the check just for performance reasons?

yes

> I think we should make a more clear choice on the status of the asof method. Is it only supposed to be for timeseries data? (as the docstring vaguely says) Then we should be more strict about it. Or do just see it as a general shortcut to using searchsorted(side='right')? If so, we should update the docstring and test for this.

I don't think so. Its not technically _only_ for timeseries methods, but the vast majority is for that. Further this is common terminology, and already in pandas just like that.

> I would personally not add the shortcircuit keyword to duplicated. It alters the purpose of the method too much IMO.

this is removed, my other check was fine.
 > > It is not fully clear to me what check_duplicates does (from the docstring). In practice, you get the last value if there are duplicates with both True or False. So is the check just for performance reasons?
> 
> yes

Can you then clarify this in the docstring? (when would you want to use this keyword?) 
Maybe also add that this is only used when `by` is specified.
 > It is not fully clear to me what check_duplicates does (from the docstring). In practice, you get the last value if there are duplicates with both True or False. So is the check just for performance reasons?
> yes
> Can you then clarify this in the docstring? (when would you want to use this keyword?) 
> Maybe also add that this is only used when by is specified.

I think this is clear already. Its by default true.
