pandas "isin" is much slower than numpy "in1d"

Question

There is a huge difference between pandas "isin" and numpy "in1d" from the efficiency aspect. After some research I've noticed that the type of the data and the values that passed as parameter to the "in" method has huge impact on the run time. Anyway it looks that numpy implementation suffer much less from this problem. What's going on here?

import timeit
import pandas as pd
import numpy as np
df = pd.DataFrame(np.random.randint(0,10,(10**6),dtype='int8'),columns=['A'])
vals = np.array([5,7],dtype='int64')
f = lambda: df['A'].isin(vals)
g = lambda: pd.np.in1d(df['A'],vals)
print 'pandas:', timeit.timeit(stmt='f()',setup='from __main__ import f',number=10)/10
print 'numpy :', timeit.timeit(stmt='g()',setup='from __main__ import g',number=10)/10
>>
**pandas: 0.0541711091995
numpy : 0.000645089149475**

Answer 1

Numpy and Pandas use different algorithms for isin. For some cases numpy's version is faster and for some pandas'. For your test case numpy seems to be faster.

Pandas' version has however a better asymptotic running time, in will win for bigger datasets.

---

Let's assume that there are n elements in the data-series (df in your example) and m elements in the query (vals in your example).

Usually, Numpy's algorithm does the following:

• Use np.unique(..) to find all unique elements in the series. Thus is done via sorting, i.e. O(n*log(n)), there might be N<=n unique elements.
• For every element use binary search to look up whether element is in the series, i.e. O(m*log(N)) in overall.

Which leads to overall running time of O(n*log(n) + m*log(N)).

There are some hard-coded optimizations in place for the cases, when vals only few elements and for this cases numpy really shines.

Pandas does something different:

• Populates a hash-map (wrapped khash-functionality) in order to find all unique elements, which takes O(n).
• Looks-up in the hash map in O(1) for every query, i.e. O(m) in overall.

I overall, running time is O(n)+O(m), which is much better than Numpy's.

However, for smaller inputs, constant factors and not the asymptotic behavior is that what counts and it is just way better for Numpy. There are also other consideration, like memory consumption (which is higher for Pandas) which might play a role.

But if we take a bigger query set, the situation is completely different:

import pandas as pd
import numpy as np
df = pd.DataFrame(np.random.randint(0,10,(10**6),dtype='int8'),columns=['A'])
vals = np.array([5,7],dtype='int64')
vals2 = np.random.randint(0,10,(10**6),dtype='int64')

And now:

%timeit df['A'].isin(vals)    # 17.0 ms 
%timeit df['A'].isin(vals2)   # 16.8 ms

%timeit pd.np.in1d(df['A'],vals)    # 1.36
%timeit pd.np.in1d(df['A'],vals2)   # 82.9 ms

Numpy is really losing ground as long as there are more queries. It can also be seen, that building of the hash-map is the bottleneck for Pandas and not the queries.

In the end it doesn't make much sense (even if I just did!) to evaluate the performance for only one input size - it should be done for a range of input sizes - there are some surprises to be discovered!

E.g. fun fact: if you would take

df = pd.DataFrame(np.random.randint(0,10,(10**6+1), dtype='int8'),columns=['A'])

i.e. 10^6+1 instead of 10^6, pandas would fall back to numpy's algorithm (which is not clever in my opinion) and would become better for small inputs but worse for big:

%timeit df['A'].isin(vals)    # 6ms  was 17.0 ms 
%timeit df['A'].isin(vals2)   # 100ms was 16.8 ms