Fix nsmallest/nlargest With Identical Values
State: closed

 - [x] closes #15297 
 - [x] tests added / passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew entry


Labels:
name: Bug
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode

Comments:
@jreback What do you think of this approach? The issue before was on this line
https://github.com/pandas-dev/pandas/blob/master/pandas/core/algorithms.py#L917
when merging series with the frame when values are identical you end up duplicating the df potentially `n` times

(obviously PR isn't ready to go, just wanted your opinion on the approach first)
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=h1) Report
> Merging [#15299](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/1fbdc23def1cc91280c508ac5b7806ced579b264?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/15299/graphs/tree.svg?width=650&src=pr&token=eZ4WkYLtcO&height=150)](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #15299      +/-   ##
==========================================
+ Coverage   90.96%   90.96%   +<.01%     
==========================================
  Files         145      145              
  Lines       49534    49560      +26     
==========================================
+ Hits        45057    45082      +25     
- Misses       4477     4478       +1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.72% <100%> (ø)` | :arrow_up: |
| #single | `40.61% <3.12%> (-0.02%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `93.92% <100%> (+0.23%)` | :arrow_up: |
| [pandas/core/common.py](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY29tbW9uLnB5) | `90.68% <0%> (-0.35%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=footer). Last update [1fbdc23...d3964f8](https://codecov.io/gh/pandas-dev/pandas/pull/15299?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
any progress?
Ah, sorry @jreback been super busy, haven't gotten around to this. Will try and get to it over the weekend, is that ok?
@RogerThomas np. just pushing things along. you can ping when you are ready for a review.
here is another example: https://github.com/pandas-dev/pandas/issues/14846#issuecomment-281338268
@RogerThomas can you rebase / update.
@jreback sorry took so long on this, been super busy. 
This should be good to go now
OK @jreback pretty sure this is ready to go now.

Saving and restoring duplicated index turned out to be challenging when considering multi-indexes, but managed to get it.
don't jump thru hoops not to copy, we copy *everywhere* as that is idiomatic pandas.
ok, if you change .reindex -> .take then I think this will be ok.
OK @jreback changes made
@RogerThomas I pushed a couple of commits.

fixed the minor PEP issue.
I added some systematic tests, a couple of which fail, can you have a look?
@jreback updated tests for object dtypes

Also had to update algorithm as your tests exposed a flaw in the previous algorithm
Hey @jreback 
How about this?

https://github.com/RogerThomas/pandas/pull/5
this is prob because Series is not tested as well. Let me see if I can fix this (and you can rebase on top).

```
=================================== FAILURES ===================================
___________________ TestNLargestNSmallest.test_n_all_dtypes ____________________
[gw0] linux2 -- Python 2.7.13 /home/travis/miniconda3/envs/pandas/bin/python
self = <pandas.tests.frame.test_analytics.TestNLargestNSmallest object at 0x7ff6da2795d0>
df_main_dtypes =    group  int  float string category_string  category_int   datetime  \
0     ...1 2013-01-02 00:00:00-05:00  00:00:02  
2 2013-01-03 00:00:00-05:00  00:00:03  
    def test_n_all_dtypes(self, df_main_dtypes):
        df = df_main_dtypes
>       df.nsmallest(2, list(set(df) - {'category_string', 'string'}))
/home/travis/miniconda3/envs/pandas/lib/python2.7/site-packages/pandas/tests/frame/test_analytics.py:1998: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
/home/travis/miniconda3/envs/pandas/lib/python2.7/site-packages/pandas/core/frame.py:3478: in nsmallest
    return algorithms.select_n_frame(self, columns, n, 'nsmallest', keep)
/home/travis/miniconda3/envs/pandas/lib/python2.7/site-packages/pandas/core/algorithms.py:976: in select_n_frame
    values = getattr(series, method)(cur_n, keep=keep)
/home/travis/miniconda3/envs/pandas/lib/python2.7/site-packages/pandas/core/series.py:1907: in nsmallest
    method='nsmallest')
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
series = 0   2013-01-01 00:00:00-05:00
1   2013-01-02 00:00:00-05:00
2   2013-01-03 00:00:00-05:00
Name: datetimetz, dtype: datetime64[ns, US/Eastern]
n = 2, keep = 'first', method = 'nsmallest'
    def select_n_series(series, n, keep, method):
        """Implement n largest/smallest for pandas Series
    
        Parameters
        ----------
        series : pandas.Series object
        n : int
        keep : {'first', 'last'}, default 'first'
        method : str, {'nlargest', 'nsmallest'}
    
        Returns
        -------
        nordered : Series
        """
        dtype = series.dtype
        if not issubclass(dtype.type, (np.integer, np.floating, np.datetime64,
                                       np.timedelta64)):
>           raise TypeError("Cannot use method %r with dtype %s" % (method, dtype))
E           TypeError: Cannot use method 'nsmallest' with dtype datetime64[ns, US/Eastern]
/home/travis/miniconda3/envs/pandas/lib/python2.7/site-packages/pandas/core/algorithms.py:915: TypeError
============ 1 failed, 8537 passed, 1991 skipped in 546.94 seconds =============
```
@RogerThomas ok #15902 fixes the tz problem in series nsmallest. after I merge you should be able to easilly rebase on top, just take``pandas/tests/series/test_analytics.py`` from master and you should be good to go.
@RogerThomas ok merged that PR in. pls rebase and should work!
OK @jreback tests passing for me
thanks @RogerThomas very nice PR! and excellent responsiveness on changes.

keem em coming!