REF/BUG/API: factorizing categorical data
State: closed

This changes / fixes how Categorical data are factorized. The return value of a
factorized categorical is now `Tuple[ndarray[int], Categorical]`.

Before

```python
In [2]: l, u = pd.factorize(pd.Categorical(['a', 'a', 'b']))

In [3]: l
Out[3]: array([0, 0, 1])

In [4]: u
Out[4]: array([0, 1])
```

after

```python
In [2]: l, u = pd.factorize(pd.Categorical(['a', 'a', 'b']))

In [3]: l
Out[3]: array([0, 0, 1])

In [4]: u
Out[4]:
[a, b]
Categories (2, object): [a, b]
```

The implementation is similar to `.unique`.

1. The algo (`pd.factorize`, `pd.unique`) handles unboxing / dtype coercion
2. The algo dispatches the actual array factorization for extension types
3. The algo boxes the output if necessary, depending on the input.

I've implemented this as a new public method on ``Categorical``, mainly since
this is what we do for unique, and I think it's a useful method to have.

This fixes a bug in factorizing categoricals with missing values. Previously, we
included -1 in the uniques.

Before

```python
In [2]: l, u = pd.factorize(pd.Categorical(['a', 'a', 'b', None]))

In [3]: u
Out[3]: array([ 0,  1, -1])
```

After

```python
In [2]: l, u = pd.factorize(pd.Categorical(['a', 'a', 'b', None]))

In [3]: u
Out[3]:
[a, b]
Categories (2, object): [a, b]
```

xref #19721. This doesn't close it, as I haven't addressed the issue of what `factorize(Series[EA])` should return. Just fixing the categorical bugs.

Labels:
name: Missing-data
description: np.nan, pd.NaT, pd.NA, dropna, isnull, interpolate
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff
name: Categorical
description: Categorical Data Type

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

```diff
@@            Coverage Diff             @@
##           master   #19938      +/-   ##
==========================================
+ Coverage   91.77%   91.78%   +<.01%     
==========================================
  Files         152      152              
  Lines       49185    49206      +21     
==========================================
+ Hits        45140    45163      +23     
+ Misses       4045     4043       -2
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.16% <100%> (ø)` | :arrow_up: |
| #single | `41.83% <62.5%> (-0.02%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/19938?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/19938/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.29% <100%> (+0.12%)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/19938/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.11% <100%> (+0.05%)` | :arrow_up: |
| [pandas/util/testing.py](https://codecov.io/gh/pandas-dev/pandas/pull/19938/diff?src=pr&el=tree#diff-cGFuZGFzL3V0aWwvdGVzdGluZy5weQ==) | `83.95% <0%> (+0.2%)` | :arrow_up: |

------

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

can you show what exactly is the 'bug' here?
> can you show what exactly is the 'bug' here?

Did you see Tom's top level post with 'before' and 'after' ? (and the discussion in https://github.com/pandas-dev/pandas/issues/19721)
ok I see the rationale behind this, which is ok. still some question regarding the impl. this looks like a bit of a work around.
Fixed the bug in my logic from the last commit.

ASV looks good. The first time I ran it I had a 1.20 ratio (slowdown) relative to master on `algorithms.Factorize.time_factorize_int(True)`. 0.8 ratio (speedup) the second time. No change 3rd time.
@jorisvandenbossche just confirming, but I assume we don't want to add `Categorical.factorize` to the API docs?
> @jorisvandenbossche just confirming, but I assume we don't want to add Categorical.factorize to the API docs?

That maybe depends on the discussion we will have on that for ExtensionArray?
ahh I see we are already exposing factorize on ``Series``. ok, then this should be a part of the EA interface. (can be separate PR).

otherwise this ok? can you rebase
Yeah, this should be good to go.
thanks @TomAugspurger