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 做了一些不同的事情：

• 填充哈希映射（包装khash功能）以查找所有唯一元素，这需要O(n).
• O(1)对于每个查询（即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 就真的会节节败退。还可以看出，哈希映射的构建是 Pandas 的瓶颈，而不是查询。

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

例如有趣的事实：如果你愿意

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

也就是说10^6+1，10^6pandas 会退回到 numpy 的算法（在我看来这并不聪明），并且对于小输入会变得更好，但对于大输入会更糟：

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