PERF: Add __contains__ to CategoricalIndex
State: closed

- [x] progress towards #20395
- [x] xref #21022
- [ ] tests added / passed
- [x] benchmark added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Currently, membership checks in ``CategoricalIndex`` is very slow as explained in #21022. This PR fixes the issue for ``CategoricalIndex``, while #21022 contains the fix for ``Categorical``. The difference between the two cases is the use of ``_engine`` for ``CategoricalIndex``, which makes this even faster than the ``Catagorical`` solution in #21022.

Tests exist already and can be found in ``tests/indexes/test_category.py::TestCategoricalIndex::test_contains``.

ASV:

```
      before           after         ratio
     [0c65c57a]       [986779ab]
-      2.49±0.2ms       3.26±0.2μs     0.00  categoricals.Contains.time_contains

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Performance
description: Memory or execution speed performance
name: Categorical
description: Categorical Data Type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21369?src=pr&el=h1) Report
> Merging [#21369](https://codecov.io/gh/pandas-dev/pandas/pull/21369?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/576d5c6b76e039a411a7cc4c0de29813e2de0149?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `90%`.

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

```diff
@@            Coverage Diff             @@
##           master   #21369      +/-   ##
==========================================
+ Coverage    91.9%    91.9%   +<.01%     
==========================================
  Files         153      153              
  Lines       49606    49610       +4     
==========================================
+ Hits        45589    45593       +4     
  Misses       4017     4017
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.3% <90%> (ø)` | :arrow_up: |
| #single | `41.89% <0%> (-0.01%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21369?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/21369/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9jYXRlZ29yeS5weQ==) | `97.09% <90%> (+0.03%)` | :arrow_up: |

------

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

I've updated the PR.

I've set it to be part of 0.23.2, if that's alright.
thanks @topper-123 
This is changing the implementation quite substantially, so let's move this to 0.24.0.txt? 

Any comments on my comment above about keeping this for 0.24.0 ?
Quility-wise this is ok to go into 23.2 IMO, the PRs are really not that complex, IMO, it's much faster and it doesn't change any APIs.

Also, my main motivation for writing this was speeding up slicing dataframes with a CategoricalIndex (see #20395), which previously was *very* slow (still is slow, but better than before, and now faster than fancy indexing, at least). I think a lot of people will appreciate this speedup.
we tagged for 0.23.2 (and note is there)
it would be slightly tricky to change as there is another related change - both in 0.23.2 or 0.24
either way is fine 
The main reason that I am raising this is that `__contains__` checking has quite some implications (which is of course also the reason you speeded it up!), and I think it is rather easy to miss a small exotic corner case where the new implementation might differ. 
To be clear, @topper-123 , I am not questioning the quality of this PR! I just know from experience, also for us, that it is easy to miss an unintended API change (which we might not even decide to fix if it is debateble behaviour, but then that is still better to be left as 0.24.0). Since this is only about performance improvement (and not a regression), I would play on safe and give it more time in 0.24.0.


>  it would be slightly tricky to change as there is another related change - both in 0.23.2 or 0.24

Yep, it would be both in 0.23.2 or both in 0.24.0 (the other I actually tagged first as 0.24.0, but that was changed before merging)
Ok, your call, I won't object.
OK, left it for 0.24 (moved the whatsnew already to v0.24.0.txt)