Pandas pd.Series.isin性能与集合与数组

Question

在Python中,一般来说,可散列集合的成员资格最好通过测试set.我们知道这一点,因为哈希的使用为我们提供了O(1)查找复杂度,而O(n)为list或np.ndarray.

在Pandas中,我经常需要检查非常大的集合中的成员资格.我推测同样适用,即检查一个系列中的每个项目的成员资格set比使用list或更有效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,以np.ndarray转换.

否定构建投入的成本,对熊猫的影响:

• 如果您知道自己的元素x_list或是x_arr独特的,请不要费心转换为x_set.与Pandas一起使用这将是昂贵的(转换和成员资格测试).
• 使用列表推导是从O(1)集查找中受益的唯一方法.

我的问题是:

1. 我的分析是否正确？对于如何pd.Series.isin实施,这似乎是一个显而易见但未记录的结果.
2. 有一种解决方法,不使用列表理解或者pd.Series.apply,这确实使用O(1)组查找？或者这是不可避免的设计选择和/或将NumPy作为熊猫骨干的必然结果？

更新:在一个旧的设置(熊猫/ NumPy的版本),我看到x_set跑赢x_arr同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'

Answer 1

这可能不是很明显,但pd.Series.isin使用O(1)- 查找.

经过分析,证明了上述说法,我们将利用其洞察力创建一个Cython原型,可以轻松击败最快的开箱即用解决方案.

我们假设"set"有n元素,"series"有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.它的定义可以在这里找到:

• 在预处理步骤中,哈希映射(pandas使用来自klib的khash)是从n元素x_arr(即运行时)中创建的O(n).
• m查找在构造的哈希映射中的O(1)每个或O(m)全部发生.
• 结果是 T(n,m)=O(m)+O(n)

我们必须记住 - numpy-array的元素是raw-C-integers而不是原始集合中的Python对象 - 所以我们不能按原样使用set.

将Python对象集转换为一组C-int的替代方法是将单个C-int转换为Python-object,从而能够使用原始集.这就是[i in x_set for i in ser.values]-variant中发生的事情:

• 没有预处理.
• m个查找O(1)每次或O(m)总共发生,但由于必要的Python对象创建,查找速度较慢.
• 结果是 T(n,m)=O(m)

显然,使用Cython可以加快这个版本的速度.

但是足够的理论,让我们来看看n固定ms的不同s 的运行时间:

我们可以看到:预处理的线性时间占据了大ns 的numpy版本.从numpy转换为pure-python(numpy->python)的版本具有与pure-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和m大致相等,这是很难说哪种解决方案是最佳的未经测试.

• 如果你有它在你的控制之下:最好的做法是set直接构建一个C整数集(khash(已经包装在pandas中)或甚至一些c ++ - 实现),从而消除了预处理的需要.我不知道,大熊猫中是否有可以重复使用的东西,但在Cython中编写函数可能不是什么大问题.

问题是,最后一个建议并不是开箱即用的,因为在它们的界面中,大熊猫和numpy都没有一套概念(至少对我有限的知识).但是拥有raw-C-set-interfaces将是两全其美的:

• 不需要预处理,因为值已作为集合传递
• 不需要转换,因为传递的集合包含raw-C值

我为khash编写了一个快速而又脏的Cython包装器(灵感来自pandas中的包装器),可以通过pip install https://github.com/realead/cykhash/zipball/masterCython进行安装,然后与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

作为另一种可能性,unordered_map可以包装c ++ (参见清单C),其缺点是需要c ++库和(正如我们将看到的)稍慢.

比较方法(参见清单D创建时间):

khash numpy->python比纯蟒蛇快约20倍,比纯蟒蛇快6倍(但纯蟒蛇不是我们想要的),甚至比cpp的版本快3倍.

房源

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)

现在:

>>> 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-wrapper:

%%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:使用不同的set-wrappers绘制结果:

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