Numpy和Pandas使用不同的算法来处理
isin
。对于某些情况,numpy的版本更快,而对于某些情况,pandas的版本更快。在您的测试用例中,numpy似乎更快。
然而,Pandas的版本具有更好的渐进运行时间,在更大的数据集上胜出。
假设数据系列(在您的示例中为
df
)中有
n
个元素,查询中有
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。还有其他考虑因素,如内存消耗(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)
%timeit df['A'].isin(vals2)
%timeit pd.np.in1d(df['A'],vals)
%timeit pd.np.in1d(df['A'],vals2)
Numpy在查询数量增加时逐渐失去优势。可以看出,对于Pandas来说,构建哈希表是瓶颈,而非查询。
最终,仅对一个输入大小进行性能评估并没有太多意义(即使我刚刚这样做了!)- 应该对一系列输入大小进行评估 - 还有一些惊喜等待着我们发现!
例如,有趣的事实:如果你采用
df = pd.DataFrame(np.random.randint(0,10,(10**6+1), dtype='int8'),columns=['A'])
即使是 10^6
,也需变成 10^6+1
,因为pandas会退回到numpy的算法(我认为不太聪明),这将导致对于小输入更好,但对于大输入更差:
%timeit df['A'].isin(vals)
%timeit df['A'].isin(vals2)