ENH: Add argmax and argmin to ExtensionArray
State: closed

-  closes #24382
-  tests added
-  passes `black pandas`
-  passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
-  whatsnew entry

The methods added in this PR ignore `nan` ,i.e., `skipna=True`. The existing `categorical.min` return `nan` if `categorical` contain any `nan`. This behavior is expected in `test_min_max` (tests/arrays/categorical/test_analytics.py). 

Labels:
name: ExtensionArray
description: Extending pandas with custom dtypes or arrays.

Comments:
can you merge master; move the release note to 1.0
@jreback This PR is pending for #27929 in which whether the keyword `numeric_only` should be deprecated is still in discussion.
@makbigc can you rebase?  I think getting these implemented could help with some of the groupby cleanup ive been working on
@makbigc can you rebase
sorry for the late reply. I will work on it.
This would definitely be a neat feature @makbigc are you still wanting to work on this?
@makbigc can you merge master?
Hello @makbigc! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:











There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2020-07-08 12:15:58 UTC
I don't know what linting error I have made.
Please tell me anything else to change.
Thanks.
@makbigc mind merging master - will then take a look at any test failures.
@makbigc sorry to chase you up, just wanted to ask - are you still working on this? Thanks :)
@alimcmaster1 Corrected. Please tell me anything else. We can finish this PR soon.
@jreback Finally, all tests are passed. Please have a look.
Dear all, the present approach is to raise an error for an empty array (like numpy).
@jreback Should we open a new PR to discuss whether an empty `ExtensionArray` raises an error? So we can finish this long PR? Thanks a lot.
> @jreback Should we open a new PR to discuss whether an empty `ExtensionArray` raises an error? So we can finish this long PR? Thanks a lot.

no, I think this is a crucial decision and am for simply returning a null value rather than raising which is inconsistent with the rest of pandas.
cc @TomAugspurger @jorisvandenbossche 
Can I just say.

For all currently implemented extension arrays, `EA.argsort` defers to `EA._values_for_argsort`, which is kind of like `EA._ndarray_values` and, in particular, is ordinal. Since the underlying values are ordinal, which actually needs to be the case if any kind of `argsort` was _ever_ going to work at all, `argmin`, `argmax`, `min` and `max` operations can all be implemented in linear O(N) time instead of the proposed O(NlogN) time.
> Can I just say.
> 
> For all currently implemented extension arrays, `EA.argsort` defers to `EA._values_for_argsort`, which is kind of like `EA._ndarray_values` and, in particular, is ordinal. Since the underlying values are ordinal, which actually needs to be the case if any kind of `argsort` was _ever_ going to work at all, `argmin`, `argmax`, `min` and `max` operations can all be implemented in linear O(N) time instead of the proposed O(NlogN) time.
> 
> ~EA API is horrid.~ 😭

wow this is a constructive comment

> all be implemented in linear O(N) time instead of the proposed O(NlogN) time.

since this uses numpy arg sort under the hood how, why is this the case?
> wow this is a constructive comment

It was best positioned after a whole day of figuring out a new "`ExtensionOrdinalReductionsMixin`" to make numeric reductions trivially accessible to all inheriting EAs. The API itself may not be that bad, just all the supporting code. :sweat_smile: 

> since this uses numpy arg sort under the hood how, why is this the case?

The mere fact that we are sorting, argsort, quicksort, supra-linear time complexity.
@makbigc not sure where we stand on this, can you merge master and will look again
This PR may not be a good idea.
Despite of the effect, this PR is closed.
Thanks for the review.
A collection of fallback default EA reduction methods is really an _essential_ idea!

