PERF: add method Categorical.__contains__
State: closed

- [x] closes #21022 
- [x] xref #21369
- [x] tests added / passed
- [x] benchmark added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

Currently, membership checks in ``Categorical`` is very slow as explained by @fjetter in #21022. This PR fixes the issue. See also #21369 which fixed the similar issue for ``CategoricalIndex``.

Tests didn't exist beforehand and have been added.

ASV:

```
      before           after         ratio
     [9e982e18]       [28461f0c]
-      4.26±0.7ms         134±20μs     0.03  categoricals.Contains.time_categorical_contains

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
```

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

Comments:
Hello @topper-123! Thanks for updating the PR.









Cheers ! There are no PEP8 issues in this Pull Request. :beers: 

##### Comment last updated on June 20, 2018 at 10:29 Hours UTC
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21508?src=pr&el=h1) Report
> Merging [#21508](https://codecov.io/gh/pandas-dev/pandas/pull/21508?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/2625759abeb78655558067d55a23c293628c3165?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `93.75%`.

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

```diff
@@            Coverage Diff             @@
##           master   #21508      +/-   ##
==========================================
+ Coverage   91.91%   91.92%   +<.01%     
==========================================
  Files         153      153              
  Lines       49546    49572      +26     
==========================================
+ Hits        45542    45568      +26     
  Misses       4004     4004
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.32% <93.75%> (ø)` | :arrow_up: |
| #single | `41.8% <18.75%> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21508?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/21508/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9jYXRlZ29yeS5weQ==) | `97.28% <100%> (+0.18%)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/21508/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.63% <92.3%> (-0.06%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/21508/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.23% <0%> (ø)` | :arrow_up: |
| [pandas/core/generic.py](https://codecov.io/gh/pandas-dev/pandas/pull/21508/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZ2VuZXJpYy5weQ==) | `96.12% <0%> (ø)` | :arrow_up: |
| [pandas/core/indexing.py](https://codecov.io/gh/pandas-dev/pandas/pull/21508/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhpbmcucHk=) | `93.55% <0%> (+0.14%)` | :arrow_up: |

------

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

@topper-123 : A bunch of nit-picking things, but overall, this looks pretty good!
Comments addressed.
Ok, won't hold you up to that approval, fixed :-)
@jreback , using ``._data`` would be slower, as it doesn't use the hashed value in ``._engine``:

```python
>>> n = 100_000
>>> ci = pd.CategoricalIndex(list('a'*n +'a' + 'b'*n + 'c'*n))
>>> %timeit ci.categories.get_loc('b') in ci._engine
1.6 µs ± 28.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit 'b' in ci._data
183 µs ± 9.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
```

So there needs to be different implementations.
@jorisvandenbossche, to my understanding these modules are themselves private and it’s not necessary for functions in private modules to be marked as private - that would be superfluous.

When it was a method on Categorical, it *was* needed to mark it private, as Categorical is a public class.
The Travis error is an HTTP error:

```
CondaHTTPError: HTTP 000 CONNECTION FAILED for url <https://repo.anaconda.com/pkgs/main/linux-64/qt-5.9.5-h7e424d6_0.tar.bz2>
Elapsed: -
An HTTP error occurred when trying to retrieve this URL.
HTTP errors are often intermittent, and a simple retry will get you on your way.
real	3m14.046s
user	1m7.620s
sys	0m3.084s
The command "ci/install_travis.sh" failed and exited with 1 during .
Your build has been stopped.
```

so the Travis failure has nothing to do with this PR.
> @jorisvandenbossche, to my understanding these modules are themselves private and it’s not necessary for functions in private modules to be marked as private - that would be superfluous.

@topper-123 whoops, sorry, only looked very briefly at the incremental diff and missed that it was a function and not a method. 
thanks @topper-123