BUG: nlargest/nsmallest gave wrong result (#22752)
State: closed

- [X] closes #22752 
- [X] tests added / passed
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [X] whatsnew entry

When asking for the n largest/smallest rows in a dataframe
nlargest/nsmallest sometimes failed to differentiate
the correct result.

I looked at the nsmallest/nlargest implementation for data frames and to
me it looks wrong. 

With ties in the first columns, the old algorithm picked all duplicates rather
than all values that lies on the border for the next tie-break iteration.
That meant that to find the top 5 values in a data frame like e.g:
   
[0 5] [0 4] [1 0] [2 3] [2 2] [2 1]

1. the algorithm would first pick the top 5 via the first column:
(That would be [1 0] [2 1] [2 2] [2 3] [0 4] [0 5])
2. It would then try to pick the values that were certain (that is the unique 
first column values, that is):
[1 0]
3. and go on for the next iteration with all rows where the first column value was non-unique but among the top 5:
That is: [2 3] [2 2] [2 1] [0 4] [0 5]
4. It would the compare the remaining on the second column, picking: [0 5] [0 4] [2 3] [2 2]
5. Finally returning: [1 0] [0 5] [0 4] [2 3] [2 2]

Which is not the correct result: [1 0][0 4] [2 3] [2 2] [2 1]

I've changed the algorithm so instead of tie-breaking on all values having duplicates in an earlier column, it will now tie break only on the duplicates of the largest/smallest value in a given column, so it will do:

1. Pick top 5 of column 1:
[1 0] [2 1] [2 2] [2 3] [0 4] [0 5]
2. zero is the border value, the rest is safe:
[1 0] [2 1] [2 2] [2 3]
3.  [0 4] [0 5] goes on to the next iteration:
4. 5 > 4 so [0 5] is the top 1 of what's left:
5. The result is:  [1 0] [2 1] [2 2] [2 3] [0 5]

Which is the correct result.

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

Comments:
Hello @troels! Thanks for updating the PR.

 - There are no PEP8 issues in the file [`asv_bench/benchmarks/frame_methods.py`](https://github.com/troels/pandas/blob/63218fde8630f8ea474ef83191f010817f6e327d/asv_bench/benchmarks/frame_methods.py) !

 - There are no PEP8 issues in the file [`pandas/core/algorithms.py`](https://github.com/troels/pandas/blob/63218fde8630f8ea474ef83191f010817f6e327d/pandas/core/algorithms.py) !

 - There are no PEP8 issues in the file [`pandas/tests/frame/test_analytics.py`](https://github.com/troels/pandas/blob/63218fde8630f8ea474ef83191f010817f6e327d/pandas/tests/frame/test_analytics.py) !



##### Comment last updated on September 23, 2018 at 16:58 Hours UTC
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22754?src=pr&el=h1) Report
> Merging [#22754](https://codecov.io/gh/pandas-dev/pandas/pull/22754?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/4cc0a71c729aaf9a5cf46a2c4b3fd5e0a4fd37a9?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/22754/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/22754?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #22754      +/-   ##
==========================================
+ Coverage   92.18%   92.18%   +<.01%     
==========================================
  Files         169      169              
  Lines       50820    50823       +3     
==========================================
+ Hits        46850    46853       +3     
  Misses       3970     3970
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.6% <100%> (ø)` | :arrow_up: |
| #single | `42.37% <0%> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/22754?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/22754/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.72% <100%> (+0.02%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/22754?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/22754?src=pr&el=footer). Last update [4cc0a71...63218fd](https://codecov.io/gh/pandas-dev/pandas/pull/22754?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Can you run asv on the nlargest / nsmallest benchmarks: http://pandas-docs.github.io/pandas-docs-travis/contributing.html#running-the-performance-test-suite
Hi @TomAugspurger, 

I ran the benchmark which gave me no significant changes. 

I thought that was odd since the old version seemed to do a lot of work. I checked and the old benchmarks only tested sorting on a single column, which is kind of non-controversial.

I therefore added two new benchmarks and increased the size of the tested dataframe a bit. Here is  the results:
```
[ 56.25%] ··· frame_methods.NSort.time_nlargest_one_column                                                                                                 ok
[ 56.25%] ··· ======= ============
                keep              
              ------- ------------
               first   4.02±0.3ms 
                last   3.24±0.2ms 
                all    3.61±0.1ms 
              ======= ============

[ 62.50%] ··· frame_methods.NSort.time_nlargest_two_columns                                                                                                ok
[ 62.50%] ··· ======= ============
                keep              
              ------- ------------
               first   5.46±0.4ms 
                last   5.11±0.2ms 
                all    5.26±0.1ms 
              ======= ============

[ 68.75%] ··· frame_methods.NSort.time_nsmallest_one_column                                                                                                ok
[ 68.75%] ··· ======= ============
                keep              
              ------- ------------
               first   3.55±0.2ms 
                last   3.71±0.1ms 
                all    3.48±0.2ms 
              ======= ============

[ 75.00%] ··· frame_methods.NSort.time_nsmallest_two_columns                                                                                               ok
[ 75.00%] ··· ======= ============
                keep              
              ------- ------------
               first   4.87±0.2ms 
                last   4.73±0.2ms 
                all    4.73±0.2ms 
              ======= ============

[ 75.00%] · For pandas commit fb784caf <ci> (round 2/2):
[ 75.00%] ·· Building for conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt...
[ 75.00%] ·· Benchmarking conda-py3.6-Cython-matplotlib-numexpr-numpy-openpyxl-pytables-pytest-scipy-sqlalchemy-xlrd-xlsxwriter-xlwt
[ 81.25%] ··· frame_methods.NSort.time_nlargest_one_column                                                                                                 ok
[ 81.25%] ··· ======= ============
                keep              
              ------- ------------
               first   3.97±0.1ms 
                last   3.45±0.1ms 
                all    4.11±0.1ms 
              ======= ============

[ 87.50%] ··· frame_methods.NSort.time_nlargest_two_columns                                                                                                ok
[ 87.50%] ··· ======= ============
                keep              
              ------- ------------
               first   6.68±0.2ms 
                last   6.39±0.1ms 
                all    6.67±0.2ms 
              ======= ============

[ 93.75%] ··· frame_methods.NSort.time_nsmallest_one_column                                                                                                ok
[ 93.75%] ··· ======= =============
                keep               
              ------- -------------
               first   3.65±0.07ms 
                last   3.67±0.08ms 
                all    3.65±0.01ms 
              ======= =============

[100.00%] ··· frame_methods.NSort.time_nsmallest_two_columns                                                                                               ok
[100.00%] ··· ======= =============
                keep               
              ------- -------------
               first    6.29±0.2ms 
                last    6.64±0.1ms 
                all    6.30±0.07ms 
              ======= =============

       before           after         ratio
     [fb784caf]       [9d94f27c]
     <ci>             <nlargest-nsmallest>
-      6.29±0.2ms       4.87±0.2ms     0.77  frame_methods.NSort.time_nsmallest_two_columns('first')
-     6.30±0.07ms       4.73±0.2ms     0.75  frame_methods.NSort.time_nsmallest_two_columns('all')
-      6.64±0.1ms       4.73±0.2ms     0.71  frame_methods.NSort.time_nsmallest_two_columns('last')

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

So the new version is also significantly faster, and more so the larger the original dataframe is and the more columns being sorted on.
ok @troels this looks good (just add some more comments as indicated), ping on green.
Ok, I've added some more comments. I hope the mechanism is clearer now.
lgtm. you have a lint error, ping on green.
@jreback The lint error should be fixed now. The failing ci-run in pandas-dev.pandas looks like a flaky network connection while setting up the testrun.
thanks @troels