Repository: pandas-dev/pandas
Pull request: PERF: GH2003 Series.isin for categorical dtypes
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 

Problem statement:
PERF: isin() is slower for categorical data than for integers
#### Problem description

For long series and many categories 'Series.isin()' is slower for `categorical` data rather than for `int64`. If categories are built from strings, then the degradation of the performance is even larger.

```python
import pandas as pd
import numpy as np

N = 3000000
Ncats = 100

cats = pd.Series(['abcdef%d'%_ for _ in range(Ncats)])

df = pd.DataFrame({'A': np.random.randn(N),
                   'B': np.random.randn(N),
                   'C': np.random.randint(0, Ncats, N),
                  })
df['D'] = cats.loc[df['C'].values].values
df['E'] = df['C'].astype('category')
df['F'] = df['D'].astype('category')

sel_codes = [1,2]
sel_cats = cats.loc[sel_codes].values

%timeit inds = df.C.isin(sel_codes)  # int64
%timeit inds = df.E.isin(sel_codes)  # category based on int64
%timeit inds = df.D.isin(sel_cats)  # object / string
%timeit inds = df.F.isin(sel_cats)  # category based on string
```
On my machine:
```
6.25 ms ± 412 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
28.7 ms ± 2.37 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
104 ms ± 4.67 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
142 ms ± 6.88 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

Interestingly, if there're many categories to compare with, categorical data is faster, e.g. for
```python
sel_codes = range(90)
sel_cats = cats.loc[sel_codes].values

%timeit inds = df.C.isin(sel_codes)  # int64
%timeit inds = df.E.isin(sel_codes)  # category based on int64
%timeit inds = df.D.isin(sel_cats)  # object / string
%timeit inds = df.F.isin(sel_cats)  # category based on string
```
the timings are:
```
441 ms ± 61 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
422 ms ± 68.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
147 ms ± 7.95 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
171 ms ± 2.39 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

p.s. I'm not sure if such performance issues are worth filing.

#### Output of ``pd.show_versions()``

<details>


INSTALLED VERSIONS
------------------
commit: None
python: 3.6.4.final.0
python-bits: 64
OS: Darwin
OS-release: 17.4.0
machine: x86_64
processor: i386
byteorder: little
LC_ALL: en_US.UTF-8
LANG: en_US.UTF-8
LOCALE: en_US.UTF-8

pandas: 0.22.0
pytest: None
pip: 9.0.1
setuptools: 28.8.0
Cython: 0.27.3
numpy: 1.14.0
scipy: 1.0.0
pyarrow: 0.7.1
xarray: None
IPython: 6.2.1
sphinx: None
patsy: 0.4.1
dateutil: 2.6.1
pytz: 2017.3
blosc: None
bottleneck: 1.2.1
tables: 3.4.2
numexpr: 2.6.4
feather: 0.4.0
matplotlib: 2.1.0
openpyxl: None
xlrd: None
xlwt: 1.3.0
xlsxwriter: None
lxml: None
bs4: 4.6.0
html5lib: 1.0b10
sqlalchemy: 1.1.15
pymysql: None
psycopg2: None
jinja2: 2.10
s3fs: None
fastparquet: None
pandas_gbq: None
pandas_datareader: None

</details>

Hints from issue discussion:
Thanks for the report, these are absolutely worth filing.

In this case we'll want to get the index position of `values` in the categorical categories (`get_indexer` should do the trick), pass the codes to algos.isin. Will just have to be careful with missing values, which will both be -1 by default.
I'm looking at this issue.

Commit message: refactor benchmark name and add reference to issue

Patch to review:
diff --git a/asv_bench/benchmarks/categoricals.py b/asv_bench/benchmarks/categoricals.py
index 7743921003353..1889830ee17d4 100644
--- a/asv_bench/benchmarks/categoricals.py
+++ b/asv_bench/benchmarks/categoricals.py
@@ -148,3 +148,18 @@ def time_rank_int_cat(self):
 
     def time_rank_int_cat_ordered(self):
         self.s_int_cat_ordered.rank()
