Repository: pandas-dev/pandas
Pull request: BUG: fix isin with nans and large arrays
Does a np.isnan if nan is given to isin and we have a large enough array to trigger the `np.in1d` path
- [x] closes #22205
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry


Problem statement:
Inconsistent handling of nan-float64 in Series.isin()
#### Code Sample, a copy-pastable example if possible

```python
N=10**6
s=pd.Series(np.full(N, np.nan, dtype=np.float64), copy=False)
s.isin([np.nan]).all()
```

results in `True`, however

```python
s=pd.Series(np.full(N+1, np.nan, dtype=np.float64), copy=False)
s.isin([np.nan]).all()
```
 results in `False`, even more  `s.isin([np.nan]).any()` results in `False`

#### Problem description

Obviously, the result should be the same in both cases.

#### Expected Output

 IMO `True` is more consistent with the behavior of Pandas in other functions (such as `pd.unique()`).

#### Output of ``pd.show_versions()``

<details>

INSTALLED VERSIONS
------------------
commit: None
python: 3.6.2.final.0
python-bits: 64
OS: Linux
OS-release: 4.4.0-53-generic
machine: x86_64
processor: x86_64
byteorder: little
LC_ALL: None
LANG: en_US.UTF-8
LOCALE: en_US.UTF-8

pandas: 0.22.0
pytest: 3.2.1
pip: 10.0.1
setuptools: 36.5.0.post20170921
Cython: 0.28.3
numpy: 1.13.1
scipy: 1.1.0
pyarrow: None
xarray: None
IPython: 6.1.0
sphinx: 1.6.3
patsy: 0.4.1
dateutil: 2.6.1
pytz: 2017.2
blosc: None
bottleneck: 1.2.1
tables: 3.4.2
numexpr: 2.6.2
feather: None
matplotlib: 2.0.2
openpyxl: 2.4.8
xlrd: 1.1.0
xlwt: 1.3.0
xlsxwriter: 0.9.8
lxml: 3.8.0
bs4: 4.6.0
html5lib: 0.9999999
sqlalchemy: 1.1.13
pymysql: None
psycopg2: None
jinja2: 2.9.6
s3fs: 0.1.3
fastparquet: None
pandas_gbq: None
pandas_datareader: None

</details>

Hints from issue discussion:
The problem at core of this issue, is that pandas' `unique` and numpy's `unique` have different notions about nan's in the case of `float64`:

```
>>> pd.unique([np.nan, np.nan])
array([ nan])
>>> np.unique([np.nan, np.nan])
array([ nan,  nan])
```

For N>10^6, pandas' notion of unique is switched to numpy's notion of unique:

```
    f = lambda x, y: htable.ismember_object(x, values)
    # GH16012
    # Ensure np.in1d doesn't get object types or it *may* throw an exception
    if len(comps) > 1000000 and not is_object_dtype(comps):
          f = lambda x, y: np.in1d(x, y)
```

