ENH: Sorting of ExtensionArrays
State: closed

This enables {Series,DataFrame}.sort_values and {Series,DataFrame}.argsort. These are required for `factorize`, which is required for `groupby` (my end goal).

I haven't implemented `ExtensionArray.sort_values` yet because it hasn't become necessary. But I can if needed / desired.


Labels:
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff
name: ExtensionArray
description: Extending pandas with custom dtypes or arrays.

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/19957?src=pr&el=h1) Report
> Merging [#19957](https://codecov.io/gh/pandas-dev/pandas/pull/19957?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/7273ea0709590e6264607f227bb8def0ef656c50?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/19957/graphs/tree.svg?token=eZ4WkYLtcO&width=650&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/19957?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #19957      +/-   ##
==========================================
+ Coverage   91.77%   91.78%   +<.01%     
==========================================
  Files         152      152              
  Lines       49205    49223      +18     
==========================================
+ Hits        45159    45177      +18     
  Misses       4046     4046
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.16% <100%> (ø)` | :arrow_up: |
| #single | `41.84% <35.71%> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/19957?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2Jhc2UucHk=) | `83.33% <100%> (+2.68%)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `96.2% <100%> (-0.02%)` | :arrow_down: |
| [pandas/core/window.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvd2luZG93LnB5) | `96.26% <0%> (-0.01%)` | :arrow_down: |
| [pandas/plotting/\_core.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL19jb3JlLnB5) | `82.27% <0%> (ø)` | :arrow_up: |
| [pandas/io/json/normalize.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vbm9ybWFsaXplLnB5) | `96.93% <0%> (+0.06%)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/19957/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `84.11% <0%> (+0.16%)` | :arrow_up: |

------

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

Changed how this is organized a bit, to reflect a pattern I noticed here an elsewhere.

In several places (here, factorize, unique), a method like `.argsort` is composed of three parts

1.) Data coercion / prep
2.) The actual algorithm
3.) postprocessing

In the case of argsort, it's

1.) Just the array for most types, the codes for `Categorical`
2.) `np.argsort`
3.) Maybe reversiong for ascending=False