+
+
+class Isin(object):
+
+    goal_time = 0.2
+
+    def setup(self):
+        n = 5 * 10**5
+        sample_size = 100
+        arr = ['s%04d' % i for i in np.random.randint(0, n // 10, size=n)]
+        self.sample = np.random.choice(arr, sample_size)
+        self.ts = pd.Series(arr).astype('category')
+
+    def time_isin_categorical_strings(self):
+        self.ts.isin(self.sample)
diff --git a/doc/source/whatsnew/v0.23.0.txt b/doc/source/whatsnew/v0.23.0.txt
index 09bd09b06d9b9..62b19c43a15a1 100644
--- a/doc/source/whatsnew/v0.23.0.txt
+++ b/doc/source/whatsnew/v0.23.0.txt
@@ -896,6 +896,7 @@ Performance Improvements
 - Improved performance of :func:`pandas.core.groupby.GroupBy.ffill` and :func:`pandas.core.groupby.GroupBy.bfill` (:issue:`11296`)
 - Improved performance of :func:`pandas.core.groupby.GroupBy.any` and :func:`pandas.core.groupby.GroupBy.all` (:issue:`15435`)
 - Improved performance of :func:`pandas.core.groupby.GroupBy.pct_change` (:issue:`19165`)
+- Improved performance of :func:`Series.isin` in the case of categorical dtypes (:issue:`20003`)
 
 .. _whatsnew_0230.docs:
 
diff --git a/pandas/core/algorithms.py b/pandas/core/algorithms.py
index 065a5782aced1..df34b3540fa3b 100644
--- a/pandas/core/algorithms.py
+++ b/pandas/core/algorithms.py
@@ -407,6 +407,12 @@ def isin(comps, values):
     if not isinstance(values, (ABCIndex, ABCSeries, np.ndarray)):
         values = construct_1d_object_array_from_listlike(list(values))
 
+    if is_categorical_dtype(comps):
+        # handle categoricals
+        return comps._values.isin(values)
+
+    comps = com._values_from_object(comps)
+
     comps, dtype, _ = _ensure_data(comps)
     values, _, _ = _ensure_data(values, dtype=dtype)
 
diff --git a/pandas/core/arrays/categorical.py b/pandas/core/arrays/categorical.py
index b5a4785fd98a6..baa73e9e4a1fc 100644
--- a/pandas/core/arrays/categorical.py
+++ b/pandas/core/arrays/categorical.py
@@ -39,6 +39,8 @@
 from pandas.util._decorators import (
     Appender, cache_readonly, deprecate_kwarg, Substitution)
 
+import pandas.core.algorithms as algorithms
+
 from pandas.io.formats.terminal import get_terminal_size
 from pandas.util._validators import validate_bool_kwarg, validate_fillna_kwargs
 from pandas.core.config import get_option
@@ -2216,6 +2218,60 @@ def _concat_same_type(self, to_concat):
     def _formatting_values(self):
         return self
 
+    def isin(self, values):
+        """
+        Check whether `values` are contained in Categorical.
+
+        Return a boolean NumPy Array showing whether each element in
+        the Categorical matches an element in the passed sequence of
+        `values` exactly.
+
+        Parameters
+        ----------
+        values : set or list-like
+            The sequence of values to test. Passing in a single string will
+            raise a ``TypeError``. Instead, turn a single string into a
+            list of one element.
+
+        Returns
+        -------
+        isin : numpy.ndarray (bool dtype)
+
+        Raises
+        ------
+        TypeError
+          * If `values` is a string
+
+        See Also
+        --------
+        pandas.Series.isin : equivalent method on Series
+
+        Examples
+        --------
+
+        >>> s = pd.Categorical(['lama', 'cow', 'lama', 'beetle', 'lama',
+        ...                'hippo'])
+        >>> s.isin(['cow', 'lama'])
+        array([ True,  True,  True, False,  True, False])
+
+        Passing a single string as ``s.isin('lama')`` will raise an error. Use
+        a list of one element instead:
+
+        >>> s.isin(['lama'])
+        array([ True, False,  True, False,  True, False])
+        """
+        if not is_list_like(values):
+            raise TypeError("only list-like objects are allowed to be passed"
+                            " to isin(), you passed a [{values_type}]"
+                            .format(values_type=type(values).__name__))
+        from pandas.core.series import _sanitize_array
+        values = _sanitize_array(values, None, None)
+        null_mask = np.asarray(isna(values))
+        code_values = self.categories.get_indexer(values)
+        code_values = code_values[null_mask | (code_values >= 0)]
+        return algorithms.isin(self.codes, code_values)
+
+
 # The Series.cat accessor
 
 
diff --git a/pandas/core/indexes/base.py b/pandas/core/indexes/base.py
index 12bb09e8f8a8a..586190fbc65d8 100644
--- a/pandas/core/indexes/base.py
+++ b/pandas/core/indexes/base.py
@@ -3487,7 +3487,7 @@ def isin(self, values, level=None):
         """
         if level is not None:
             self._validate_index_level(level)
-        return algos.isin(np.array(self), values)
+        return algos.isin(self, values)
 
     def _can_reindex(self, indexer):
         """
diff --git a/pandas/core/series.py b/pandas/core/series.py
index 1d6f770d92795..89916872651ac 100644
--- a/pandas/core/series.py
+++ b/pandas/core/series.py
@@ -3564,7 +3564,7 @@ def isin(self, values):
         5    False
         Name: animal, dtype: bool
         """
-        result = algorithms.isin(com._values_from_object(self), values)
+        result = algorithms.isin(self, values)
         return self._constructor(result, index=self.index).__finalize__(self)
 
     def between(self, left, right, inclusive=True):
diff --git a/pandas/tests/categorical/test_algos.py b/pandas/tests/categorical/test_algos.py
index f727184e862d8..1c68377786dd4 100644
--- a/pandas/tests/categorical/test_algos.py
+++ b/pandas/tests/categorical/test_algos.py
@@ -47,3 +47,25 @@ def test_factorized_sort_ordered():
 
     tm.assert_numpy_array_equal(labels, expected_labels)
     tm.assert_categorical_equal(uniques, expected_uniques)
+
+
+def test_isin_cats():
+    # GH2003
+    cat = pd.Categorical(["a", "b", np.nan])
+
+    result = cat.isin(["a", np.nan])
+    expected = np.array([True, False, True], dtype=bool)
+    tm.assert_numpy_array_equal(expected, result)
+
+    result = cat.isin(["a", "c"])
+    expected = np.array([True, False, False], dtype=bool)
+    tm.assert_numpy_array_equal(expected, result)
+
+
+@pytest.mark.parametrize("empty", [[], pd.Series(), np.array([])])
+def test_isin_empty(empty):
+    s = pd.Categorical(["a", "b"])
+    expected = np.array([False, False], dtype=bool)
+
+    result = s.isin(empty)
+    tm.assert_numpy_array_equal(expected, result)


Code review comments:
diff_hunk: @@ -2216,6 +2218,60 @@ def _concat_same_type(self, to_concat):
     def _formatting_values(self):
         return self
 
+    def isin(self, values):
+        """
+        Check whether `values` are contained in Categorical.
+
+        Return a boolean NumPy Array showing whether each element in
+        the Categorical matches an element in the passed sequence of
+        `values` exactly.
+
+        Parameters
+        ----------
+        values : set or list-like
+            The sequence of values to test. Passing in a single string will
+            raise a ``TypeError``. Instead, turn a single string into a
+            list of one element.
+
+        Returns
+        -------
+        isin : numpy.ndarray (bool dtype)
+
+        Raises
+        ------
+        TypeError
+          * If `values` is a string
+
+        See Also
+        --------
+        pandas.Series.isin : equivalent method on Series
+
+        Examples
+        --------
+
+        >>> s = pd.Categorical(['lama', 'cow', 'lama', 'beetle', 'lama',
+        ...                'hippo'])
+        >>> s.isin(['cow', 'lama'])
+        array([ True,  True,  True, False,  True, False])
+
+        Passing a single string as ``s.isin('lama')`` will raise an error. Use
+        a list of one element instead:
+
+        >>> s.isin(['lama'])
+        array([ True, False,  True, False,  True, False])
+        """
+        if not is_list_like(values):
+            raise TypeError("only list-like objects are allowed to be passed"
+                            " to isin(), you passed a [{values_type}]"
+                            .format(values_type=type(values).__name__))
+        from pandas.core.series import _sanitize_array
path: pandas/core/arrays/categorical.py
text: @user1:
can you move the import to top of function

diff_hunk: @@ -148,3 +148,18 @@ def time_rank_int_cat(self):
 
     def time_rank_int_cat_ordered(self):
         self.s_int_cat_ordered.rank()
+
+
+class Isin(object):
+
+    goal_time = 0.2
+
+    def setup(self):
+        n = 5 * 10**5
+        sample_size = 100
+        arr = ['s%04d' % i for i in np.random.randint(0, n // 10, size=n)]
+        self.sample = np.random.choice(arr, sample_size)
+        self.ts = pd.Series(arr).astype('category')
+
+    def time_isin_categorical_strings(self):
path: asv_bench/benchmarks/categoricals.py
text: @user1:
there are 4 cases in the original issue can you cover them