一般来说，在 Python 中，可哈希集合的成员资格最好通过以下方式进行测试set。我们知道这一点是因为散列的使用为我们提供了 O(1) 查找复杂度，而对于list or np.ndarray.
在 Pandas 中，我经常需要检查非常大的集合中的成员资格。我认为同样的情况也适用，即检查系列中的每个项目是否属于某个系列set比使用更有效list or np.ndarray。然而，情况似乎并非如此：
import numpy as np
import pandas as pd
np.random.seed(0)
x_set = {i for i in range(100000)}
x_arr = np.array(list(x_set))
x_list = list(x_set)
arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()
%timeit ser.isin(x_set) # 8.9 ms
%timeit ser.isin(x_arr) # 2.17 ms
%timeit ser.isin(x_list) # 7.79 ms
%timeit np.in1d(arr, x_arr) # 5.02 ms
%timeit [i in x_set for i in lst] # 1.1 ms
%timeit [i in x_set for i in ser.values] # 4.61 ms
用于测试的版本：
np.__version__ # '1.14.3'
pd.__version__ # '0.23.0'
sys.version # '3.6.5'
源代码为pd.Series.isin，我相信，利用numpy.in1d，这可能意味着很大的开销set to np.ndarray转换。
否定构建输入的成本，对 Pandas 的影响：
x_list or x_arr是独一无二的，不必费心转换为x_set。对于 Pandas 来说，这将是昂贵的（转换和成员测试）。我的问题是：
pd.Series.isin已实施。pd.Series.apply, which does利用 O(1) 集合查找？或者这是不可避免的设计选择和/或以 NumPy 作为 Pandas 骨干的必然结果？Update：在较旧的设置（Pandas / NumPy 版本）上我明白了x_set跑赢大盘x_arr with pd.Series.isin。所以还有一个问题：是否有任何从旧到新的根本变化会导致性能set恶化？
%timeit ser.isin(x_set) # 10.5 ms
%timeit ser.isin(x_arr) # 15.2 ms
%timeit ser.isin(x_list) # 9.61 ms
%timeit np.in1d(arr, x_arr) # 4.15 ms
%timeit [i in x_set for i in lst] # 1.15 ms
%timeit [i in x_set for i in ser.values] # 2.8 ms
pd.__version__ # '0.19.2'
np.__version__ # '1.11.3'
sys.version # '3.6.0'
这可能并不明显，但是pd.Series.isin uses O(1)-查找每个元素。
经过分析证明上述陈述后，我们将利用其见解来创建一个 Cython 原型，它可以轻松击败最快的开箱即用解决方案。
我们假设“集合”有n元素和“系列”有m元素。那么运行时间为：
T(n,m)=T_preprocess(n)+m*T_lookup(n)
对于纯 python 版本，这意味着：
T_preprocess(n)=0- 无需预处理T_lookup(n)=O(1)- python 集合的众所周知的行为T(n,m)=O(m)
会发生什么pd.Series.isin(x_arr)？显然，如果我们跳过预处理并在线性时间内搜索，我们将得到O(n*m)，这是不可接受的。
借助调试器或分析器（我使用 valgrind-callgrind+kcachegrind）很容易看到发生了什么：工作的马是函数__pyx_pw_6pandas_5_libs_9hashtable_23ismember_int64。其定义可以查到here:
n元素来自x_arr，即在运行时O(n).m查找发生在O(1)每个或O(m)总共在构造的哈希图中。T(n,m)=O(m)+O(n)
我们必须记住 - numpy-array 的元素是原始 C 整数，而不是原始集合中的 Python 对象 - 所以我们不能按原样使用该集合。
将 Python 对象集转换为 C 整数集的另一种方法是将单个 C 整数转换为 Python 对象，从而能够使用原始集。这就是发生在[i in x_set for i in ser.values]-变体：
O(1)每次或O(m)总共，但由于需要创建 Python 对象，查找速度较慢。T(n,m)=O(m)
显然，您可以使用 Cython 稍微加快此版本的速度。
但理论已经足够了，让我们看看不同情况下的运行时间ns 与固定ms:
我们可以看到：预处理的线性时间在大型的 numpy 版本中占主导地位n是。从 numpy 转换为纯 python 的版本（numpy->python）与纯 python 版本具有相同的恒定行为，但由于必要的转换而速度较慢 - 这一切都符合我们的分析。
这在图中看不清楚：如果n < mnumpy 版本变得更快 - 在这种情况下，查找速度更快khash-lib 起着最重要的作用，而不是预处理部分。
我从这个分析中得出的结论是：
n < m: pd.Series.isin应该采取，因为O(n)- 预处理并不那么昂贵。
n > m：（可能是 cythonized 版本）[i in x_set for i in ser.values]应采取，因此O(n)避免了。
显然存在一个灰色地带n and m近似相等，未经测试很难判断哪种解决方案最好。
如果你能控制它：最好的办法是构建set直接作为 C 整数集 (khash (已经被熊猫包裹了）或者甚至可能是一些 C++ 实现），从而消除了预处理的需要。我不知道 pandas 中是否有可以重用的东西，但在 Cython 中编写该函数可能不是什么大问题。
问题是最后一个建议不能开箱即用，因为 pandas 和 numpy 在它们的界面中都没有集合的概念（至少就我有限的知识而言）。但拥有原始 C 集接口将是两全其美：
我编写了一个快速而肮脏的代码khash 的 Cython 包装器（受到 pandas 中包装器的启发），可以通过以下方式安装pip install https://github.com/realead/cykhash/zipball/master然后与 Cython 一起使用以获得更快的速度isin版本：
%%cython
import numpy as np
cimport numpy as np
from cykhash.khashsets cimport Int64Set
def isin_khash(np.ndarray[np.int64_t, ndim=1] a, Int64Set b):
cdef np.ndarray[np.uint8_t,ndim=1, cast=True] res=np.empty(a.shape[0],dtype=np.bool)
cdef int i
for i in range(a.size):
res[i]=b.contains(a[i])
return res
作为进一步的可能性，c++unordered_map可以被包装（参见清单 C），它的缺点是需要 c++ 库并且（正如我们将看到的）速度稍慢。
比较这些方法（参见清单 D 创建时序）：
khash 的速度大约比 20 倍快numpy->python，比纯 python 快约 6 倍（但无论如何，纯 python 都不是我们想要的），甚至比 cpp 版本快约 3 倍。
Listings
1) 使用 valgrind 进行分析：
#isin.py
import numpy as np
import pandas as pd
np.random.seed(0)
x_set = {i for i in range(2*10**6)}
x_arr = np.array(list(x_set))
arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
for _ in range(10):
ser.isin(x_arr)
and now:
>>> valgrind --tool=callgrind python isin.py
>>> kcachegrind
导致以下调用图：
B：用于生成运行时间的 ipython 代码：
import numpy as np
import pandas as pd
%matplotlib inline
import matplotlib.pyplot as plt
np.random.seed(0)
x_set = {i for i in range(10**2)}
x_arr = np.array(list(x_set))
x_list = list(x_set)
arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()
n=10**3
result=[]
while n<3*10**6:
x_set = {i for i in range(n)}
x_arr = np.array(list(x_set))
x_list = list(x_set)
t1=%timeit -o ser.isin(x_arr)
t2=%timeit -o [i in x_set for i in lst]
t3=%timeit -o [i in x_set for i in ser.values]
result.append([n, t1.average, t2.average, t3.average])
n*=2
#plotting result:
for_plot=np.array(result)
plt.plot(for_plot[:,0], for_plot[:,1], label='numpy')
plt.plot(for_plot[:,0], for_plot[:,2], label='python')
plt.plot(for_plot[:,0], for_plot[:,3], label='numpy->python')
plt.xlabel('n')
plt.ylabel('running time')
plt.legend()
plt.show()
C：cpp 包装器：
%%cython --cplus -c=-std=c++11 -a
from libcpp.unordered_set cimport unordered_set
cdef class HashSet:
cdef unordered_set[long long int] s
cpdef add(self, long long int z):
self.s.insert(z)
cpdef bint contains(self, long long int z):
return self.s.count(z)>0
import numpy as np
cimport numpy as np
cimport cython
@cython.boundscheck(False)
@cython.wraparound(False)
def isin_cpp(np.ndarray[np.int64_t, ndim=1] a, HashSet b):
cdef np.ndarray[np.uint8_t,ndim=1, cast=True] res=np.empty(a.shape[0],dtype=np.bool)
cdef int i
for i in range(a.size):
res[i]=b.contains(a[i])
return res
D：使用不同的集合包装器绘制结果：
import numpy as np
import pandas as pd
%matplotlib inline
import matplotlib.pyplot as plt
from cykhash import Int64Set
np.random.seed(0)
x_set = {i for i in range(10**2)}
x_arr = np.array(list(x_set))
x_list = list(x_set)
arr = np.random.randint(0, 20000, 10000)
ser = pd.Series(arr)
lst = arr.tolist()
n=10**3
result=[]
while n<3*10**6:
x_set = {i for i in range(n)}
x_arr = np.array(list(x_set))
cpp_set=HashSet()
khash_set=Int64Set()
for i in x_set:
cpp_set.add(i)
khash_set.add(i)
assert((ser.isin(x_arr).values==isin_cpp(ser.values, cpp_set)).all())
assert((ser.isin(x_arr).values==isin_khash(ser.values, khash_set)).all())
t1=%timeit -o isin_khash(ser.values, khash_set)
t2=%timeit -o isin_cpp(ser.values, cpp_set)
t3=%timeit -o [i in x_set for i in lst]
t4=%timeit -o [i in x_set for i in ser.values]
result.append([n, t1.average, t2.average, t3.average, t4.average])
n*=2
#ploting result:
for_plot=np.array(result)
plt.plot(for_plot[:,0], for_plot[:,1], label='khash')
plt.plot(for_plot[:,0], for_plot[:,2], label='cpp')
plt.plot(for_plot[:,0], for_plot[:,3], label='pure python')
plt.plot(for_plot[:,0], for_plot[:,4], label='numpy->python')
plt.xlabel('n')
plt.ylabel('running time')
ymin, ymax = plt.ylim()
plt.ylim(0,ymax)
plt.legend()
plt.show()