ENH: add return_inverse to duplicated for DataFrame/Series/Index/MultiIndex
State: closed

Closes #21357 

I followed the recommendation of @jreback there to change `duplicated`, and to make the output a tuple if `return_inverse=True`.

I didn't find a test for the behavior of `DataFrame.duplicated()` -- there's a test of `Index.duplicated()` and `Series.duplicated()` in `tests/test_base.py`, but nothing I could find in `tests/frame/`.

So I added a file to test to test current behavior, as well as the new kwarg. Notably, the backend between the different Series in the output tuple is different (`pandas._libs.hashtable.duplicated_int64` vs. `np.unique`), and so I also added several tests that these results are exactly compatible.

Labels:
name: Enhancement

Comments:
Can you add a whatsnew entry to 0.24.0?

Also, looks like we have asvs for `DataFrame.duplicated`.  Might be nice to add methods for `return_inverse=True` to these.  Not sure if this is strictly necessary though.

https://github.com/pandas-dev/pandas/blob/838e8dac435e1d5a08004e21c0e630a299b6dac0/asv_bench/benchmarks/frame_methods.py#L412-L429
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21645?src=pr&el=h1) Report
> Merging [#21645](https://codecov.io/gh/pandas-dev/pandas/pull/21645?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/44a9b167bda9654ce60588cf2dcee88e4bad831d?src=pr&el=desc) will **decrease** coverage by `0.14%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #21645      +/-   ##
==========================================
- Coverage   92.18%   92.04%   -0.15%     
==========================================
  Files         169      169              
  Lines       50820    50818       -2     
==========================================
- Hits        46850    46776      -74     
- Misses       3970     4042      +72
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.45% <100%> (-0.15%)` | :arrow_down: |
| #single | `42.19% <13.2%> (-0.19%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21645?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/multi.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9tdWx0aS5weQ==) | `95.41% <100%> (-0.04%)` | :arrow_down: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `93.73% <100%> (-0.02%)` | :arrow_down: |
| [pandas/core/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYmFzZS5weQ==) | `96.99% <100%> (-0.62%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.21% <100%> (+0.01%)` | :arrow_up: |
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.8% <100%> (+0.11%)` | :arrow_up: |
| [pandas/core/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9jYXRlZ29yeS5weQ==) | `97.28% <100%> (+0.01%)` | :arrow_up: |
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `96.45% <100%> (+0.05%)` | :arrow_up: |
| [pandas/io/formats/console.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvY29uc29sZS5weQ==) | `65.15% <0%> (-10.61%)` | :arrow_down: |
| [pandas/errors/\_\_init\_\_.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2Vycm9ycy9fX2luaXRfXy5weQ==) | `92.3% <0%> (-7.7%)` | :arrow_down: |
| [pandas/core/dtypes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZHR5cGVzL2Jhc2UucHk=) | `92.68% <0%> (-7.32%)` | :arrow_down: |
| ... and [55 more](https://codecov.io/gh/pandas-dev/pandas/pull/21645/diff?src=pr&el=tree-more) | |

------

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

@jschendel @WillAyd 
Thanks for the feedback, working to incorporate all the comments.

Another question that I realised while writing the whatsnew entry - should this kwarg be made available to Series/Index as well? In this case I'm guessing I'd have to adapt `core.base.IndexOpsMixin.duplicated`?
@jschendel Re:
> Also, looks like we have asvs for DataFrame.duplicated. Might be nice to add methods for return_inverse=True to these. Not sure if this is strictly necessary though.

Haven't ever worked with the asv's yet - will have a look later.
I added three runs in the ASV, here are the results against current master. I don't know why `frame_methods.Duplicated.time_frame_duplicated` failed on master, that shouldn't be the case - all the others are explained by the missing `return_inverse` kwarg on master.

Edit: ran again on a clean, restarted machine with no background applications.

```
  before           after         ratio
[a620e725]       [094139bf]
       203ms            203ms     1.00  frame_methods.Duplicated.time_frame_duplicated
-     78.1ms           70.3ms     0.90  frame_methods.Duplicated.time_frame_duplicated_mixed
      failed            156ms      n/a  frame_methods.Duplicated.time_frame_duplicated_mixed_inverse
      failed            125ms      n/a  frame_methods.Duplicated.time_frame_duplicated_mixed_inverse_last
       203ms            203ms     1.00  frame_methods.Duplicated.time_frame_duplicated_wide
      failed            203ms      n/a  frame_methods.Duplicated.time_frame_duplicated_wide_inverse
```
Hello @h-vetinari! Thanks for updating the PR.































Cheers ! There are no PEP8 issues in this Pull Request. :beers: 

##### Comment last updated on August 31, 2018 at 08:00 Hours UTC
Test failure in circleci is unrelated. Failed in `TestPythonParser.test_dtype_with_converter` with 
```
E           AssertionError: Caused unexpected warning(s): ['ResourceWarning'].
```
@mroeschke 
I got the results now, although I had to add a temporary if-condition (otherwise `master` would stumble over the unknown kwarg). Will remove that condition again, but I just wanted to have the same hash show up in the comparison as well as the commit I just pushed. Here are the results:

```
   before      after       ratio
 [a620e725]  [36b03a1c]
      203ms       203ms     1.00  frame_methods.Duplicated.time_frame_duplicated('first', False)
     failed       578ms      n/a  frame_methods.Duplicated.time_frame_duplicated('first', True)
+     203ms       250ms     1.23  frame_methods.Duplicated.time_frame_duplicated('last', False)
     failed       438ms      n/a  frame_methods.Duplicated.time_frame_duplicated('last', True)
     78.1ms      78.1ms     1.00  frame_methods.Duplicated.time_frame_duplicated_mixed('first', False)
     failed       125ms      n/a  frame_methods.Duplicated.time_frame_duplicated_mixed('first', True)
     78.1ms      78.1ms     1.00  frame_methods.Duplicated.time_frame_duplicated_mixed('last', False)
     failed       125ms      n/a  frame_methods.Duplicated.time_frame_duplicated_mixed('last', True)
      219ms       203ms     0.93  frame_methods.Duplicated.time_frame_duplicated_wide('first', False)
     failed       203ms      n/a  frame_methods.Duplicated.time_frame_duplicated_wide('first', True)
      203ms       203ms     1.00  frame_methods.Duplicated.time_frame_duplicated_wide('last', False)
     failed       203ms      n/a  frame_methods.Duplicated.time_frame_duplicated_wide('last', True)
```

To me, the benchmarks seem a bit unstable, otherwise I don't know where the performance differences come from.
As I already mentioned above, it became obvious to me while writing the whatsnew entry that this kwarg should be enabled for Series/Index as well. The last commit contains a working version but no tests yet -- ran into troubles with #21684. Additional xref #21685

This is already much more elegant than the previous commits, because it does all the work for `return_inverse` in one spot (`pandas.core.algorithms`), and all the calling objects just need to wrap around that.

In summary, the following is still lacking:
* tests for Series/Index/MultiIndex
* asv for Series/Index/MultiIndex
* update whatsnew
I finally finished adding all the tests, turns out it's quite complicated to do anything for `Index`, haha. ;-)

The core algorithm changes almost vanish compared to the amount of test changes. Some of the things I added tests for were not really tested so far (bare `duplicated` was only tested implicitly - and then only sometimes - for stuff like `drop_duplicates`). I also split up `pandas/tests/indexes/multi/test_unique_and_duplicates.test_duplicated`, which had a large amount of tests in one.

ASVs should be in line with what I posted above, because as long as `return_inverse=False`, I never calculate anything additional.

I needed to implement a different signature for `pandas.core.algorithms.duplicated`, which is inspired by `np.unique`, in the sense that it has both `return_index` and `return_inverse` (with the same meanings). This method is not public as far as I can tell? In any case, the docstring reflects the changes.
Finally, I added a `stabilize`-kwarg, which *stabilises* against the implicit sorting that numpy does. It's on by default, but turning it off is a performance improvement in case the index/inverse are immediately plugged together again (as is the case for `Series`/`DataFrame`).

Tried to explain all the code as well as possible, but happy to receive feedback (and/or answer questions).
> pls pls let's keep the scope to the original. just return_inverse. If you want to do more things, make them PR's on top.

@jreback I did keep strictly with the scope of just adding `return_inverse` to `duplicated`. The issue is that `Series/DataFrame` need a *slightly* different treatment than `Index`:
* the inverse for `Series/DataFrame` needs to take into account two indexes (the original index, and the one of the deduplicated data). This needs to combine the outputs `return_index=True` and `return_inverse=True` from `np.unique`.
* the inverse for `Index` is just a simple `np.ndarray`, which would in principle just need `return_inverse=True` from `np.unique`, except we need to undo the implicit sorting that `np.unique` does.

There are two options from my POV:
1. implement two different `duplicated`-methods for `Series/DataFrame` vs. `Index`, which would however overlap if `return_inverse=False`.
1. (current state of PR) implement one central `duplicated`-method, but with enough flexibility to cover both cases, and have thin wrappers around that. Since -- AFAIU -- `pandas.core.algorithms.duplicated` is not public API, I decided to add that extra flexibility.

Does that make the situation clearer? I don't mind implementing option 1, but it would lead to code duplication and would IMHO be messier.
Ugh, resolving conflicts on windows is such a pain (conflict resolution commits not recognised by git). Had to do a massive rebase...

Also added some examples to the separate `duplicated`-docstrings.
@jreback 

I refactored `core.algorithms.duplicated` and removed the offending kwargs. This means that for the `Series/DataFrame` case, there is some unnecessary `argsort`-ing happening, but I'm guessing that performance penalty (up to 2x as long) is more welcome than having a different method-signature. For completeness, the ASV-comparison is below.

I also reworked the `Series/DataFrame/Index` docstrings - it might be instructive to have a look at the examples. :)

```
     before           after       ratio
   [93bd97f3]       [18b15eb1]
        234ms            250ms     1.07  frame_methods.Duplicated.time_frame_duplicated('first', False)
+       438ms            828ms     1.89  frame_methods.Duplicated.time_frame_duplicated('first', True)
-       219ms            188ms     0.86  frame_methods.Duplicated.time_frame_duplicated('last', False)
+       656ms            1.02s     1.55  frame_methods.Duplicated.time_frame_duplicated('last', True)
-       250ms            219ms     0.88  frame_methods.Duplicated.time_frame_duplicated(False, False)
       78.1ms           85.9ms     1.10  frame_methods.Duplicated.time_frame_duplicated_mixed('first', False)
+       125ms            188ms     1.50  frame_methods.Duplicated.time_frame_duplicated_mixed('first', True)
       85.9ms           78.1ms     0.91  frame_methods.Duplicated.time_frame_duplicated_mixed('last', False)
+       172ms            203ms     1.18  frame_methods.Duplicated.time_frame_duplicated_mixed('last', True)
       85.9ms           85.9ms     1.00  frame_methods.Duplicated.time_frame_duplicated_mixed(False, False)
        219ms            203ms     0.93  frame_methods.Duplicated.time_frame_duplicated_wide('first', False)
+       203ms            234ms     1.15  frame_methods.Duplicated.time_frame_duplicated_wide('first', True)
        203ms            203ms     1.00  frame_methods.Duplicated.time_frame_duplicated_wide('last', False)
        203ms            219ms     1.08  frame_methods.Duplicated.time_frame_duplicated_wide('last', True)
        203ms            219ms     1.08  frame_methods.Duplicated.time_frame_duplicated_wide(False, False)
   3.77±0.3ms         3.47±0ms     0.92  series_methods.Duplicated.time_series_duplicated('first', False)
      141±8ms         141±10ms     1.00  series_methods.Duplicated.time_series_duplicated('first', True)
   3.35±0.2ms       3.91±0.2ms    ~1.17  series_methods.Duplicated.time_series_duplicated('last', False)
      156±8ms          172±8ms     1.10  series_methods.Duplicated.time_series_duplicated('last', True)
   3.47±0.2ms       3.91±0.3ms    ~1.12  series_methods.Duplicated.time_series_duplicated(False, False)
```
@jschendel @WillAyd @mroeschke @jreback 
gentle ping since everything is green and I now incorporated (resp. responded to) all your feedback.
@jschendel @WillAyd @mroeschke @jreback
I know this ping is quite soon after the last - please excuse. I'll be gone for a while in about a week, and would prefer to get this done before, instead of having to do lots of rebasing afterwards.
@jreback I split out all the orthogonal changes (often in more consistent form than here) into independent PRs - #21897 #21898 #21899 #21900 #21902 - hope this helps with reviewing. I'll leave the docstring additions in here for now, but if that's an issue, I can add have another PR for them as well. ASV changes should IMO be part of this PR and not a follow-up.
@jreback @WillAyd Rebased on the merged PRs and the most current state of #21902.
@jreback @WillAyd Now that #21902 is in, all preparatory PRs should be out of the way, and this is ready to be discussed again.
@jreback @WillAyd This has been lying around for about a month or so. Could you guys have a look please? :)
Traveling for a few days but can review again next week. Larger PRs just take more time to review - definitely still appreciate the contribution (and patience!)
@WillAyd No problem. :)
TBH, part of the reason for not having pushed this more is that I still want to get #22225 in beforehand, but that PR itself is waiting for #22486, which is blocked by #22236, haha...
@WillAyd I incorporated your feedback - any open questions?

@jreback care to take a look?
@jorisvandenbossche

> What is the reason you decided to add it to duplicated and not drop_duplicates ? (because from quickly looking at the issue, and from the docstring examples, that is actually what you want?)
I also ask because I think it would be a more natural fit there, as it is not literally an "inverse" for the result of duplicated (as it is for drop_duplicates or as for unique in numpy)

I wanted to add `.unique` method in #21357, but got told by @jreback that:
> -1 on adding any new methods, but would be ok with adding a return_inverse kwarg (clearly defaulting to False), to .duplicated() to easily recovering the indexer.

I still think it makes sense for `duplicated`, which is invoked by `drop_duplicates`, and so would need to support that anyway if one wanted to add it to `drop_duplicates`.

> I think we should have more discussion (or at least motivation for the current design) about the actual return value (series vs array, index labels vs positional integers). Always returning an array of integers would also be an option (and is eg robust for duplicates in the index)

numpy returns two arrays of indexes, one relative to the original set and one relative to the unique values. I think this information fundamentally belongs together and since pandas supports the index/values distinction, I strongly believe that they should live in the same object. I don't like reusing the index of `duplicated` itself, because then I need to keep around *two* separate objects to reconstruct. But happy to discuss alternative approaches.

@jorisvandenbossche 
I incorporated your feedback. Since no compelling alternatives have come up for the return type, I left that aspect as-is.
@jreback @WillAyd @jorisvandenbossche 

How can I/we move this PR forward?
@h-vetinari sorry for the slow answer

I think my main worry is that we are adding a `return_inverse` keyword which actually does not return the inverse for that function (it does return the inverse for another function), and that it is in name similar to numpy's keyword, but in usage also different.

Numpy's `unique` is more comparable to `drop_duplicates`. Therefore I think such a keyword would be  a more natural fit there.


> numpy returns two arrays of indexes

Can you clarify this? You are talking about `np.unique`?  (but I think that only returns a single array of indices?)

Side note: it might make sense to add this to `pd.unique` / `Series.unique` as well? (not necessarily at the same time; or might actually be an easier starter)


@jorisvandenbossche 

> I think my main worry is that we are adding a return_inverse keyword which actually does not return the inverse for that function (it does return the inverse for another function), and that it is in name similar to numpy's keyword, but in usage also different.

Fair point. I would prefer a `df.unique` as well, but was following what I was told in #21357
> -1 on adding any new methods, but would be ok with adding a return_inverse kwarg (clearly defaulting to False), to .duplicated() to easily recovering the indexer.

which is how I implemented it here. Could still be added to `drop_duplicates` as well, but since that depends on `duplicated`, we'd need it there anyway.

Re: 
> >  numpy returns two arrays of indexes

> Can you clarify this? You are talking about np.unique? (but I think that only returns a single array of indices?)

https://docs.scipy.org/doc/numpy/reference/generated/numpy.unique.html has both `return_indices` and `return_inverse`, and both are necessary to reconstruct from the pandas side (the difference for us being that we also need to keep track of the index, whereas numpy just has `arange` as index).

> Side note: it might make sense to add this to pd.unique / Series.unique as well? (not necessarily at the same time; or might actually be an easier starter)

Agreed. Actually, for me the best solution would be: 
* add `df.unique` (could be a thin wrapper around `drop_duplicates`)
* have `df.unique`, `series.unique`, `index.unique` with `return_inverse`-kwarg
* dispatch from `pd.unique` to appropriate code branch
> Fair point. I would prefer a df.unique as well, but was following what I was told in #21357

I have wanted a `DataFrame.unique` for a long time, but the question is how it would be different compared to `drop_duplicates`? 

Anyway, yes @jreback put you on the path to add it to `duplicated` as a first idea, but I am questioning that choice. So regardless of previous recommendation, we should still discuss that (@jreback can you chime in here?)

> numpy.unique has both return_indices and return_inverse, and both are necessary to reconstruct from the pandas side

I think the numpy's `return_indices` is rather unrelated here? It is about the index into the original array to get the unique ones, while you want to preserve the index of the original array?

> Agreed. Actually, for me the best solution would be:
>
>    add df.unique (could be a thin wrapper around drop_duplicates)
>   have df.unique, series.unique, index.unique with return_inverse-kwarg
>    dispatch from pd.unique to appropriate code branch

Adding a `return_inverse` to the existing `unique` function / methods would certainly be a welcome change I think.

i am not against adding this to .unique, though as you have mentioned that is indeed just drop_duplicates
@jorisvandenbossche 
Thanks for your answer:

> I have wanted a DataFrame.unique for a long time, but the question is how it would be different compared to drop_duplicates?

I would suggest that `unique` just acts as a thin wrapper around `drop_duplicates`. The latter has been in the pandas API forever, but the former name is even more established, and I think they could peacefully coexist.

> I think the numpy's return_indices is rather unrelated here? It is about the index into the original array to get the unique ones, while you want to preserve the index of the original array?

Assuming `np.unique` didn't sort (which I have to laboriously undo in this PR) and `keep='first'`, we would have:
```
isduplicated = some_series.duplicated()
_, values2unique, unique2values = np.unique(some_series.values,
                                            return_index=True, return_inverse=True)
inverse = Series(some_series.index[values2unique][unique2values], index=some_series.index)
```

and neither `values2unique` (the indices) nor `unique2values` (the inverse) can be omitted. Again, the difference to `numpy` here is that `some_series` can have an index different from `arange(len(some_series))`, which is why we need to first select the right indices of the index (to get the uniques) and the broadcast them back to the full shape to get the full inverse. If we didn't care about the index of `some_series`, then the indices would indeed be not necessary, but then we wouldn't be able to use the inverse in `.loc` or `.reindex` of the uniques (`=some_series.loc[~isduplicated]`), because the indexes wouldn't match.

> Adding a return_inverse to the existing unique function / methods would certainly be a welcome change I think.

I had already collected some thoughts for this during the day and opened a (largely orthogonal to this PR) issue for this: #22824

EDIT: clarified mechanics for inverse