Pandas "isin"比 numpy "in1d"慢得多

Question

pandas "isin"和 numpy "in1d"在效率方面有很大的不同。经过一些研究，我注意到数据类型和作为参数传递给“in”方法的值对运行时间有巨大影响。无论如何，看起来 numpy 实现受到这个问题的影响要小得多。这是怎么回事？

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 和 Pandas 对 isin 使用不同的算法.在某些情况下，numpy 的版本更快，而对于某些 pandas 而言。对于您的测试用例，numpy 似乎更快。

Pandas 的版本具有更好的渐近运行时间，将赢得更大的数据集。

---

假设有 n数据系列中的元素(在您的示例中为 df)和 m查询中的元素(在您的示例中为 vals)。

通常，Numpy 的算法会执行以下操作:

• 使用np.unique(..)找到该系列中的所有独特元素。这是通过排序完成的，即 O(n*log(n)) , 可能有 N<=n独特的元素。
• 对每个元素使用二分查找查找元素是否在系列中，即O(m*log(N))总体而言。

这导致整体运行时间为 O(n*log(n) + m*log(N)) .

当 vals 时，针对这些情况进行了一些硬编码优化。只有很少的元素，对于这种情况，numpy 真的很出色。

Pandas 做了一些不同的事情:

• 填充 HashMap (包装 khash - 功能)以查找所有唯一元素，这需要 O(n) .
• 在 O(1) 中的 HashMap 中查找对于每个查询，即 O(m)总体而言。

我总的来说，运行时间是O(n)+O(m) ，这比 Numpy 的要好得多。

然而，对于较小的输入，常数因子而不是渐近行为才是最重要的，它对 Numpy 来说更好。还有其他考虑因素，例如内存消耗(对于 Pandas 来说更高)可能会起作用。

但是如果我们采用更大的查询集，情况就完全不同了:

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')

现在:

%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 就真的在失去优势。还可以看出，构建 HashMap 是 Pandas 的瓶颈，而不是查询。

最后，仅评估一种输入大小的性能并没有多大意义(即使我刚刚这样做了!)——应该针对一系列输入大小进行评估——有一些惊喜有待发现!

例如有趣的事实:如果你愿意接受

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

即10^6+1而不是 10^6 , pandas 会退回到 numpy 的算法(我认为这并不聪明)并且对于小输入会变得更好但对于大输入会更糟:

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