Given the API grants [`factorize` primitives](https://www.slideshare.net/TwoSigma/future-of-pandas-jeff-reback/15) (i.e. _categories_ and _codes_), values like max, min, argmax, argmin, argsort, count, median can be efficiently obtained from mere codes when categories are _ordered_—mode even when not—, while values like mean, sum, std etc. by an additional lookup through categories table (or rather `EA._ndarray_values` or some such to avoid copy), offloading _distance_ semantics to categories type.

It can be done efficiently for all current builtin EA types that wrap ndarray. And is something the users had certainly expected to work before wider EA release. :smile: I feel like ten years ago.
@makbigc sorry for not responding much in the discussions above. Although it has been a difficult discussion, it's an important one to finish, so I am reopening the PR. 
I certainly understand if you would prefer not further working on this one, in which case I can also push some updates later. But let's first try to get some common understanding on the remaining issues / goals.

> [@kernc] `EA.argsort` defers to `EA._values_for_argsort`. ... Since the underlying values are ordinal, which actually needs to be the case if any kind of `argsort` was _ever_ going to work at all, `argmin`, `argmax`, `min` and `max` operations can all be implemented in linear O(N) time instead of the proposed O(NlogN) time.

Being concrete here, you mean we can get eg `argmin` directly based on `_values_for_argsort` instead of going through the `argsort` route? 
So in pseudo code, doing `np.argmin(EA._values_for_argsort())` instead of `np.argsort(EA._values_for_argsort())[0]` ?

If so, I fully agree with that. It's not only faster, but actually also more correct. `argmax` is supposed to give the *first* occurence of a maximum, while `self.argsort()[-1 - no_nan]` gives the last occurence. 
We still need some handling of missing values (similarly as is done in the internal `argsort` implementation), but that should be relatively easy (basically filtering them out, which is what our internal `argsort` does).

---

Rereading the comments above, it seems main discussion point is about the behaviour of min/max of empty arrays: What should min/max do for empty arrays, raise (which numpy does) or return nan (as pands does for Series/Index).

It might also make sense to focus on `argmin` / `argmax` for now in this PR, since I think the desired behaviour for those is clear and non-controversial (and in addition, `min` / `max` also overlap with some other recent work being done). 
I think it would already be very useful to have argmin/argmax in as a first step (and in general, smaller scoped PRs will get reviewed/merged faster). In the meantime we can discuss what to do with min/max.


Some concrete to do items I see, apart from updating on latest master:

- Update the implementation of argmax/argmin to use `_values_for_argsort` directly
- Add more tests for argmax/argmin corner cases: with repeated values (ensuring the index of the first occurence is returned), with all-NA values
OK, I pushed some updates to this PR:

* Removed `min`/`max` for now, to focus this PR on `argmin`/`argmax` (and it's still in the git history of course)
* Made an implementation of `argmin`/`argmax` based on `_values_for_argsort`, with missing value handling, similar as we currently have `pandas/core/sorting.py::nargsort`
* Expanded the tests to cover duplicated values / all missing values.

So all please take a new look!

I didn't yet hook this into `Series.argmin/argmax` (there is the question what the all-NaN case, where Series currently deviates from EA -> https://github.com/pandas-dev/pandas/issues/33941).  

What's also still missing is a `skipna=False` keyword, but let's start with reviewing the current updates (-> https://github.com/pandas-dev/pandas/issues/33942 for an issue about this)
> Made an implementation of argmin/argmax based on _values_for_argsort

My understanding based on other threads is that we shouldn't be using _values_for_(argsort|factorize) for anything other than (argsort|factorize)
@jbrockmendel I think `argsort` and `argmax/min` are basically the same regarding requirements on `_values_for_argsort` ? 

Before we better define the expected sematics of `_values_for_argsort`, we indeed shouldn't use it in other context as argsort (eg indexing). But IMO argsort and argmax/min are the same *kind* of usage. 

> Before we better define the expected sematics of _values_for_argsort, we indeed shouldn't use it in other context as argsort (eg indexing). But IMO argsort and argmax/min are the same kind of usage.

I dont understand this distinction.  My understanding based on what you've said elsewhere is that we cant count on _values_for_argsort to be implemented, only argsort
> I dont understand this distinction.

`_values_for_argsort` is used to implement `argsort`, and hence has certain requirements on the return value of `_values_for_argsort` (sort in the same order, but in practice now don't need to handle missing values).  
As far as I can see, `argmax`/`argmin` have the exact same requirements as argsort (at least I can't think of a case where argsort would work but argmax/argmin would fail or be incorrect. Can you?). But that is not at all the case for using those values in indexing context, or in joining operations, where there are additional requirements (hashable, handle missing values), and thus for those we can't simply assume that `_values_for_argsort` is usable for those use cases just because it is usable for `argsort`. But for argmax/argmin, I think we clearly *can* make this assumption.

> My understanding based on what you've said elsewhere is that we cant count on _values_for_argsort to be implemented, only argsort

That was indeed the original idea: as EA author you can either implement `_values_for_argsort`, or either override `EA.argsort` with a custom implementation (which indeed means we can't rely on `_values_for_argsort` being usable directly). 
But so, then we can simply expand this implmentation note in the docs to: you can either implement `_values_for_argsort` (and then `argsort`, `argmin` and `argmax` provide a default implementation based on those values), or implement `argsort`, `argmin` and `argmax` yourself. I don't think that is any problem?

Now, what became apparent in the recent discussions regarding those `_values_for_argsort`, is that this original idea of "either implement `EA._values_for_argsort` or either override `EA.argsort`" in practice isn't followed anymore. We "broke" that since the original EA implementation while fixing some bugs last year, so this is something to be fleshed out -> https://github.com/pandas-dev/pandas/issues/27218 (and the last paragraph of https://github.com/pandas-dev/pandas/issues/33276#issuecomment-609023389). But if we can fix this at some point for argsort, we can at once fix it for argmax/argmin as well (as the fix will be the same, I assume). So I dont't think this "broken" part of the EA interface is a reason to not use `_values_for_argsort` for argmax/argmin.