So I split the method in two `EA.argsort` and `EA._values_for_argsort`. For the common case of "I just want to pick which array gets sent to the algo", you just have to overrride `_values_for_argort`. If you need total control (e.g. if you aren't using `np.argsort` to do the actual work), then you'll need to override `EA.argsort` and do everything.

I don't know how useful this will prove to be, but wanted to hear other's thoughts.
Do you foresee similar patterns for other algos? Like `_values_for_factorize` (not sure if that makes sense). Just to think about if we would get a proliferation of such methods
Yes factorize would be another. Though it would be a bit more complicated.

I'll probably remove it for now. That means a bit more duplication, but
fewer levels of indirection.

On Fri, Mar 2, 2018 at 10:13 AM, Joris Van den Bossche <
notifications@github.com> wrote:

> Do you foresee similar patterns for other algos? Like
> _values_for_factorize (not sure if that makes sense). Just to think about
> if we would get a proliferation of such methods
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/19957#issuecomment-369967861>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIsdiBiJkXrc6AUBR5y_d0GnEojQBks5taW9igaJpZM4SY-A0>
> .
>

What is the use-case for writing your own sorting algorithm? Maybe radix sort when your data falls into pre-known categories?

My inclination would be to only cinlude `_values_for_argsort`, since that means minimal work for extension array authors.
> my inclination would be to only cinlude _values_for_argsort

Do you mean not having an `argsort` method then? From pandas point of view, having `argsort`, as we don't have to check the array time in `sort_values`, and other places where we use `arr.argsort`.
The linting failure is fixed in https://github.com/pandas-dev/pandas/pull/20330


Hmm I don't know. What about when you need a slightly different integer
mapping for values?
We already have that for Categorical, as _codes_for_groupby is
inappropriate for _values_for_argsort.

This is trying to avoid the whole "which .values is this?" issue by being
clear what it's used for. With this name, it's
very clear.

From a library author's point of view, *if* we have several of these "give
me a simple array to operate on" that can be shared by the implementation,
it's
as simple as

```
_codes_for_groupby = _values_for_argsort = _as_simple_array
```

And if they can't share an implementation (like Categorical) it's clear
which one is useful in which situation.



On Wed, Mar 14, 2018 at 6:06 AM, Jeff Reback <notifications@github.com>
wrote:

> *@jreback* commented on this pull request.
> ------------------------------
>
> In pandas/core/arrays/base.py
> <https://github.com/pandas-dev/pandas/pull/19957#discussion_r174422842>:
>
> > @@ -236,6 +237,52 @@ def isna(self):
>          """
>          raise AbstractMethodError(self)
>
> +    def _values_for_argsort(self):
> +        # type: () -> ndarray
> +        """Get the ndarray to be passed to np.argsort.
>
> ok, so then let's pick a name change _codes_for_groupby. in this refactor
> we want to find other usecases and fix our code now rather than later.
>
> something like: _int_mapping_for_values
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/19957#discussion_r174422842>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIvNp2eeHf6sGbl9qCymHC3b2JzBiks5tePmtgaJpZM4SY-A0>
> .
>

@jreback are you -1 on `_values_for_argsort`, or just -0? I believe the rest of us are +1.
i am -1 in this

it seems that EA is adding a bunch of things that we don’t know are really necessary or very specifically named

i would defer adding this or make it general purpose

this API has to be as simple as possible but it is exploding in size and complexity 
> i would defer adding this or make it general purpose

I'm not sure if that's possible. We already have two cases that can't be satisfied by a simple array.

> this API has to be as simple as possible but it is exploding in size and complexity

The purpose of `_values_for_argsort` is to make it *easier* to implement `argsort` correctly. Just pass a simple array of codes if you have one (which is true for Categorical, Period, Interval, and IPArray). We need `argsort` to support groupby, which is certainly worth supporting. I think the *marginal* complexity of `_values_for_argsort` is negative. If you can't use it, then you just override `argsort` normally. If you can use it, then your job is easier.
@jreback Do you have an alternative solution? Or just not having it?

As Tom said, not having this would mean duplicating the implementation of `argsort` in `Categorical`, `Period`, `Interval` (and external extension arrays). That's certainly not ideal as well.

It is difficult to exactly know how things will turn out (whether we need to add a bunch of those `_values_for_...` methods or not, whether we can reuse this `_values_for_argsort` for other purposes or not (eg groupby or factorize), if we would need to add a constructor method for roundtripping it, ...). But it will only by actually trying to fully implement ExtensionArray and all our own arrays types (period, interval) that we will find out. 
Therefore, I personally think it is better to move forward, let's implement all those things, and when doing that, constantly re-evaluate if things can be re-used, simplified, ..
I think it would be worthwile to convert datetime w/tz to a first class extension type before proceeding with more changes. The issue is have is we are looking at a very narrow case, categorical, so its pretty hard to tell if something is generally needed/useful, or is something specific to an extension type. The types that are added (decimal/json) are not battle tested and don't have nearly the sophistication and internal usage as do categorical and datetime w/tz.

I'm close to having groupby done. I'd prefer to finish that first before starting on another type.
FYI @jbrockmendel has started on DatetimeArray in https://github.com/pandas-dev/pandas/pull/19902 (will review today, sorry).
needs a rebase. my point from above is also that the idea of mapping an EA to integers (which are meaningful) is generally useful, essentially what you have for ``_values_for_argsort`` is pretty much factorize. so maybe make this explicit, e.g. ``_factorized_values`` or something like this. (and depending on the array you *may* want to cache this).
The name "factorized_values" takes on pandas' factorization semantics
around types and ordering.

We can't respect the types because we don't have a good way of getting
integers (yet, and even if we did that may be expensive).
We can't respect the ordering rules (where order of appearance matters)
because that would break sorting.

What are all the properties we need, and what's a good name to summarize
those? Hard to say in the abstract.

For sorting, we need to preserve ordering and have each value be distinct.
In other words, a strictly monotonic function:
https://en.wikipedia.org/wiki/Monotonic_function.

On Fri, Mar 16, 2018 at 4:59 PM, Jeff Reback <notifications@github.com>
wrote:

> needs a rebase. my point from above is also that the idea of mapping an EA
> to integers (which are meaningful) is generally useful, essentially what
> you have for _values_for_argsort is pretty much factorize. so maybe make
> this explicit, e.g. _factorized_values or something like this. (and
> depending on the array you *may* want to cache this).
>
> —
> You are receiving this because you authored the thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/19957#issuecomment-373856329>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIhKMj4FpmwdZOW-8N0Lp6odnyojFks5tfDW8gaJpZM4SY-A0>
> .
>

Updated the name to `_simple_ndarray`, and documented the strict monotonicity requirement. I think monotonicity is a good compromise between being useful enough for a broad class of tasks, while being specific enough to be easy to implement.
I'm not tied to the name `_simple_ndarray`, other than

- I don't want to mention a type like integer (not all EAs can be easily converted to integers)
- I'd like to have `ndarary` in the name
@shoyer @jorisvandenbossche any thoughts on the name? Does strict monotonicity seem like a good requirement for this type of thing? It covers our current use-cases well I think (Categorical, Period, Interval, IPArray, datetime w/ TZ)
> It covers our current use-cases well I think

But only for sorting? Or do you see other use-cases?

If it is only for sorting, I still think including that notion in the name is better / more explicit (for now).

> [jreback] what you have for _values_for_argsort is pretty much factorize. so maybe make this explicit, e.g. _factorized_values or something like this.

I was also thinking about this at a certain point, in light of geopandas. For geopandas, I could convert the geometries in a meaningful *physical* array by converting it a (well-known) binary representation. And using this array, I could do a `factorize` step. So somehow, having a `_factorize_values` which is then used by a default implementation of `argsort` and `factorize` would make it easier for geopandas. 
However, the problem with such `_factorize_values` is that they then need to be roundtrippable, you need to convert the unique physical array back to actual ExtensionArray. In the above case of geopandas, that is possible, but I don't think that is something we can assume in general.


> However, the problem with such _factorize_values is that they then need to be roundtrippable

Indeed, though with a caveat, they need to be round-trippable *when combined with the original array*.

Using `PeriodIndex` as an example, we have the ordinals.

```python
In [25]: p = pd.period_range('2017', periods=4)

In [26]: labels, uniques = pd.factorize(p._ndarray_values)

In [27]: pd.PeriodIndex._from_ordinals(y, freq=p.freq)
Out[27]: PeriodIndex(['2017-01-01', '2017-01-02', '2017-01-03', '2017-01-04'], dtype='period[D]', freq='D')
```

So we would have to expand the API to include a new constructor `_from_simple_ndarray` or something like that. Is that an unreasonable burden? Keep in mind that the default implementation for the simple ndarray will still be `.astype(object)`, and the simple constructor can be aliased to `_from_scalars`, or whatever we called it.

At this point though, we're straying a bit far afield from the original purpose of this PR.
And, in case it wasn't clear, `.argsort` doesn't need the new constructor since we aren't reconstructing an EA from the transformed values.
So here's my current proposal.

```python
    @classmethod
    def _from_simple_ndarray(self, values, similar):
        raise AbstractMethodError

    def _as_simple_ndarray(self):
        # type: () -> ndarray
        """Convert the array to a simple ndarray representaiton.

        Requirements:

        * strictly monotonic
          For every i, j index in `self`, if `self[i] < self[j]` then
          ``self._as_simple_ndarray()[i] < self._as_simple_ndarray()[j])``.
          Likewise for equality.
        * Invertable, when combined with another instance of this object
          For r = ``self._as_simple_ndarray()``,
              ``(self == self._from_simple_ndarray(r)).all()``

        """
        # Implemnetor note: This method is currently used in
        # - ExtensionArray.argsort

        return np.array(self)
```

(edit: hit return too early).

The name / semantics the second argument to `_from_simple_ndarray` is tricky. It's not necessarily the original. In the case of `factorize`, it'll be the unique values, a subset of `original`.

If you use the default impl of `._as_simple_ndarray`, casting to object, then you can define `_from_simple_ndarray` as `return cls._constructor_from_sequence(values)`, since you have a sequence of your scalar type.
I'm pretty sure factorize can't handle arbitrary dtypes -- we only have hashtables for handful of builtin types (e.g., int64, float64, object, maybe uint64 if I recall correctly). So it seems quite likely that we will need different arrays for factorization and sorting (e.g., for IPAddress, which can return a structured array for sorting and an object array for hashing). In other cases (geopandas?) sorting might not even be well defined.

I don't like the name `_as_simple_ndarray`. It's too vague, and will both confuse users and tempt us (pandas devs) to add additional functionality/requirements to the method.

I actually like defining separate special methods such as `_ndarray_for_argsort` and `_ndarray_for_factorize`,  along with complementary constructors as necessary, e.g., `_from_factorized`. Here's why:
- The name of the methods makes it obvious (both to us and users) what properties the returned values should satisfy.
- We can define separate methods as necessary if there is any conceivable difference in use-cases. It's much easier to consolidate methods later than to split them later.
- I don't think the list of special methods like this that we will need will be very long.

Finally, for the record I'm still not a fan of putting *implementations* like the `argsort()` method on ExtensionArray. I think this is unnecessary and will make the interface more confusing. Ideally ExtensionArray should be entirely abstract.
> So it seems quite likely that we will need different arrays for factorization and sorting

Ah, yes. That is indeed the case for IPArray...

> Finally, for the record I'm still not a fan of putting implementations like the argsort() method on ExtensionArray.

What's the alternative? An internal helper in pandas like `argsort_array`?
I haven't formed an opinion on _values_for_argsort, but _conditional_ on it being needed, I'm +1 on it being kept out of the DataFrame/Series/Index namespace.

Is there an implicit assumption that EAs are always 1D?
> Is there an implicit assumption that EAs are always 1D?

At the moment, we've explicitly documented them to be 1D only.
> Finally, for the record I'm still not a fan of putting implementations like the argsort() method on ExtensionArray. I think this is unnecessary and will make the interface more confusing. Ideally ExtensionArray should be entirely abstract.

@shoyer would you then propose to have a full abstract class, and separate a partially filled in base extension array people can subclass? 
As having this "partially implemented" class to subclass is certainly useful to avoid repetition for extension authors.
Updated https://github.com/pandas-dev/pandas/pull/20361 with an example of what `_factorize` looks like using a similar approach (`_values_for_factorize` and a method reconstructing).