PERF: __contains__ method for Categorical
State: closed

Calling `key in Categorical(...)` trivially falls back to calling `__iter__` and then forces a full construction of the array by invoking `get_values`. 
This implementation is faster in best case situations than using .e.g.`any(Categorical.isin(key))` since we do not care about the complete array. Not sure if I need to handle any edge cases, though.

This obviously can't reach the performance of a simple Index but is a bit faster than before

before:
```
· Discovering benchmarks
· Running 1 total benchmarks (1 commits * 1 environments * 1 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[100.00%] ··· Running categoricals.Slicing.time_loc_categorical                                         2.04ms
```
after
```
· Discovering benchmarks
· Running 1 total benchmarks (1 commits * 1 environments * 1 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[100.00%] ··· Running categoricals.Slicing.time_loc_categorical                                       852.58μs
```

- [x] closes #20395
- [x] benchmark added
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

cc @topper-123 

Labels:
name: Performance
description: Memory or execution speed performance
name: Categorical
description: Categorical Data Type

Comments:
Nice.

wrt #20395: Now I get test result of 4.1 ms as compared to 13.8 ms beforehand. So while this is much better, the test case of ``pd.Index`` is at 125 µs, so #20395 is not completely solved...
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21022?src=pr&el=h1) Report
> Merging [#21022](https://codecov.io/gh/pandas-dev/pandas/pull/21022?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/0c65c57a279e755ab7093db925d1e580f9878dae?src=pr&el=desc) will **increase** coverage by `0.04%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #21022      +/-   ##
==========================================
+ Coverage   91.85%   91.89%   +0.04%     
==========================================
  Files         153      153              
  Lines       49549    49585      +36     
==========================================
+ Hits        45512    45565      +53     
+ Misses       4037     4020      -17
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.29% <100%> (+0.04%)` | :arrow_up: |
| #single | `41.85% <16.66%> (-0.03%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21022?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.73% <100%> (+0.03%)` | :arrow_up: |
| [pandas/core/reshape/melt.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS9tZWx0LnB5) | `97.34% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexes/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZXMucHk=) | `95.8% <0%> (+0.02%)` | :arrow_up: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `94.17% <0%> (+0.05%)` | :arrow_up: |
| [pandas/core/reshape/pivot.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS9waXZvdC5weQ==) | `97.03% <0%> (+0.05%)` | :arrow_up: |
| [pandas/io/formats/style.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvc3R5bGUucHk=) | `96.12% <0%> (+0.08%)` | :arrow_up: |
| [pandas/core/dtypes/missing.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZHR5cGVzL21pc3NpbmcucHk=) | `92.52% <0%> (+0.57%)` | :arrow_up: |
| [pandas/plotting/\_core.py](https://codecov.io/gh/pandas-dev/pandas/pull/21022/diff?src=pr&el=tree#diff-cGFuZGFzL3Bsb3R0aW5nL19jb3JlLnB5) | `83.53% <0%> (+1.14%)` | :arrow_up: |

------

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

Your code was good, though use ``get_loc`` rather than ``get_indexer`` as this is faster.

A related improvement would be to look at ``CategoricalIndex.__contains__``. There the line 

```python
    return key in self.values
```
can be replaced with 

```python
        code_value = self.categories.get_loc(key)
        return code_value in self._engine
```

to gain some additional speedup when using ``CategoricalIndex`` rather than ``Categorical``:

```python
>>> n = 1_000_000
>>> c = pd.Categorical(list('a' * n + 'b' * n + 'c' * n))  # using get_loc
>>> %timeit 'b' in c
4.49 ms ± 12.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
>>> %timeit 'b' in ci
3,11 µs ± 19.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
```

Also in ``CategoricalIndex.contains`` you can replace ``return key in self.values`` with ``return key in self``.



Hey @fjetter, This is a very nice PR. Want to take this over the finishing line? I could make the CategoricalIndex case myself, if you want.
> , though use get_loc rather than get_indexer as this is faster.

General question, wouldn't simply `val in self.categories` not even be faster and simpler?
@jorisvandenbossche: in general that wouldn't work, as some categories might not be present in the ``Categorical``/``CategoricalIndex``...
> as some categories might not be present in the 

How is that possible? The only one I can think of is NA, so the check could be something like `val in self.categories or isna(val) and self.isna().any()` 
Maybe I wasn't communicating clearly, sorry about that. What I meant was this:

```python
>>> c = pd.CategoricalIndex('a a'.split(), categories='a b'.split())
>>> 'b' in c
False
>>< 'b' in c.categories
True
```

So to check for membership in categories can give different results than checking membership in the values. Was this not the question from @jorisvandenbossche, or did I misunderstand?
Oh, of course.

Though I wonder if checking `val in self.categories` is still worthwhile to get a quick no / maybe.
Ah yes, that's a good reason!
Exactly this reason actually is a bug in `CategoricalIndex.__contains__` for interval categories:

```
In [14]: intervals = pd.interval_range(1, 4)

In [15]: intervals
Out[15]: 
IntervalIndex([(1, 2], (2, 3], (3, 4]]
              closed='right',
              dtype='interval[int64]')

In [16]: cat = pd.CategoricalIndex(list(intervals[:-1]), categories=intervals)

In [17]: cat
Out[17]: CategoricalIndex([(1, 2], (2, 3]], categories=[(1, 2], (2, 3], (3, 4]], ordered=False, dtype='category')

In [18]: intervals[-1] in cat
Out[18]: True
```

Sorry, I've been swamped the past few weeks.

@TomAugspurger I extended the `CategoricalIndex` unit test and extended the benchmarks to cover all combinations you mentioned. Is there anything else you'd want to be covered?

@jorisvandenbossche Indeed this bug exists but I think it's unrelated to this PR. It's connected to the `_defer_to_indexing` attribute
see https://github.com/pandas-dev/pandas/blob/0c65c57a279e755ab7093db925d1e580f9878dae/pandas/core/indexes/category.py#L328
which appears to be only `True` for `IntervalIndex`. Unfortunately I have no idea what this is for and would suggest to fix this in another PR

@jreback You asked me to check whether there are similar benchmarks in `indexing.py` and I believe the short answer would be yes. However, most tests/benchmark for categorical related cases are in their own module which is why I put it there. I do not have a strong opinion about this topic and would move the code wherever you feel most appropriate

The currently implemented benchmarks show a speedup between ~2-1000 depending on the task we're looking at.


### BEFORE
```
~/workspace/pandas/asv_bench(performance/improve_contains_in_categorical*) » asv run --python=same --show-stderr --bench=categoricals.Indexing
· Discovering benchmarks
· Running 2 total benchmarks (1 commits * 1 environments * 2 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[ 50.00%] ··· Running categoricals.Indexing.time_loc_df                                                                                   ok
[ 50.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a      3.90±0.7ms   1.95±0.05ms
                  c     3.41±0.02ms    2.37±0.1ms
               ======= ============= =============

[100.00%] ··· Running categoricals.Indexing.time_loc_ser                                                                                  ok
[100.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a     2.43±0.05ms    3.15±0.5ms
                  c      2.85±0.1ms   2.91±0.05ms
               ======= ============= =============

------------------------------------------------------------
~/workspace/pandas/asv_bench(performance/improve_contains_in_categorical*) » asv run --python=same --show-stderr --bench=categoricals.Contains
· Discovering benchmarks
· Running 2 total benchmarks (1 commits * 1 environments * 2 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[ 50.00%] ··· Running categoricals.Contains.time_cat_isin                                                                                 ok
[ 50.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a     1.20±0.02ms   1.19±0.04ms
                  c     1.54±0.03ms   1.50±0.04ms
                  d     1.74±0.05ms   1.69±0.05ms
                  z     1.78±0.08ms   1.78±0.06ms
                 nan    1.19±0.01ms   1.84±0.04ms
               ======= ============= =============

[100.00%] ··· Running categoricals.Contains.time_contains_index                                                                           ok
[100.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a     1.21±0.05ms   1.20±0.02ms
                  c     1.54±0.02ms   1.64±0.09ms
                  d      1.83±0.3ms   1.76±0.04ms
                  z     1.72±0.05ms   1.71±0.05ms
                 nan    1.25±0.08ms   1.85±0.06ms
               ======= ============= =============
```

### AFTER
```
~/workspace/pandas/asv_bench(performance/improve_contains_in_categorical*) » asv run --python=same --show-stderr --bench=categoricals.Indexing
· Discovering benchmarks
· Running 2 total benchmarks (1 commits * 1 environments * 2 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[ 50.00%] ··· Running categoricals.Indexing.time_loc_df                                                                                   ok
[ 50.00%] ····
               ======= ============= ==========
               --              has_nan
               ------- ------------------------
                value       True       False
               ======= ============= ==========
                  a     1.86±0.04ms   734±20μs
                  c     1.75±0.01ms   634±20μs
               ======= ============= ==========

[100.00%] ··· Running categoricals.Indexing.time_loc_ser                                                                                  ok
[100.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a     1.25±0.07ms   1.36±0.08ms
                  c     1.30±0.07ms   1.38±0.07ms
               ======= ============= =============


~/workspace/pandas/asv_bench(performance/improve_contains_in_categorical*) » asv run --python=same --show-stderr --bench=categoricals.Contains
· Discovering benchmarks
· Running 2 total benchmarks (1 commits * 1 environments * 2 benchmarks)
[  0.00%] ·· Building for existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[  0.00%] ·· Benchmarking existing-py_Users_fjetter_miniconda2_envs_pandas-dev_bin_python
[ 50.00%] ··· Running categoricals.Contains.time_cat_isin                                                                                 ok
[ 50.00%] ····
               ======= ============= =============
               --                has_nan
               ------- ---------------------------
                value       True         False
               ======= ============= =============
                  a      15.2±0.4μs    15.1±0.1μs
                  c      16.5±0.3μs     15.7±2μs
                  d      17.8±0.8μs    16.3±0.5μs
                  z     1.96±0.07μs   1.98±0.02μs
                 nan     11.5±0.1μs    11.6±0.3μs
               ======= ============= =============

[100.00%] ··· Running categoricals.Contains.time_contains_index                                                                           ok
[100.00%] ····
               ======= ============= ============
               --               has_nan
               ------- --------------------------
                value       True        False
               ======= ============= ============
                  a      17.1±0.4μs   16.3±0.2μs
                  c      17.7±0.5μs   17.9±0.4μs
                  d      18.7±0.6μs   17.4±0.3μs
                  z     3.34±0.06μs   3.37±0.1μs
                 nan     14.3±0.2μs   13.3±0.5μs
               ======= ============= ============

```
Please compare my #21369 to your ``__contains__`` implementation.

My version is slightly different:

```python
    def __contains__(self, key):
        hash(key)
        if isna(key):
            return self.isna().any()
        elif self.categories._defer_to_indexing:  # e.g. Interval values
            loc = self.categories.get_loc(key)
            return np.isin(self.codes, loc).any()
        elif key in self.categories:
            return self.categories.get_loc(key) in self._engine
        else:
            return False
```

The ``isna`` section comes first to guard against passing nans to the ``elif self.categories._defer_to_indexing`` case.

In the ``elif self.categories._defer_to_indexing`` case, the key may be in several intervals, so ``loc`` may be an array. Therefor I used ``np.isin`` for the membership check.

The rest is like your version, except I use ``_engine``, which is what gives CategoricalIndex a nice speedup. Comments/reviews welcome.
since we merged @topper-123 other fix, can you confirm this (the correct fix should be in Categorical and CI can just call it)
@topper-123 Your version doesn't work since there is no `Categorical._engine`. The engine does only exist for the `CategoricalIndex`. I exchanged it with `self._codes`. The timing is basically the same as for my version but since you added the additional case for the `_defer_to_indexing` I took your version

@jreback Are you referring to #21025? Not sure how #21025 relates and I couldn't find any other merged PRs related to this. I assume you meant that the CategoricalIndex should just forward the call to the Categorical underneath. I removed any special cases in the `CategoricalIndex` and with the additional _if case_ @topper-123 suggested, the bug with the `IntervalIndex` is now also fixed. I believe this is what #21369 is doing, isn't it? I'd hate to _compete_ with another PR. If there are any major issues left and @topper-123 is willing to take care of it, I'll gladly step back since I wouldn't want this PR to blow up any further
Tests seem to break because `np.isin` was only introduced in rather recent numpy versions but CI tests also up to `1.10` where this doesn't exist. Can someone explain to me what the flag `_defer_to_indexing` is for and why we even require special treatment in this case?
@fjetter , Sorry about that, I was also confused by the ``_defer_to_indexing``. I looked more into it and the underlying issue is that ``self.categories.get_loc`` may return a array, if ``self.categories`` is a ``IntervalIndex``.

So I suggest doing this, whích also avoids special-casing Intervals.

```python
    def __contains__(self, key):
        hash(key)
        if isna(key):
            return self.isna().any()
        try:
            loc = self.categories.get_loc(key)
        except KeyError:
            return False
        if is_scalar(loc):
            return loc in self._codes
        else:  # if self.categories is IntervalIndex, loc is an array
            return any(loc_ in self._codes for loc_ in loc)
```

EDIT: An example where ``self.categories.get_loc`` returns an array:

```python
>>> ii = pd.IntervalIndex.from_arrays((0,0,0), (1,1,2))
>>> c = pd.Categorical(ii)
>>> c.categories.get_loc(1)
array([0, 1], dtype=int64)
```
Hi @fjetter, I’ve gotten merged #21369, which is very similar to your PR. You only need to replace my  self._engine with self.codes in yout PR, and your code should work.

Want to take it the last few steps? Otherwise I can take this, it’s not much work remaining.
closing in favor of #21508