[Here the whole code](https://github.com/pandas-dev/pandas/blob/master/pandas/core/algorithms.py#L425)
It seems, as if `np.in1d` is used because it is faster. 

I don't  understand the [the 'in1d- algorithm](https://github.com/numpy/numpy/blob/23cb605d7f230ee2b00c0e7167256cf434731b16/numpy/lib/arraysetops.py#L434) good enough, to tell what is going on, but here are my benchmark and timings:
```
port pandas.core.algorithms as algos
uses_pandas = np.arange(10**6)
uses_numpy = np.arange(10**6+1)
small = np.arange(2)
small2 = np.arange(10)
large = np.arange(10**7)
%timeit algos.isin(uses_pandas, small)
%timeit algos.isin(uses_numpy, small)
%timeit algos.isin(uses_pandas, small2)
%timeit algos.isin(uses_numpy, small2)
%timeit algos.isin(uses_pandas, large)
%timeit algos.isin(uses_numpy, large)
```

results in
```
                pandas vs numpy
small          4.4ms      2.4ms
small2        5.5ms     10.9ms
large          277 ms 699 ms
```
To me it seems, as if for large inputs of look-up-values, the hash-map-approach could be the better one.

Actually, [there is an optimization](https://github.com/numpy/numpy/blob/23cb605d7f230ee2b00c0e7167256cf434731b16/numpy/lib/arraysetops.py#L510) if the size of the second array is very small:

```
    if len(ar2) < 10 * len(ar1) ** 0.145 or contains_object:
        if invert:
            mask = np.ones(len(ar1), dtype=bool)
            for a in ar2:
                mask &= (ar1 != a)
        else:
            mask = np.zeros(len(ar1), dtype=bool)
            for a in ar2:
                mask |= (ar1 == a)
      return mask
```

which leads to `O(n*m)` behavior (n.m - sizes of input arrays)for small sizes `m` of the second array. This linear behavior can also be seen in the timing.

The running times of algorithms are

 pandas:    `O(n+m)` if look-up can be assumed to be `O(1)`
 np.in1d:    `O(n*log(n)+m*log(m) +(N+M)log(N+M))` if there are N/M unique elements in the arrays

So it looks like `np.in1d` is only faster if there are less than 5 elements in the second array.

Commit message: update whats new

Patch to review:
diff --git a/doc/source/whatsnew/v1.1.3.rst b/doc/source/whatsnew/v1.1.3.rst
index 8ead78a17e9c2..5b1e77d917cf0 100644
--- a/doc/source/whatsnew/v1.1.3.rst
+++ b/doc/source/whatsnew/v1.1.3.rst
@@ -30,6 +30,8 @@ Bug fixes
 - Bug in :meth:`Series.str.startswith` and :meth:`Series.str.endswith` with ``category`` dtype not propagating ``na`` parameter (:issue:`36241`)
 - Bug in :class:`Series` constructor where integer overflow would occur for sufficiently large scalar inputs when an index was provided (:issue:`36291`)
 - Bug in :meth:`DataFrame.stack` raising a ``ValueError`` when stacking :class:`MultiIndex` columns based on position when the levels had duplicate names (:issue:`36353`)
+- Bug in :meth:`isin()` when using NaN and a row length above 1,000,000 (:issue:`22205`)
+- Bug in :meth:`Series.isin` when using ``NaN`` and a row length above 1,000,000 (:issue:`22205`)
 
 .. ---------------------------------------------------------------------------
 
diff --git a/pandas/core/algorithms.py b/pandas/core/algorithms.py
index 2ce3f2d9a7bfa..50d1810fee30d 100644
--- a/pandas/core/algorithms.py
+++ b/pandas/core/algorithms.py
@@ -440,7 +440,12 @@ def isin(comps: AnyArrayLike, values: AnyArrayLike) -> np.ndarray:
     # GH16012
     # Ensure np.in1d doesn't get object types or it *may* throw an exception
     if len(comps) > 1_000_000 and not is_object_dtype(comps):
-        f = np.in1d
+        # If the the values include nan we need to check for nan explicitly
+        # since np.nan it not equal to np.nan
+        if np.isnan(values).any():
+            f = lambda c, v: np.logical_or(np.in1d(c, v), np.isnan(c))
+        else:
+            f = np.in1d
     elif is_integer_dtype(comps):
         try:
             values = values.astype("int64", copy=False)
diff --git a/pandas/tests/test_algos.py b/pandas/tests/test_algos.py
index a2c2ae22a0b62..acc9bb21ad41c 100644
--- a/pandas/tests/test_algos.py
+++ b/pandas/tests/test_algos.py
@@ -801,7 +801,6 @@ def test_i8(self):
         tm.assert_numpy_array_equal(result, expected)
 
     def test_large(self):
-
         s = pd.date_range("20000101", periods=2000000, freq="s").values
         result = algos.isin(s, s[0:2])
         expected = np.zeros(len(s), dtype=bool)
@@ -841,6 +840,23 @@ def test_same_nan_is_in(self):
         result = algos.isin(comps, values)
         tm.assert_numpy_array_equal(expected, result)
 
+    # issue:`22205`
+    def test_same_nan_is_in_large(self):
+        s = np.tile(1.0, 1_000_001)
+        s[0] = np.nan
+        result = algos.isin(s, [np.nan, 1])
+        expected = np.ones(len(s), dtype=bool)
+        tm.assert_numpy_array_equal(result, expected)
+
+    # issue:`#25395`
+    def test_same_nan_is_in_large_series(self):
+        s = np.tile(1.0, 1_000_001)
+        series = pd.Series(s)
+        s[0] = np.nan
+        result = series.isin([np.nan, 1])
+        expected = pd.Series(np.ones(len(s), dtype=bool))
+        tm.assert_series_equal(result, expected)
+
     def test_same_object_is_in(self):
         # GH 22160
         # there could be special treatment for nans


Code review comments:
diff_hunk: @@ -30,6 +30,8 @@ Bug fixes
 - Bug in :meth:`Series.str.startswith` and :meth:`Series.str.endswith` with ``category`` dtype not propagating ``na`` parameter (:issue:`36241`)
 - Bug in :class:`Series` constructor where integer overflow would occur for sufficiently large scalar inputs when an index was provided (:issue:`36291`)
 - Bug in :meth:`DataFrame.stack` raising a ``ValueError`` when stacking :class:`MultiIndex` columns based on position when the levels had duplicate names (:issue:`36353`)
+- Bug in :meth:`isin()` when using NaN and a row length above 1,000,000 (:issue:`22205`)
path: doc/source/whatsnew/v1.1.3.rst
text: @user1:
Can you delete this note in favor of the one below?