PERF: GH2003 Series.isin for categorical dtypes
State: closed

I have added a branching for the categorical case in `Series.isin` function.
I have also added a test for the most crucial cases (nans).
closes #20003 

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

Comments:
> I'd prefer to move your categorical isin logic to a new method Categorical.isin.

To be a bit clearer about this. I'd imagine the `Categorical.isin` method doing the codes and categories stuff, to see which codes the items in `values` would map to. Then calling `algorithms.value_counts(codes, code_values)`, where `code_values` is the code that each value maps to (if any).
@TomAugspurger Why do I need to call `algorithms.value_counts(codes, code_values)` in `Categorical.isin`? Do you mean `algorithms.isin`?
Sorry, I meant `isin` :)

On Wed, Mar 28, 2018 at 5:30 PM, Artem Bogachev <notifications@github.com>
wrote:

> @TomAugspurger <https://github.com/TomAugspurger> Why do I need to call algorithms.value_counts(codes,
> code_values) in Categorical.isin
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/20522#issuecomment-377059341>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIhSHMMtDX_sbWG8bTcnhm9cg6tDVks5tjA8SgaJpZM4S_K1T>
> .
>

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

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

```diff
@@            Coverage Diff             @@
##           master   #20522      +/-   ##
==========================================
+ Coverage   91.77%   91.77%   +<.01%     
==========================================
  Files         153      153              
  Lines       49257    49270      +13     
==========================================
+ Hits        45207    45220      +13     
  Misses       4050     4050
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.17% <93.33%> (ø)` | :arrow_up: |
| #single | `41.89% <93.33%> (+0.01%)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/20522?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/algorithms.py](https://codecov.io/gh/pandas-dev/pandas/pull/20522/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYWxnb3JpdGhtcy5weQ==) | `94.39% <100%> (+0.02%)` | :arrow_up: |
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/20522/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `96.63% <100%> (ø)` | :arrow_up: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/20522/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `93.99% <100%> (+0.09%)` | :arrow_up: |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/20522/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.7% <90%> (-0.08%)` | :arrow_down: |

------

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

@TomAugspurger I have moved the logic to `Categorical.isin`. But I still need to do more careful handling of `values` argument of that function. What are the possible argument types that can be used in `Series.isin` for example? Is using `_sanitize_array` enough to cover all basic cases?

And I cannot understand why checks on CircleCI have failed. The same tests on my laptop are passing. 
And I think my changes do not affect JSON parsing 😄 .
Merged in master. That'll hopefully fix the circleCI failure.
@ma3axaka did you run the ASV benchmarks? Or just a simple `%timeit` before / after? How does the performance look?
> What are the possible argument types that can be used in Series.isin for example?

It looks like it can be just about anything.  Did you run into issues without using `_sanitize_array`?
Yep. I have run the `asv` benchmark. I got the positive result. Do I need to post them here?
Sure (just the new one). I'm curious to see the performance improvement.

On Mon, Apr 2, 2018 at 4:50 PM, Artem Bogachev <notifications@github.com>
wrote:

> Yep. I have run the asv benchmark. I got the positive result. Do I need
> to post them here?
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/20522#issuecomment-378057577>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIvItwyqche6UatcRKiPvpfFxiyIPks5tkp0JgaJpZM4S_K1T>
> .
>

Can you also add a release note (doc/source/whatsnew/v0.23.0.txt) noting the performance improvement? Make sure to pull my commit first.
I've already added the line about the performance improvement to `whatsnew`. Do I need to add another one?
Sorry, missed that. 
That's what I got on my laptop from `asv`:
```
       before           after         ratio
     [fac2ef1b]       [d6c39534]
-         230±6ms      17.6±0.01ms     0.08  categoricals.IsIn.time_isin_categorical_strings
```
@jreback Changed the condition to `hasattr`
Sorry, I just noticed an issue. You've made the changes in `Series.isin`, so that the performance boost won't apply to other cases, most notably `CategoricalIndex.isin`.

We have a couple ways to proceed. IMO, I think it's best for the container classes `Series.isin` and `Index.isin` to be as simple as possible. Really just calling `algos.isin(self, values)` *without coercing the data.*

In `algos.isin` we'll unbox the series / index to get the underlying array (numpy array or categorical).

If we find a Categorical, we dispatch to `Categorical.isin`, which extracts the codes, and calls algos.isin again with the codes. Just like you've done.

So the order would be Series.isin -> algos.isin(categorical) -> Categorical.isin -> algos.isin(categorical).

In terms of code changes, it'll be

1. Ensure that `algos.isin` dispatches to `Categorical.isin`
2. Ensure that `algos.isin` does the `_values_from_object` stuff that's currently in `Series.isin` and `Index.isin`. (I think it's already doing that in `ensure_data`, so we may have been doing it twice originally.


Does that make sense? 
Yes. It makes sense. I will try to refactor it the way you've proposed.
If you're feeling ambitious, you can make a shared doc between algorithms.isin & Categorical.isin (see factorize).
@TomAugspurger I cannot reproduce CI errors locally. What is the best way to proceed here?
Something strange with Py2.

```python
(Pdb) code_values[null_mask | (code_values >= 0)]
array([1, 1])
```

The reason is that `null_mask` is boolean series, since `values` was a `Categorical` (same would happen with a Series).

```python
(Pdb) null_mask
0    False
1    False
dtype: bool
```

Casting it to an array seems to help

```python
(Pdb) code_values[np.asarray(null_mask) | (code_values >= 0)]
array([0, 1])
```

Are you able to setup a python2 environment to test locally?
I would prefer to convert `values` to `ndarray` before this logic. Is there any function I could use to safely do it?
use np.asarray as
tom suggests
Hello @ma3axaka! Thanks for updating the PR.













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

##### Comment last updated on April 25, 2018 at 10:02 Hours UTC
@TomAugspurger @jreback I have added the docs and fixed the problem with Python 2 (thanks to @TomAugspurger). Is there something else to be done?
@jreback I have renamed the benchmark class and a reference to the issue. Switching to `is_extension_type` doesn't work. It fails on `SparseArray` for example the class doesn't have `isin` method. I am assuming implementing these methods is the goal of #20617?
@jreback I've made requested changes except moving tests to a different file (see comments). But the Travis CI build is failing with an S3 error.
@jreback There are still errors with S3. Is this OK?
I'm looking into the s3 / moto issues today. Things should be OK on your
end.

On Wed, Apr 18, 2018 at 8:10 AM, Artem Bogachev <notifications@github.com>
wrote:

> @jreback <https://github.com/jreback> There are still errors with S3. Is
> this OK?
>
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub
> <https://github.com/pandas-dev/pandas/pull/20522#issuecomment-382380778>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABQHIol8ciUhkCI4qEyopTCeyK5eakb2ks5tpztDgaJpZM4S_K1T>
> .
>

@TomAugspurger Hi. Did you fix the issue with S3? Is there something left to do before merging the. ranch?
@ma3axaka can you rebase